Private Learning Implies Online Learning: An Efficient Reduction
We study the relationship between the notions of differentially private learning and online learning in games. Several recent works have shown that differentially private learning implies online learning, but an open problem of Neel, Roth, and Wu \cite{NeelAaronRoth2018} asks whether this implication is {\it efficient}. Specifically, does an efficient differentially private learner imply an efficient online learner? In this paper we resolve this open question in the context of pure differential privacy. We derive an efficient black-box reduction from differentially private learning to online learning from expert advice.
Code (0)
등록된 구현이 없습니다.
Tasks
Open-Ended Question AnsweringSimilar Papers 제목 키워드 기반
On the Equivalence between Online and Private Learnability beyond Binary Classification
Alon et al. [2019] and Bun et al. [2020] recently showed that online learnability and private PAC learnability are equivalent in binary classification. We investigate whether this equivalence extends to multi-class class…
Binary ClassificationClassificationGeneral ClassificationMulti-class Classification+1Ramsey Theorems for Trees and a General 'Private Learning Implies Online Learning' Theorem
This work continues to investigate the link between differentially private (DP) and online learning. Alon, Livni, Malliaris, and Moran (2019) showed that for binary concept classes, DP learnability of a given class impli…
General ClassificationPAC learningRobustness Implies Privacy in Statistical Estimation
We study the relationship between adversarial robustness and differential privacy in high-dimensional algorithmic statistics. We give the first black-box reduction from privacy to robustness which can produce private est…
Adversarial Robustnessparameter estimationPrivate learning implies quantum stability
Learning an unknown $n$-qubit quantum state $\rho$ is a fundamental challenge in quantum computing. Information-theoretically, it is known that tomography requires exponential in $n$ many copies of $\rho$ to estimate it …
Learning TheoryPAC learningDifferentially Private Online-to-Batch for Smooth Losses
We develop a new reduction that converts any online convex optimization algorithm suffering $O(\sqrt{T})$ regret into an $\epsilon$-differentially private stochastic convex optimization algorithm with the optimal converg…