# Fast Dimension Independent Private AdaGrad on Publicly Estimated Subspaces

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Aug 2020.

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

- [A Field Guide to Federated Optimization](https://mlsanity.com/paper/2107.06917/) (2021)
- [Large Scale Private Learning via Low-rank Reparametrization](https://mlsanity.com/paper/2106.09352/) (2021)
- [Do Not Let Privacy Overbill Utility: Gradient Embedding Perturbation for Private Learning](https://mlsanity.com/paper/2102.12677/) (2021)
- [Public Data-Assisted Mirror Descent for Private Model Training](https://mlsanity.com/paper/2112.00193/) (2021)
- [Private Adaptive Gradient Methods for Convex Optimization](https://mlsanity.com/paper/2106.13756/) (2021)
- [PrE-Text: Training Language Models on Private Federated Data in the Age of LLMs](https://mlsanity.com/paper/2406.02958/) (2024)
- [Choosing Public Datasets for Private Machine Learning via Gradient Subspace Distance](https://mlsanity.com/paper/2303.01256/) (2023)
- [Stability Based Generalization Bounds for Exponential Family Langevin Dynamics](https://mlsanity.com/paper/2201.03064/) (2022)
- [The Power of Sampling: Dimension-free Risk Bounds in Private ERM](https://mlsanity.com/paper/2105.13637/) (2021)
- [On Differentially Private Subspace Estimation in a Distribution-Free Setting](https://mlsanity.com/paper/2402.06465/) (2024)

## Abstract (arXiv)

We revisit the problem of empirical risk minimziation (ERM) with differential privacy. We show that noisy AdaGrad, given appropriate knowledge and conditions on the subspace from which gradients can be drawn, achieves a regret comparable to traditional AdaGrad plus a well-controlled term due to noise. We show a convergence rate of O(Tr(GT)/T), where GT captures the geometry of the gradient subspace. Since Tr(GT)=O(√T) we can obtain faster rates for convex and Lipschitz functions, compared to the O(1/√T) rate achieved by known versions of noisy (stochastic) gradient descent with comparable noise variance. In particular, we show that if the gradients lie in a known constant rank subspace, and assuming algorithmic access to an envelope which bounds decaying sensitivity, one can achieve faster convergence to an excess empirical risk of tilde O(1/ε n), where ε is the privacy budget and n the number of samples. Letting p be the problem dimension, this result implies that, by running noisy Adagrad, we can bypass the DP-SGD bound tilde O(√p/ε n) in T=(ε n)2/(1+2α) iterations, where α ≥ 0 is a parameter controlling gradient norm decay, instead of the rate achieved by SGD of T=ε2n2. Our results operate with general convex functions in both constrained and unconstrained minimization. Along the way, we do a perturbation analysis of noisy AdaGrad of independent interest. Our utility guarantee for the private ERM problem follows as a corollary to the regret guarantee of noisy AdaGrad.