2019

Private Stochastic Convex Optimization with Optimal Rates

Bassily, Raef, Feldman, Vitaly, Talwar, Kunal et al.

Understand

We study differentially private (DP) algorithms for stochastic convex optimization (SCO).

In this problem the goal is to approximately minimize the population loss given i.i.d.
samples from a distribution over convex and Lipschitz loss functions.
A long line of existing work on private convex optimization focuses on the empirical loss and derives asymptotically tight bounds on the excess empirical loss.

Built on

Stability and generalization
Olivier Bousquet and André Elisseeff · 2002
Earlier work this paper cites.
Smooth minimization of non-smooth functions
Yu Nesterov · 2005
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.
Calibrating noise to sensitivity in private data analysis
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith · 2006
Earlier work this paper cites.
Privacy-preserving logistic regression
Kamalika Chaudhuri and Claire Monteleoni · 2008
Earlier work this paper cites.
Stochastic Convex Optimization
Shai Shalev-Shwartz, Ohad Shamir, Nathan Srebro, and Karthik Sridharan · 2009
Earlier work this paper cites.
The effect of deterministic noise in subgradient methods
Angelia Nedić and Dimitri P Bertsekas · 2010
Earlier work this paper cites.
Mathematical optimization
Emmanuel Candes · 2011
Earlier work this paper cites.
Differentially private empirical risk minimization
Kamalika Chaudhuri, Claire Monteleoni, and Anand D Sarwate · 2011
Earlier work this paper cites.
Differentially private online learning
Prateek Jain, Pravesh Kothari, and Abhradeep Thakurta · 2012
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.
Local privacy and statistical minimax rates
John C. Duchi, Michael I. Jordan, and Martin J. Wainwright · 2013
Earlier work this paper cites.

Similar

Accelerating stochastic gradient descent using predictive variance reduction
Rie Johnson and Tong Zhang · 2013
Cited alongside, same era.
Stochastic gradient descent with differentially private updates
Shuang Song, Kamalika Chaudhuri, and Anand D Sarwate · 2013
Cited alongside, same era.
Differentially private feature selection via stability arguments, and the robustness of the LASSO
Adam Smith and Abhradeep Thakurta · 2013
Cited alongside, same era.
Differentially private empirical risk minimization: Efficient algorithms and tight error bounds
Original
Raef Bassily, Adam Smith, and Abhradeep Thakurta · 2014
Cited alongside, same era.
The algorithmic foundations of differential privacy
Cynthia Dwork and Aaron Roth · 2014
Cited alongside, same era.
The algorithmic foundations of differential privacy
Cynthia Dwork, Aaron Roth, et al · 2014
Cited alongside, same era.
(near) dimension independent risk bounds for differentially private learning
Prateek Jain and Abhradeep Thakurta · 2014
Cited alongside, same era.
Understanding machine learning: From theory to algorithms
Shai Shalev-Shwartz and Shai Ben-David · 2014
Cited alongside, same era.
A proximal stochastic gradient method with progressive variance reduction
Lin Xiao and Tong Zhang · 2014
Cited alongside, same era.
Convex optimization: Algorithms and complexity
Sébastien Bubeck · 2015
Cited alongside, same era.
Preserving statistical validity in adaptive data analysis
Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Aaron Leon Roth · 2015
Cited alongside, same era.
Train faster, generalize better: Stability of stochastic gradient descent
Original
Moritz Hardt, Benjamin Recht, and Yoram Singer · 2015
Cited alongside, same era.

Then

Nearly optimal private LASSO
Kunal Talwar, Abhradeep Thakurta, and Li Zhang · 2015
Later among the works it cites.
Private multiplicative weights beyond linear queries
Jonathan Ullman · 2015
Later among the works it cites.
Deep learning with differential privacy
Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang · 2016
Later among the works it cites.
Algorithmic stability for adaptive data analysis
Raef Bassily, Kobbi Nissim, Adam Smith, Thomas Steinke, Uri Stemmer, and Jonathan Ullman · 2016
Later among the works it cites.
Generalization of erm in stochastic convex optimization: The dimension strikes back
Vitaly Feldman · 2016
Later among the works it cites.
Statistical query algorithms for mean vector estimation and stochastic convex optimization
Original
Vitaly Feldman, Cristobal Guzman, and Santosh Vempala · 2017
Later among the works it cites.
Is interaction necessary for distributed private learning?
Adam Smith, Abhradeep Thakurta, and Jalaj Upadhyay · 2017
Later among the works it cites.
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
Later among the works it cites.
Differentially private empirical risk minimization revisited: Faster and more general
Di Wang, Minwei Ye, and Jinhui Xu · 2017
Later among the works it cites.
High probability generalization bounds for uniformly stable algorithms with nearly optimal rate
Original
Vitaly Feldman and Jan Vondrak · 2019
Closest in time.
Towards practical differentially private convex optimization
Roger Iyengar, Joseph P Near, Dawn Song, Om Thakkar, Abhradeep Thakurta, and Lun Wang · 2019
Closest in time.

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…