Differentially Private Accelerated Optimization Algorithms
arXiv:2008.01989 · doi:10.1137/20M1355847
Abstract
We present two classes of differentially private optimization algorithms derived from the well-known accelerated first-order methods. The first algorithm is inspired by Polyak's heavy ball method and employs a smoothing approach to decrease the accumulated noise on the gradient steps required for differential privacy. The second class of algorithms are based on Nesterov's accelerated gradient method and its recent multi-stage variant. We propose a noise dividing mechanism for the iterations of Nesterov's method in order to improve the error behavior of the algorithm. The convergence rate analyses are provided for both the heavy ball and the Nesterov's accelerated gradient method with the help of the dynamical system analysis techniques. Finally, we conclude with our numerical experiments showing that the presented algorithms have advantages over the well-known differentially private algorithms.
arXiv comment28 pages, 4 figures
References in corpus (12)
- Deep Learning with Differential Privacy
- Renyi Differential Privacy
- Analysis and Design of Optimization Algorithms via Integral Quadratic Constraints
- Privacy Amplification by Subsampling: Tight Analyses via Couplings and Divergences
- Unified Convergence Analysis of Stochastic Momentum Methods for Convex and Non-convex Optimization
- From Averaging to Acceleration, There is Only a Step-size
- AdaCliP: Adaptive Clipping for Private SGD
- Adaptive restart of accelerated gradient methods under local quadratic growth condition
- Efficient Private ERM for Smooth Objectives
- On the Generalization of Stochastic Gradient Descent with Momentum
- Evading Curse of Dimensionality in Unconstrained Private GLMs via Private Gradient Descent
- An Empirical Study on the Intrinsic Privacy of SGD