Fast Dimension Independent Private AdaGrad on Publicly Estimated Subspaces

Abstract

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(\text{Tr}(G_T)/T)$, where $G_T$ captures the geometry of the gradient subspace. Since $\text{Tr}(G_T)=O(\sqrt{T})$ we can obtain faster rates for convex and Lipschitz functions, compared to the $O(1/\sqrt{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/\epsilon n)$, where $\epsilon$ 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}(\sqrt{p}/\epsilon n)$ in $T=(\epsilon n{)}^{2/(1+2\alpha )}$ iterations, where $\alpha \ge 0$ is a parameter controlling gradient norm decay, instead of the rate achieved by SGD of $T={\epsilon }^2{n}^2$. 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.

References in corpus (14)

• Deep Learning with Differential Privacy
• Renyi Differential Privacy
• Learning Differentially Private Recurrent Language Models
• Adaptive Bound Optimization for Online Convex Optimization
• The Power of Interpolation: Understanding the Effectiveness of SGD in Modern Over-parametrized Learning
• Gradient Descent Happens in a Tiny Subspace
• Differentially Private Learning with Adaptive Clipping
• Private Stochastic Convex Optimization with Optimal Rates
• AdaCliP: Adaptive Clipping for Private SGD
• Less Regret via Online Conditioning
• Efficient Full-Matrix Adaptive Regularization
• Private Stochastic Non-Convex Optimization: Adaptive Algorithms and Tighter Generalization Bounds
• Evading Curse of Dimensionality in Unconstrained Private GLMs via Private Gradient Descent
• A Framework for Private Matrix Analysis

Cited by in corpus (7)

• A Field Guide to Federated Optimization
• Large Language Models Can Be Strong Differentially Private Learners
• Differentially Private Learning Needs Better Features (or Much More Data)
• Bypassing the Ambient Dimension: Private SGD with Gradient Subspace Identification
• Large Scale Private Learning via Low-rank Reparametrization
• Evading Curse of Dimensionality in Unconstrained Private GLMs via Private Gradient Descent
• Privately Learning Subspaces