PaperlayerView exact revision on arXiv

Source-linked AI summary

Private Stochastic Convex Optimization: Optimal Rates in Linear Time

Vitaly Feldman, Tomer Koren, Kunal Talwar

arXiv:2005.04763v1cs.LGcs.CRmath.OCstat.ML

TL;DR

The paper addresses the inefficiency of prior differentially private stochastic convex optimization algorithms while preserving optimal excess population-loss bounds. It introduces variable-batch privacy amplification and localization techniques, achieving linear-time or near-linear-time algorithms under stated assumptions, with extensions to strongly convex and non-smooth cases.

  • Problem

    Prior differentially private stochastic convex optimization achieved optimal excess population-loss bounds but required substantially more gradient computations than optimal non-private algorithms.

  • Method

    The paper uses variable batch sizes with privacy amplification by iteration and a localization reduction based on uniformly stable non-private optimization algorithms.

  • Results

    O(min{n, n^2/d}) gradient computations achieve asymptotically optimal excess population-loss bounds, matching optimal non-private running time.

  • Takeaways & Limitations

    For d ≤ n, differential privacy adds no excess-loss or computational overhead under the paper’s assumptions; strongly convex extensions also achieve near-linear time.

  • Takeaways & Limitations

    The algorithms require a mild smoothness assumption, and privacy amplification by iteration applies only to algorithms outputting the last SGD iterate.

Abstract

from arXiv · show

We study differentially private (DP) algorithms for stochastic convex optimization: the problem of minimizing the population loss given i.i.d. samples from a distribution over convex loss functions. A recent work of Bassily et al. (2019) has established the optimal bound on the excess population loss achievable given $n$ samples. Unfortunately, their algorithm achieving this bound is relatively inefficient: it requires $O(\min\{n^{3/2}, n^{5/2}/d\})$ gradient computations, where $d$ is the dimension of the optimization problem. We describe two new techniques for deriving DP convex optimization algorithms both achieving the optimal bound on excess loss and using $O(\min\{n, n^2/d\})$ gradient computations. In particular, the algorithms match the running time of the optimal non-private algorithms. The first approach relies on the use of variable batch sizes and is analyzed using the privacy amplification by iteration technique of Feldman et al. (2018). The second approach is based on a general reduction to the problem of localizing an approximately optimal solution with differential privacy. Such localization, in turn, can be achieved using existing (non-private) uniformly stable optimization algorithms. As in the earlier work, our algorithms require a mild smoothness assumption. We also give a linear-time algorithm achieving the optimal bound on the excess loss for the strongly convex case, as well as a faster algorithm for the non-smooth case.

1 Introduction

The paper develops differentially private stochastic convex optimization algorithms that attain optimal excess population-loss bounds with linear-time computation under mild assumptions. It also examines privacy, smoothness, and strong-convexity trade-offs, including limitations of prior approaches.

  • Problem setting: Stochastic convex optimization minimizes expected population loss from i.i.d. samples, with excess population loss measuring solution quality.The problem supports applications including regression and classification and underlies continuous optimization methods for non-convex settings.
  • Motivation and prior work: Uniform-convergence approaches to private empirical risk minimization can yield suboptimal population-loss bounds, especially when n and d are comparable.Prior efficient private algorithms attain optimal loss bounds but may require substantially more than the n gradient evaluations used by optimal non-private methods.
  • Contributions: The paper introduces two techniques achieving asymptotically optimal excess population-loss bounds with O(min{n, n^2/d}) gradient computations.For d ≤ n, privacy adds no excess-loss or computational overhead; for d ≥ n, excess loss increases, but optimal bounds remain achievable without computational overhead.
  • Variable-batch approach: Variable batch sizes combined with privacy amplification by iteration provide sufficient privacy for every data point, including points used in the final steps.The approach uses Snowball-SGD and exploits increasing batch sizes near the end of optimization.
  • Variable-batch approach: The privacy-amplification analysis applies only to the last SGD iterate, so the method relies on step sizes giving that iterate asymptotically optimal excess loss.Without the special step sizes, the last iterate incurs an excess-loss increase by a log n factor.
  • Localization approach: A localization reduction adds Gaussian noise to outputs of uniformly stable non-private optimizers, exploiting the weaker requirement of staying within R/2 of the solution.The analysis uses SGD bounds expressed through the second moment of distance to the optimum to avoid a logarithmic rate loss from high-probability localization.
  • Scope and extensions: The algorithms require mild smoothness; removing smoothness remains possible with prior methods, but their prox-based implementation can require O(n^4.5) gradient computations.A faster non-smooth variant based on strongly convex ERM uses O(n^2) gradient computations, leaving further improvement as an open direction.
  • Strongly convex case: For strongly convex stochastic optimization, the paper gives nearly linear-time algorithms matching known lower bounds, using iterative localization or privacy amplification by iteration.The strongly convex results preserve the near-zero privacy overhead in utility or efficiency when d ≤ n, up to a possible logarithmic overhead.

2 Preliminaries

The preliminaries define stochastic convex optimization, privacy notions, and contractive noisy iterations used to analyze private optimization algorithms.

  • Convex Loss Minimization: Stochastic convex optimization minimizes expected loss over a convex domain using i.i.d. samples, with excess population loss measuring solution quality.The objective is F(w)=E[f(w,x)], and performance is F(w)−min F.
  • Convex Loss Minimization: L-Lipschitz continuity bounds loss changes by parameter distance, while β-smoothness bounds gradient changes by parameter distance.
  • Differential Privacy: RDP and zCDP provide fine-grained privacy accounting, with composition adding privacy losses across adaptively chosen mechanisms.
  • Contractive Noisy Iteration: A contraction is a 1-Lipschitz map; projection onto a convex set and suitably sized gradient descent steps are contractions.For β-smooth convex functions, the gradient step is contractive when η≤2/β.
  • Contractive Noisy Iteration: Contractive noisy iteration alternates contractive maps with independent noise, enabling privacy analysis through noise-shift divergences.Gaussian noise has Rényi divergence proportional to the squared shift divided by its variance.

3 DP SCO via Privacy Amplification by Iteration

This section analyzes projected noisy SGD using variable batch sizes and privacy amplification by iteration, obtaining privacy guarantees alongside efficient optimization.

  • Noisy SGD: Projected noisy SGD averages gradients within batches, adds Gaussian noise, projects onto K, and returns the final iterate.
  • Privacy Guarantees: Privacy amplification by iteration analyzes each sample’s influence by treating later noise as additional noise on that sample’s gradient.
  • Privacy Guarantees: Contractivity follows from composing projection with a smooth convex gradient step, provided the step size satisfies ηt≤2/β.
  • Snowball-SGD: Variable batch sizes improve privacy guarantees, with Snowball-SGD using batches proportional to d/(T−t+1).
  • Utility Guarantees: The utility analysis uses last-iterate stochastic-gradient guarantees, including fixed-step schedules that avoid the logarithmic factor in some bounds.
  • Main Guarantee: The main corollary gives an RDP algorithm using n gradient evaluations and states its population-loss guarantee for i.i.d. samples.

4 Localization-Based Algorithms

The localization framework privatizes approximately optimal solutions by repeatedly shrinking the search region, using stable optimization methods for smooth and non-smooth losses.

  • Iterative Localization: Iterative localization adds Gaussian noise to low-sensitivity outputs while geometrically decreasing the radius around an approximately optimal solution.
  • Smooth Convex Losses: The framework first uses SGD for smooth convex losses, where bounded step sizes yield low L2-sensitivity under mild smoothness.
  • Smooth Convex Losses: Each localization phase provides privacy through Gaussian perturbation and utility through standard projected-SGD convergence guarantees.
  • Non-Smooth Losses: For non-smooth losses, Phased-ERM replaces SGD with regularized approximate ERM to obtain sensitivity and generalization guarantees.
  • Non-Smooth Losses: The non-smooth algorithm uses approximate optimization with high-probability accuracy and provides (ε,2δ)-DP guarantees.
  • Non-Smooth Losses: The approximate regularized ERM subproblems can be solved with SGD using a stated number of stochastic gradient computations.

5 The Strongly Convex Case

Under strong convexity, the paper shows that the optimal private stochastic optimization rate is attainable with linear-time algorithms under suitable smoothness and condition-number assumptions, while a reduction also gives an optimal-rate method using at most n samples.

  • The optimal strongly convex private rate is the larger of the two lower bounds and is attainable by a linear-time algorithm.
  • 5.1 Reduction to the Convex Case: A reduction repeatedly applies a private convex optimizer for ⌈log log n⌉ phases, using no more than n samples.Phase i uses n_i = 2^{i−2}n/log n iterations.
  • 5.2 Direct Algorithms for the Strongly Convex Case: With smoothness, the reduction can use Algorithm 2 for linear time; without smoothness, Algorithm 3 gives the optimal rate in quadratic time.
  • 5.1 Reduction to the Convex Case: The reduction reaches phase error Δ_k ≤ 2E_k after k > log log(Δ_1/E_1) phases, and therefore after ⌈log log n⌉ phases under the stated bounds.
  • 5.2 Direct Algorithms for the Strongly Convex Case: The direct linear-time algorithm applies when the condition number κ = β/λ is O(n/log n).The analysis uses fixed step sizes for stochastic strongly convex optimization.
  • 5.2.1 Fixed Step-size Algorithm for Strongly Convex SCO: The direct fixed-step analysis obtains its second bound by setting η = log(T)/(λT) and using strong convexity to bound the initial distance.
  • 5.2.3 Direct Algorithm via Privacy Amplification by Iteration: The privacy-amplification construction uses constant step sizes and batch sizes within a strongly convex, Lipschitz, smooth setting, subject to η ≤ 2/β.

6 No Privacy Amplification by Averaged Iteration

The paper gives a counterexample showing that averaging contractive noisy iterates need not preserve the privacy amplification enjoyed by the last iterate, including for long suffix averages.

  • Averaging is not generally guaranteed to have privacy comparable to the last iterate in contractive noisy iterations.
  • The construction uses contractive maps that inject the initial signal only during the first k steps and Gaussian noise thereafter.
  • The failure extends to suffix averaging over an Ω(T)-sized suffix and also yields a similar lower bound for online convex optimization.
Loading 2005.04763v1…