# Private Adaptive Gradient Methods for Convex Optimization arXiv: https://arxiv.org/abs/2106.13756 · HTML: https://mlsanity.com/paper/2106.13756/ ## Key facts - Cited by 46 papers in the map (data through 14 Oct 2026). - Builds on 13 of its 34 references that are in the map. - First posted on arXiv 25 Jun 2021. ## Builds on (most cited first, 13 of 13) - [Pointer Sentinel Mixture Models](https://mlsanity.com/paper/1609.07843/) (2016) - [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016) - [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) - [Differentially Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Bounds](https://mlsanity.com/paper/1405.7085/) (2014) - [Minimax Optimal Procedures for Locally Private Estimation](https://mlsanity.com/paper/1604.02390/) (2016) - [Bypassing the Ambient Dimension: Private SGD with Gradient Subspace Identification](https://mlsanity.com/paper/2007.03813/) (2020) - [Do Not Let Privacy Overbill Utility: Gradient Embedding Perturbation for Private Learning](https://mlsanity.com/paper/2102.12677/) (2021) - [Private Stochastic Convex Optimization: Optimal Rates in ℓ1 Geometry](https://mlsanity.com/paper/2103.01516/) (2021) - [AdaCliP: Adaptive Clipping for Private SGD](https://mlsanity.com/paper/1908.07643/) (2019) - [Stochastic (Approximate) Proximal Point Methods: Convergence, Optimality, and Adaptivity](https://mlsanity.com/paper/1810.05633/) (2018) - [Geometry, Computation, and Optimality in Stochastic Optimization](https://mlsanity.com/paper/1909.10455/) (2019) - [Fast Dimension Independent Private AdaGrad on Publicly Estimated Subspaces](https://mlsanity.com/paper/2008.06570/) (2020) ## Built on by (most cited first, 30 of 46) - [Large Language Models Can Be Strong Differentially Private Learners](https://mlsanity.com/paper/2110.05679/) (2021) - [How to DP-fy ML: A Practical Guide to Machine Learning with Differential Privacy](https://mlsanity.com/paper/2303.00654/) (2023) - [Exploring the Limits of Differentially Private Deep Learning with Group-wise Clipping](https://mlsanity.com/paper/2212.01539/) (2022) - [Public Data-Assisted Mirror Descent for Private Model Training](https://mlsanity.com/paper/2112.00193/) (2021) - [Differentially Private Learning Needs Hidden State (Or Much Faster Convergence)](https://mlsanity.com/paper/2203.05363/) (2022) - [When Does Differentially Private Learning Not Suffer in High Dimensions?](https://mlsanity.com/paper/2207.00160/) (2022) - [Large Scale Transfer Learning for Differentially Private Image Classification](https://mlsanity.com/paper/2205.02973/) (2022) - [Private Adaptive Optimization with Side Information](https://mlsanity.com/paper/2202.05963/) (2022) - [Why Is Public Pretraining Necessary for Private Model Training?](https://mlsanity.com/paper/2302.09483/) (2023) - [Normalized/Clipped SGD with Perturbation for Differentially Private Non-Convex Optimization](https://mlsanity.com/paper/2206.13033/) (2022) - [FLAIR: Federated Learning Annotated Image Repository](https://mlsanity.com/paper/2207.08869/) (2022) - [Differentially Private Learning with Per-Sample Adaptive Clipping](https://mlsanity.com/paper/2212.00328/) (2022) - [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) - [Differentially Private Adaptive Optimization with Delayed Preconditioners](https://mlsanity.com/paper/2212.00309/) (2022) - [Private Online Prediction from Experts: Separations and Faster Rates](https://mlsanity.com/paper/2210.13537/) (2022) - [Fast Optimal Locally Private Mean Estimation via Random Projections](https://mlsanity.com/paper/2306.04444/) (2023) - [Faster Rates of Private Stochastic Convex Optimization](https://mlsanity.com/paper/2108.00331/) (2021) - [Differentially private Riemannian optimization](https://mlsanity.com/paper/2205.09494/) (2022) - [User-level Differentially Private Stochastic Convex Optimization: Efficient Algorithms with Optimal Rates](https://mlsanity.com/paper/2311.03797/) (2023) - [Momentum Aggregation for Private Non-convex ERM](https://mlsanity.com/paper/2210.06328/) (2022) - [PILLAR: How to make semi-private learning more effective](https://mlsanity.com/paper/2306.03962/) (2023) - [Stability Based Generalization Bounds for Exponential Family Langevin Dynamics](https://mlsanity.com/paper/2201.03064/) (2022) - [Differentially Private ℓ1-norm Linear Regression with Heavy-tailed Data](https://mlsanity.com/paper/2201.03204/) (2022) - [Mixed Federated Learning: Joint Decentralized and Centralized Learning](https://mlsanity.com/paper/2205.13655/) (2022) - [Spectral-DP: Differentially Private Deep Learning through Spectral Perturbation and Filtering](https://mlsanity.com/paper/2307.13231/) (2023) - [Private Stochastic Convex Optimization with Heavy Tails: Near-Optimality from Simple Reductions](https://mlsanity.com/paper/2406.02789/) (2024) - [Differentially Private Online-to-Batch for Smooth Losses](https://mlsanity.com/paper/2210.06593/) (2022) - [Delving into Differentially Private Transformer](https://mlsanity.com/paper/2405.18194/) (2024) - [Differentially Private Deep Learning with ModelMix](https://mlsanity.com/paper/2210.03843/) (2022) ## Abstract (arXiv) We study adaptive methods for differentially private convex optimization, proposing and analyzing differentially private variants of a Stochastic Gradient Descent (SGD) algorithm with adaptive stepsizes, as well as the AdaGrad algorithm. We provide upper bounds on the regret of both algorithms and show that the bounds are (worst-case) optimal. As a consequence of our development, we show that our private versions of AdaGrad outperform adaptive SGD, which in turn outperforms traditional SGD in scenarios with non-isotropic gradients where (non-private) Adagrad provably outperforms SGD. The major challenge is that the isotropic noise typically added for privacy dominates the signal in gradient geometry for high-dimensional problems; approaches to this that effectively optimize over lower-dimensional subspaces simply ignore the actual problems that varying gradient geometries introduce. In contrast, we study non-isotropic clipping and noise addition, developing a principled theoretical approach; the consequent procedures also enjoy significantly stronger empirical performance than prior approaches.