Private Stochastic Non-Convex Optimization: Adaptive Algorithms and Tighter Generalization Bounds

Abstract

We study differentially private (DP) algorithms for stochastic non-convex optimization. In this problem, the goal is to minimize the population loss over a $p$-dimensional space given $n$ i.i.d. samples drawn from a distribution. We improve upon the population gradient bound of $\sqrt{p}/\sqrt{n}$ from prior work and obtain a sharper rate of $\sqrt[4]{p}/\sqrt{n}$. We obtain this rate by providing the first analyses on a collection of private gradient-based methods, including adaptive algorithms DP RMSProp and DP Adam. Our proof technique leverages the connection between differential privacy and adaptive data analysis to bound gradient estimation error at every iterate, which circumvents the worse generalization bound from the standard uniform convergence argument. Finally, we evaluate the proposed algorithms on two popular deep learning tasks and demonstrate the empirical advantages of DP adaptive gradient methods over standard DP SGD.

In the current version, we drop the experimental results on CIFAR-10 dataset due to an implementation error

References in corpus (10)

• Adam: A Method for Stochastic Optimization
• Deep Learning with Differential Privacy
• On the Convergence of Adam and Beyond
• AdaGrad stepsizes: Sharp convergence over nonconvex landscapes
• Generalization in Adaptive Data Analysis and Holdout Reuse
• Subsampled Rényi Differential Privacy and Analytical Moments Accountant
• The Landscape of Empirical Risk for Non-convex Losses
• Differentially Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Bounds
• Deep Learning with Gaussian Differential Privacy
• Efficient Privacy-Preserving Stochastic Nonconvex Optimization

Cited by in corpus (4)

• Differentially Private Learning Needs Better Features (or Much More Data)
• Fast Dimension Independent Private AdaGrad on Publicly Estimated Subspaces
• Differentially Private Stochastic Optimization: New Results in Convex and Non-Convex Settings
• Adaptive Differentially Private Empirical Risk Minimization