Private stochastic convex optimization: optimal rates in linear time

By Vitaly Feldman, Tomer Koren, Kunal Talwar. 2020

230 citations recorded by the source corpus.

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 optimal algorithm for the strongly convex case, as well as a faster algorithm for the non-smooth case.

Subfields: Artificial Intelligence

How researchers see this paper

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

In Artificial Intelligence

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.”
Stochastic Adaptive Line Search for Differentially Private Optimization (2020, methodology): “The convergence property of private optimization algorithms is shown in [26], [27].”
FedBoost: Communication-Efficient Algorithms for Federated Learning (2020, unknown): “Furthermore, this learning problem is typically a convex optimization problem for which DP convex optimization can give better privacy guarantees (Feldman et al., 2019).”
Unlocking High-Accuracy Differentially Private Image Classification through Scale (2022, background): “…analysis of the privacy-utility oﬀered by these algorithms, and by now there are large classes of problems for which algorithms achieving (nearly) optimal privacy-utility trade-oﬀs are known (Asi et al., 2021; Bassily et al., 2014; Feldman et al., 2020; Song et al., 2021; Talwar et al., 2015).”
Adversary Instantiation: Lower Bounds for Differentially Private Machine Learning (2021, background): “Theoretical work producing upper bounds of privacy is extensive [7, 4, 51, 1, 38, 55, 25, 47, 20, 21, 1, 4, 51, 40].”
Stability of Stochastic Gradient Descent on Nonsmooth Convex Losses (2020, methodology): “Our algorithm is simpler and more efficient than the best known algorithm for the nonsmooth case [16].”
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.”
Private Stochastic Non-Convex Optimization: Adaptive Algorithms and Tighter Generalization Bounds (2020, background): “[15] Vitaly Feldman, Tomer Koren, and Kunal Talwar.”