# Adapting to Function Difficulty and Growth Conditions in Private Optimization

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

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 49 references that are in the map.
- First posted on arXiv 5 Aug 2021.

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

- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016)
- [Fairness Without Demographics in Repeated Loss Minimization](https://mlsanity.com/paper/1806.08010/) (2018)
- [Private Stochastic Convex Optimization with Optimal Rates](https://mlsanity.com/paper/1908.09970/) (2019)
- [Stability of Stochastic Gradient Descent on Nonsmooth Convex Losses](https://mlsanity.com/paper/2006.06914/) (2020)
- [Private Stochastic Convex Optimization: Optimal Rates in Linear Time](https://mlsanity.com/paper/2005.04763/) (2020)
- [Differentially Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Bounds](https://mlsanity.com/paper/1405.7085/) (2014)
- [A Short Note on Concentration Inequalities for Random Vectors with SubGaussian Norm](https://mlsanity.com/paper/1902.03736/) (2019)
- [High probability generalization bounds for uniformly stable algorithms with nearly optimal rate](https://mlsanity.com/paper/1902.10710/) (2019)
- [Private Stochastic Convex Optimization: Optimal Rates in ℓ1 Geometry](https://mlsanity.com/paper/2103.01516/) (2021)
- [Learning with User-Level Privacy](https://mlsanity.com/paper/2102.11845/) (2021)
- [Communication Lower Bounds for Statistical Estimation Problems via a Distributed Data Processing Inequality](https://mlsanity.com/paper/1506.07216/) (2015)
- [Private Adaptive Gradient Methods for Convex Optimization](https://mlsanity.com/paper/2106.13756/) (2021)
- [From error bounds to the complexity of first-order descent methods for convex functions](https://mlsanity.com/paper/1510.08234/) (2015)
- [Asymptotic Optimality in Stochastic Optimization](https://mlsanity.com/paper/1612.05612/) (2016)
- [On Communication Cost of Distributed Statistical Estimation and Dimensionality](https://mlsanity.com/paper/1405.1665/) (2014)
- [Near Instance-Optimality in Differential Privacy](https://mlsanity.com/paper/2005.10630/) (2020)
- [Primal-dual subgradient methods for minimizing uniformly convex functions](https://mlsanity.com/paper/1401.1792/) (2014)
- [Geometry, Computation, and Optimality in Stochastic Optimization](https://mlsanity.com/paper/1909.10455/) (2019)
- [Local Minimax Complexity of Stochastic Convex Optimization](https://mlsanity.com/paper/1605.07596/) (2016)

## Built on by (most cited first, 20 of 20)

- [(Amplified) Banded Matrix Factorization: A unified approach to private training](https://mlsanity.com/paper/2306.08153/) (2023)
- [Why Is Public Pretraining Necessary for Private Model Training?](https://mlsanity.com/paper/2302.09483/) (2023)
- [Adaptive SGD with Polyak stepsize and Line-search: Robust Convergence and Variance Reduction](https://mlsanity.com/paper/2308.06058/) (2023)
- [Private Online Prediction from Experts: Separations and Faster Rates](https://mlsanity.com/paper/2210.13537/) (2022)
- [Private (Stochastic) Non-Convex Optimization Revisited: Second-Order Stationary Points and Excess Risks](https://mlsanity.com/paper/2302.09699/) (2023)
- [User-level Differentially Private Stochastic Convex Optimization: Efficient Algorithms with Optimal Rates](https://mlsanity.com/paper/2311.03797/) (2023)
- [Differentially Private Stochastic Convex Optimization in (Non)-Euclidean Space Revisited](https://mlsanity.com/paper/2303.18047/) (2023)
- [Private Stochastic Convex Optimization with Heavy Tails: Near-Optimality from Simple Reductions](https://mlsanity.com/paper/2406.02789/) (2024)
- [On Design Principles for Private Adaptive Optimizers](https://mlsanity.com/paper/2507.01129/) (2025)
- [Improved Analysis of Sparse Linear Regression in Local Differential Privacy Model](https://mlsanity.com/paper/2310.07367/) (2023)
- [Differentially Private Non-Convex Optimization under the KL Condition with Optimal Rates](https://mlsanity.com/paper/2311.13447/) (2023)
- [Differentially Private Sampling from Rashomon Sets, and the Universality of Langevin Diffusion for Convex Optimization](https://mlsanity.com/paper/2204.01585/) (2022)
- [Private optimization in the interpolation regime: faster rates and hardness results](https://mlsanity.com/paper/2210.17070/) (2022)
- [Private Online Learning via Lazy Algorithms](https://mlsanity.com/paper/2406.03620/) (2024)
- [Differentially Private Optimization with Sparse Gradients](https://mlsanity.com/paper/2404.10881/) (2024)
- [Beyond Ordinary Lipschitz Constraints: Differentially Private Stochastic Optimization with Tsybakov Noise Condition](https://mlsanity.com/paper/2509.04668/) (2025)
- [Optimal Rates for O(1)-Smooth DP-SCO with a Single Epoch and Large Batches](https://mlsanity.com/paper/2406.02716/) (2024)
- [Optimal Rates for Pure varepsilon-Differentially Private Stochastic Convex Optimization with Heavy Tails](https://mlsanity.com/paper/2604.06492/) (2026)
- [Near-Optimal Machine Unlearning Utility for Smooth Strongly Convex Losses](https://mlsanity.com/paper/2606.01527/) (2026)
- [An Accuracy-Information Tradeoff for Loss-Difference Conditional Mutual Information](https://mlsanity.com/paper/2610.09206/) (2026)

## Abstract (arXiv)

We develop algorithms for private stochastic convex optimization that adapt to the hardness of the specific function we wish to optimize. While previous work provide worst-case bounds for arbitrary convex functions, it is often the case that the function at hand belongs to a smaller class that enjoys faster rates. Concretely, we show that for functions exhibiting kappa-growth around the optimum, i.e., f(x) ≥ f(x^*) + λ kappa-1 |x-x^*|2^kappa for kappa > 1, our algorithms improve upon the standard √d/nvarepsilon privacy rate to the faster (√d/nvarepsilon)^tfrackappakappa - 1. Crucially, they achieve these rates without knowledge of the growth constant kappa of the function. Our algorithms build upon the inverse sensitivity mechanism, which adapts to instance difficulty (Asi & Duchi, 2020), and recent localization techniques in private optimization (Feldman et al., 2020). We complement our algorithms with matching lower bounds for these function classes and demonstrate that our adaptive algorithm is simultaneously (minimax) optimal over all kappa ≥ 1+c whenever c = Theta(1).