2020

Stochastic Adaptive Line Search for Differentially Private Optimization

Chen, Chen, Lee, Jaewoo

Understand

The performance of private gradient-based optimization algorithms is highly dependent on the choice of step size (or learning rate) which often requires non-trivial amount of tuning.

In this paper, we introduce a stochastic variant of classic backtracking line search algorithm that satisfies R\'enyi differential privacy.
Specifically, the proposed algorithm adaptively chooses the step size satsisfying the the Armijo condition (with high probability) using noisy gradients and function estimates.
Furthermore, to improve the probability with which the chosen step size satisfies the condition, it adjusts per-iteration privacy budget during runtime according to the reliability of noisy gradient.

Built on

Minimization of functions having lipschitz continuous first partial derivatives
Larry Armijo · 1966
Earlier work this paper cites.
Convex optimization
Stephen Boyd and Lieven Vandenberghe · 2004
Earlier work this paper cites.
Calibrating noise to sensitivity in private data analysis
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith · 2006
Earlier work this paper cites.
Our data, ourselves: Privacy via distributed noise generation
Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor · 2006
Earlier work this paper cites.
Differentially private empirical risk minimization
Kamalika Chaudhuri, Claire Monteleoni, and Anand D Sarwate · 2011
Earlier work this paper cites.
Libsvm: A library for support vector machines
Chih-Chung Chang and Chih-Jen Lin · 2011
Earlier work this paper cites.
Private convex empirical risk minimization and high-dimensional regression
Daniel Kifer, Adam Smith, and Abhradeep Thakurta · 2012
Earlier work this paper cites.
Accelerating stochastic gradient descent using predictive variance reduction
Rie Johnson and Tong Zhang · 2013
Earlier work this paper cites.
Privgene: differentially private model fitting using genetic algorithms
Jun Zhang, Xiaokui Xiao, Yin Yang, Zhenjie Zhang, and Marianne Winslett · 2013
Earlier work this paper cites.
The algorithmic foundations of differential privacy
Cynthia Dwork, Aaron Roth, et al · 2014
Earlier work this paper cites.

Similar

Private empirical risk minimization: Efficient algorithms and tight error bounds
Raef Bassily, Adam Smith, and Abhradeep Thakurta · 2014
Cited alongside, same era.
Adam: A method for stochastic optimization
Original
Diederik P Kingma and Jimmy Ba · 2014
Cited alongside, same era.
Integrated public use microdata series: Version 6.0 [dataset]
Steven Ruggles, Katie Genadek, Ronald Goeken, Josiah Grover, and Matthew Sobek · 2015
Cited alongside, same era.
Deep learning with differential privacy
Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang · 2016
Cited alongside, same era.
Understanding the sparse vector technique for differential privacy
Original
Min Lyu, Dong Su, and Ninghui Li · 2016
Cited alongside, same era.
Concentrated differential privacy: Simplifications, extensions, and lower bounds
Mark Bun and Thomas Steinke · 2016
Cited alongside, same era.
Rényi differential privacy
Ilya Mironov · 2017
Cited alongside, same era.
Efficient private erm for smooth objectives
Original
Jiaqi Zhang, Kai Zheng, Wenlong Mou, and Liwei Wang · 2017
Cited alongside, same era.
Bolt-on differential privacy for scalable stochastic gradient descent-based analytics
Xi Wu, Fengan Li, Arun Kumar, Kamalika Chaudhuri, Somesh Jha, and Jeffrey Naughton · 2017
Cited alongside, same era.

Then

Differentially private empirical risk minimization revisited: Faster and more general
Di Wang, Minwei Ye, and Jinhui Xu · 2017
Later among the works it cites.
UCI machine learning repository, 2017
Dheeru Dua and Casey Graff · 2017
Later among the works it cites.
Concentrated differentially private gradient descent with adaptive per-iteration privacy budget
Jaewoo Lee and Daniel Kifer · 2018
Later among the works it cites.
Detecting violations of differential privacy
Zeyu Ding, Yuxin Wang, Guanhong Wang, Danfeng Zhang, and Daniel Kifer · 2018
Later among the works it cites.
Learning rate adaptation for differentially private stochastic gradient descent
Original
Antti Koskela and Antti Honkela · 2018
Later among the works it cites.
Painless stochastic gradient: Interpolation, line-search, and convergence rates
Sharan Vaswani, Aaron Mishkin, Issam Laradji, Mark Schmidt, Gauthier Gidel, and Simon Lacoste-Julien · 2019
Later among the works it cites.
Poission subsampled rényi differential privacy
Yuqing Zhu and Yu-Xiang Wang · 2019
Later among the works it cites.
Robust learning rate selection for stochastic optimization via splitting diagnostic
Original
Matteo Sordello and Weijie Su · 2019
Later among the works it cites.
Renyi differentially private erm for smooth objectives
Chen Chen, Jaewoo Lee, and Dan Kifer · 2019
Later among the works it cites.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…