Dimension Independence in Unconstrained Private ERM via Adaptive Preconditioning

By Peter Kairouz, Mónica Ribero, Keith Rush, Abhradeep Thakurta. 2020

14 citations recorded by the source corpus.

In this paper we revisit the problem of private empirical risk minimziation (ERM) with differential privacy. We show that for unconstrained convex empirical risk minimization if the observed gradients of the objective function along the path of private gradient descent lie in a low-dimensional subspace (smaller than the ambient dimensionality of $p$), then using noisy adaptive preconditioning (a.k.a., noisy Adaptive Gradient Descent (AdaGrad)) we obtain a regret composed of two terms: a constant multiplicative factor of the original AdaGrad regret and an additional regret due to noise. In particular, we show that if the gradients lie in a constant rank subspace, then one can achieve an excess empirical risk of $ \tilde{O}(1/\epsilon n)$, compared to the worst-case achievable bound of $\tilde{O}(\sqrt{p}/\epsilon n)$. While previous works show dimension independent excess empirical risk bounds for the restrictive setting of convex generalized linear problems optimized over unconstrained subspaces, our results operate with general convex functions in unconstrained minimization. Along the way, we do a perturbation analysis of noisy AdaGrad, which may be of independent interest.

Subfields: Artificial Intelligence, Statistics and Probability

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Dan Boneh
2. Florian Tramèr
3. Brent Waters
4. Allison Bishop
5. Xavier Boyen
6. Craig Gentry
7. Dawn Song
8. Amit Sahai

In Statistics and Probability

1. Dan Boneh
2. Florian Tramèr

Citations in the corpus

• Differentially Private Learning Needs Better Features (or Much More Data) (2020, background): “…circumvent this worst-case dimensionality dependence by leveraging the empirical observation that model gradients lie in a low-dimensional subspace (Kairouz et al., 2020; Zhou et al., 2020b). satisfies (ε, δ)-differential privacy (Dwork et al., 2006a), if for any datasets D,D′ that differ in one…”