Private Stochastic Convex Optimization with Optimal Rates

By Raef Bassily, Vitaly Feldman, Kunal Talwar, Abhradeep Thakurta. 2019

273 citations recorded by the source corpus.

We study differentially private (DP) algorithms for stochastic convex optimization (SCO). In this problem the goal is to approximately minimize the population loss given i.i.d.~samples from a distribution over convex and Lipschitz loss functions. A long line of existing work on private convex optimization focuses on the empirical loss and derives asymptotically tight bounds on the excess empirical loss. However a significant gap exists in the known bounds for the population loss. We show that, up to logarithmic factors, the optimal excess population loss for DP algorithms is equal to the larger of the optimal non-private excess population loss, and the optimal excess empirical loss of DP algorithms. This implies that, contrary to intuition based on private ERM, private SCO has asymptotically the same rate of $1/\sqrt{n}$ as non-private SCO in the parameter regime most common in practice. The best previous result in this setting gives rate of $1/n^{1/4}$. Our approach builds on existing differentially private algorithms and relies on the analysis of algorithmic stability to ensure generalization.

Subfields: Privacy & Security, Mathematical Optimization

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Privacy & Security

In Mathematical Optimization

Citations in the corpus

Practical and Private (Deep) Learning without Sampling or Shuffling (2021, background): “√ While the results in [7, 8, 29] have a tighter (and optimal) excess population risk of (cid:101) Θ(1 / n + √ p/ ( εn )) , they either require convexity to ensure privacy for a single pass algorithm, or need to make n -passes over the data.”
Privacy Amplification via Random Check-Ins (2020, background): “Thus, we observe that all the bounds recover the optimal population risk trade-offs from [9, 8] as m → n, and for m n and non-smooth loss Afix provides a better trade-off than Aavg , while on smooth losses Aavg and Afix are incomparable.”
Characterizing Private Clipped Gradient Descent on Convex Generalized Linear Problems (2020, unknown): “In fact, it can be used to justify the use of standard private convex optimization analysis in [7, 16, 15, 5] to DP-GD on convex generalized linear problems.”
Stochastic Adaptive Line Search for Differentially Private Optimization (2020, methodology): “The convergence property of private optimization algorithms is shown in [26], [27].”
Stability of Stochastic Gradient Descent on Nonsmooth Convex Losses (2020, methodology): “A recent work of Bassily et al. (2019) established that the optimal rate of the excess population risk for ( α, β ) -DP SCO algorithms is (cid:0) Subsequently, Feldman et al. (2020) gave several new algorithms for DP-SCO with the optimal population risk.”
Private Stochastic Non-Convex Optimization: Adaptive Algorithms and Tighter Generalization Bounds (2020, methodology): “More recently, [15] further reduces the number of gradient computations in the algorithm of [2].”
How to DP-fy ML: A Practical Guide to Machine Learning with Differential Privacy (2023, background): “…one can measure the utility in terms of excess population risk with respect to a fixed distribution τ as follows: RPop(θ) = Ed∼τ [`(θ; d)]−min θ Ed∼τ [`(θ; d)] Bassily et al. (2014, 2019, 2020) show that for (strongly) convex and Lipschitz losses variants of DP-SGD obtain optimal excess…”
Bypassing the Ambient Dimension: Private SGD with Gradient Subspace Identification (2020, methodology): “Given the dimension of gradient to be p, this method ends up in getting a factor of p in the error rate [4, 7].”
Remember What You Want to Forget: Algorithms for Machine Unlearning (2021, methodology): “We set the DP algorithm A as the mini-batch noisy SGD method from Bassily et al. (2019).”
Differentially Private Federated Learning: An Information-Theoretic Perspective (2021, background): “For instance, each iteration of the projected noisy stochastic gradient descent with Gaussian noise (see e.g., [4, 5, 7, 8, 11, 30]) can be viewed as a Gaussian kernel whose input (and output) are values from a compact set.”