# Private Stochastic Convex Optimization: Optimal Rates in ℓ1 Geometry

arXiv: https://arxiv.org/abs/2103.01516 · HTML: https://mlsanity.com/paper/2103.01516/

## Key facts

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

## Builds on (most cited first, 10 of 10)

- [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016)
- [Train faster, generalize better: Stability of stochastic gradient descent](https://mlsanity.com/paper/1509.01240/) (2015)
- [SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator](https://mlsanity.com/paper/1807.01695/) (2018)
- [Private Stochastic Convex Optimization with Optimal Rates](https://mlsanity.com/paper/1908.09970/) (2019)
- [Private Stochastic Convex Optimization: Optimal Rates in Linear Time](https://mlsanity.com/paper/2005.04763/) (2020)
- [Relatively-Smooth Convex Optimization by First-Order Methods, and Applications](https://mlsanity.com/paper/1610.05708/) (2016)
- [Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy Amplification by Shuffling](https://mlsanity.com/paper/2012.12803/) (2020)
- [Between Pure and Approximate Differential Privacy](https://mlsanity.com/paper/1501.06095/) (2015)
- [Non-Euclidean Differentially Private Stochastic Convex Optimization: Optimal Rates in Linear Time](https://mlsanity.com/paper/2103.01278/) (2021)
- [Generalization of ERM in Stochastic Convex Optimization: The Dimension Strikes Back](https://mlsanity.com/paper/1608.04414/) (2016)

## Built on by (most cited first, 30 of 83)

- [Unlocking High-Accuracy Differentially Private Image Classification through Scale](https://mlsanity.com/paper/2204.13650/) (2022)
- [Private Convex Optimization via Exponential Mechanism](https://mlsanity.com/paper/2203.00263/) (2022)
- [When Does Differentially Private Learning Not Suffer in High Dimensions?](https://mlsanity.com/paper/2207.00160/) (2022)
- [Improved Rates for Differentially Private Stochastic Convex Optimization with Heavy-Tailed Data](https://mlsanity.com/paper/2106.01336/) (2021)
- [Private Adaptive Gradient Methods for Convex Optimization](https://mlsanity.com/paper/2106.13756/) (2021)
- [Differentially Private Stochastic Optimization: New Results in Convex and Non-Convex Settings](https://mlsanity.com/paper/2107.05585/) (2021)
- [High Dimensional Differentially Private Stochastic Optimization with Heavy-tailed Data](https://mlsanity.com/paper/2107.11136/) (2021)
- [Faster Rates of Convergence to Stationary Points in Differentially Private Optimization](https://mlsanity.com/paper/2206.00846/) (2022)
- [Private Federated Learning Without a Trusted Server: Optimal Algorithms for Convex Losses](https://mlsanity.com/paper/2106.09779/) (2021)
- [DPZero: Private Fine-Tuning of Language Models without Backpropagation](https://mlsanity.com/paper/2310.09639/) (2023)
- [Stochastic Bias-Reduced Gradient Methods](https://mlsanity.com/paper/2106.09481/) (2021)
- [Constant matters: Fine-grained Complexity of Differentially Private Continual Observation](https://mlsanity.com/paper/2202.11205/) (2022)
- [Bring Your Own Algorithm for Optimal Differentially Private Stochastic Minimax Optimization](https://mlsanity.com/paper/2206.00363/) (2022)
- [Private Non-smooth Empirical Risk Minimization and Stochastic Convex Optimization in Subquadratic Steps](https://mlsanity.com/paper/2103.15352/) (2021)
- [Adapting to Function Difficulty and Growth Conditions in Private Optimization](https://mlsanity.com/paper/2108.02391/) (2021)
- [Beyond Uniform Lipschitz Condition in Differentially Private Optimization](https://mlsanity.com/paper/2206.10713/) (2022)
- [Optimal Algorithms for Differentially Private Stochastic Monotone Variational Inequalities and Saddle-Point Problems](https://mlsanity.com/paper/2104.02988/) (2021)
- [Private Online Prediction from Experts: Separations and Faster Rates](https://mlsanity.com/paper/2210.13537/) (2022)
- [ReSQueing Parallel and Private Stochastic Convex Optimization](https://mlsanity.com/paper/2301.00457/) (2023)
- [Stochastic Differentially Private and Fair Learning](https://mlsanity.com/paper/2210.08781/) (2022)
- [Private Convex Optimization in General Norms](https://mlsanity.com/paper/2207.08347/) (2022)
- [Private (Stochastic) Non-Convex Optimization Revisited: Second-Order Stationary Points and Excess Risks](https://mlsanity.com/paper/2302.09699/) (2023)
- [Differentially Private Algorithms for the Stochastic Saddle Point Problem with Optimal Rates for the Strong Gap](https://mlsanity.com/paper/2302.12909/) (2023)
- [User-level Differentially Private Stochastic Convex Optimization: Efficient Algorithms with Optimal Rates](https://mlsanity.com/paper/2311.03797/) (2023)
- [Taming Nonconvex Stochastic Mirror Descent with General Bregman Divergence](https://mlsanity.com/paper/2402.17722/) (2024)
- [A Huber Loss Minimization Approach to Mean Estimation under User-level Differential Privacy](https://mlsanity.com/paper/2405.13453/) (2024)
- [Differentially Private Coordinate Descent for Composite Empirical Risk Minimization](https://mlsanity.com/paper/2110.11688/) (2021)
- [DIFF2: Differential Private Optimization via Gradient Differences for Nonconvex Distributed Learning](https://mlsanity.com/paper/2302.03884/) (2023)
- [Algorithmic Aspects of the Log-Laplace Transform and a Non-Euclidean Proximal Sampler](https://mlsanity.com/paper/2302.06085/) (2023)
- [Initialization Matters: Privacy-Utility Analysis of Overparameterized Neural Networks](https://mlsanity.com/paper/2310.20579/) (2023)

## 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.