Fast Dimension Independent Private AdaGrad on Publicly Estimated Subspaces

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.