mlsanityData to 7 Oct 2026

Private Stochastic Convex Optimization: Optimal Rates in ℓ1 Geometry

arXiv 2103.01516 ↗First posted 2 Mar 2021cs.LG cs.CR math.OCcited by 83

Not on the map. Why?

Abstract (arXiv)

Stochastic convex optimization over an ℓ1-bounded domain is ubiquitous in machine learning applications such as LASSO but remains poorly understood when learning with differential privacy. We show that, up to logarithmic factors the optimal excess population loss of any (varepsilon,δ)-differentially private optimizer is √log(d)/n + √d/varepsilon n. The upper bound is based on a new algorithm that combines the iterative localization approach of~citetFeldmanKoTa20 with a new analysis of private regularized mirror descent. It applies to ℓp bounded domains for p∈ [1,2] and queries at most n3/2 gradients improving over the best previously known algorithm for the ℓ2 case which needs n2 gradients. Further, we show that when the loss functions satisfy additional smoothness assumptions, the excess loss is upper bounded (up to logarithmic factors) by √log(d)/n + (log(d)/varepsilon n)2/3. This bound is achieved by a new variance-reduced version of the Frank-Wolfe algorithm that requires just a single pass over the data. We also show that the lower bound in this case is the minimum of the two rates mentioned above.

Key facts. Cited by 83 papers in the map (data through 7 Oct 2026). Builds on 10 of its 26 references that are in the map. First posted on arXiv 2 Mar 2021.

Builds on

10 of 26 references.

References · 10

  1. 2016Deep Learning with Differential Privacycited by 2,682
  2. 2015Train faster, generalize better: Stability of stochastic gradient descentcited by 547
  3. 2018SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimatorcited by 283
  4. 2019Private Stochastic Convex Optimization with Optimal Ratescited by 183
  5. 2020Private Stochastic Convex Optimization: Optimal Rates in Linear Timecited by 152
  6. 2016Relatively-Smooth Convex Optimization by First-Order Methods, and Applicationscited by 108
  7. 2020Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy Amplification by Shufflingcited by 96
  8. 2015Between Pure and Approximate Differential Privacycited by 55
  9. 2021Non-Euclidean Differentially Private Stochastic Convex Optimization: Optimal Rates in Linear Timecited by 51
  10. 2016Generalization of ERM in Stochastic Convex Optimization: The Dimension Strikes Backcited by 37

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 12; 2022: 20; 2023: 16; 2024: 18; 2025: 10; 2026: 7.

83 papers.

Sort:

By area:

  1. 2022Unlocking High-Accuracy Differentially Private Image Classification through Scalecited by 218
  2. 2022When Does Differentially Private Learning Not Suffer in High Dimensions?cited by 48
  3. 2021Improved Rates for Differentially Private Stochastic Convex Optimization with Heavy-Tailed Datacited by 47
  4. 2022Private Convex Optimization via Exponential Mechanismcited by 47
  5. 2021Private Adaptive Gradient Methods for Convex Optimizationcited by 46
  6. 2021Differentially Private Stochastic Optimization: New Results in Convex and Non-Convex Settingscited by 45
  7. 2021High Dimensional Differentially Private Stochastic Optimization with Heavy-tailed Datacited by 42
  8. 2022Faster Rates of Convergence to Stationary Points in Differentially Private Optimizationcited by 32
  9. 2021Private Federated Learning Without a Trusted Server: Optimal Algorithms for Convex Lossescited by 30
  10. 2023DPZero: Private Fine-Tuning of Language Models without Backpropagationcited by 26
  11. 2021Stochastic Bias-Reduced Gradient Methodscited by 25
  12. 2022Constant matters: Fine-grained Complexity of Differentially Private Continual Observationcited by 23
38 more
  1. 2022Bring Your Own Algorithm for Optimal Differentially Private Stochastic Minimax Optimizationcited by 22
  2. 2021Private Non-smooth Empirical Risk Minimization and Stochastic Convex Optimization in Subquadratic Stepscited by 21
  3. 2021Adapting to Function Difficulty and Growth Conditions in Private Optimizationcited by 19
  4. 2022Beyond Uniform Lipschitz Condition in Differentially Private Optimizationcited by 19
  5. 2021Optimal Algorithms for Differentially Private Stochastic Monotone Variational Inequalities and Saddle-Point Problemscited by 17
  6. 2022Private Online Prediction from Experts: Separations and Faster Ratescited by 17
  7. 2023ReSQueing Parallel and Private Stochastic Convex Optimizationcited by 17
  8. 2022Stochastic Differentially Private and Fair Learningcited by 16
  9. 2022Private Convex Optimization in General Normscited by 13
  10. 2023Private (Stochastic) Non-Convex Optimization Revisited: Second-Order Stationary Points and Excess Riskscited by 12
  11. 2023User-level Differentially Private Stochastic Convex Optimization: Efficient Algorithms with Optimal Ratescited by 12
  12. 2023Differentially Private Algorithms for the Stochastic Saddle Point Problem with Optimal Rates for the Strong Gapcited by 11
  13. 2024Taming Nonconvex Stochastic Mirror Descent with General Bregman Divergencecited by 11
  14. 2024A Huber Loss Minimization Approach to Mean Estimation under User-level Differential Privacycited by 11
  15. 2021Differentially Private Coordinate Descent for Composite Empirical Risk Minimizationcited by 10
  16. 2023DIFF2: Differential Private Optimization via Gradient Differences for Nonconvex Distributed Learningcited by 10
  17. 2024How to Make the Gradients Small Privately: Improved Rates for Differentially Private Non-Convex Optimizationcited by 10
  18. 2023Near Optimal Private and Robust Linear Regressioncited by 9
  19. 2023Algorithmic Aspects of the Log-Laplace Transform and a Non-Euclidean Proximal Samplercited by 9
  20. 2023Initialization Matters: Privacy-Utility Analysis of Overparameterized Neural Networkscited by 9
  21. 2022Differentially Private ℓ1-norm Linear Regression with Heavy-tailed Datacited by 8
  22. 2022Uniform Stability for First-Order Empirical Risk Minimizationcited by 8
  23. 2023Differentially Private Stochastic Convex Optimization in (Non)-Euclidean Space Revisitedcited by 8
  24. 2023On User-Level Private Convex Optimizationcited by 8
  25. 2023Scaling Up Differentially Private LASSO Regularized Logistic Regression via Faster Frank-Wolfe Iterationscited by 8
  26. 2024Private Heterogeneous Federated Learning Without a Trusted Server Revisited: Error-Optimal and Communication-Efficient Algorithms for Convex Lossescited by 8
  27. 2022Differentially Private Learning with Margin Guaranteescited by 7
  28. 2024Mirror Descent Algorithms with Nearly Dimension-Independent Rates for Differentially-Private Stochastic Saddle-Point Problemscited by 7
  29. 2024Private Stochastic Convex Optimization with Heavy Tails: Near-Optimality from Simple Reductionscited by 6
  30. 2024Fast Rates for Bandit PAC Multiclass Classificationcited by 6
  31. 2021On the Convergence of Differentially Private Federated Learning on Non-Lipschitz Objectives, and with Normalized Client Updatescited by 5
  32. 2024SoK: A Review of Differentially Private Linear Models For High-Dimensional Datacited by 5
  33. 2022High-Dimensional Private Empirical Risk Minimization by Greedy Coordinate Descentcited by 4
  34. 2023Improved Analysis of Sparse Linear Regression in Local Differential Privacy Modelcited by 4
  35. 2023Differentially Private Non-Convex Optimization under the KL Condition with Optimal Ratescited by 4
  36. 2024Faster Algorithms for User-Level Private Stochastic Convex Optimizationcited by 4
  37. 2025Towards Understanding Generalization in DP-GD: A Case Study in Training Two-Layer CNNscited by 4
  38. 2021The Power of Sampling: Dimension-free Risk Bounds in Private ERMcited by 3

50 most cited of 83 All 83 (JSON)