PAC learning with stable and private predictions

Yuval Dagan, Vitaly Feldman
Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:1389-1410, 2020.

Abstract

We study binary classification algorithms for which the prediction on any point is not too sensitive to individual examples in the dataset. Specifically, we consider the notions of uniform stability (Bousquet and Elisseeff, 2001) and prediction privacy (Dwork and Feldman, 2018). Previous work on these notions shows how they can be achieved in the standard PAC model via simple aggregation of models trained on disjoint subsets of data. Unfortunately, this approach leads to a significant overhead in terms of sample complexity. Here we demonstrate several general approaches to stable and private prediction that either eliminate or significantly reduce the overhead. Specifically, we demonstrate that for any class $C$ of VC dimension $d$ there exists a $\gamma$-uniformly stable algorithm for learning $C$ with excess error $\alpha$ using $\tilde O(d/(\alpha\gamma) + d/\alpha^2)$ samples. We also show that this bound is nearly tight. For $\eps$-differentially private prediction we give two new algorithms: one using $\tilde O(d/(\alpha^2\eps))$ samples and another one using $\tilde O(d^2/(\alpha\eps) + d/\alpha^2)$ samples. The best previously known bounds for these problems are $O(d/(\alpha^2\gamma))$ and $O(d/(\alpha^3\eps))$, respectively.

Cite this Paper

BibTeX
@InProceedings{pmlr-v125-dagan20a, title = {PAC learning with stable and private predictions}, author = {Dagan, Yuval and Feldman, Vitaly}, booktitle = {Proceedings of Thirty Third Conference on Learning Theory}, pages = {1389--1410}, year = {2020}, editor = {Abernethy, Jacob and Agarwal, Shivani}, volume = {125}, series = {Proceedings of Machine Learning Research}, month = {09--12 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v125/dagan20a/dagan20a.pdf}, url = {https://proceedings.mlr.press/v125/dagan20a.html}, abstract = { We study binary classification algorithms for which the prediction on any point is not too sensitive to individual examples in the dataset. Specifically, we consider the notions of uniform stability (Bousquet and Elisseeff, 2001) and prediction privacy (Dwork and Feldman, 2018). Previous work on these notions shows how they can be achieved in the standard PAC model via simple aggregation of models trained on disjoint subsets of data. Unfortunately, this approach leads to a significant overhead in terms of sample complexity. Here we demonstrate several general approaches to stable and private prediction that either eliminate or significantly reduce the overhead. Specifically, we demonstrate that for any class $C$ of VC dimension $d$ there exists a $\gamma$-uniformly stable algorithm for learning $C$ with excess error $\alpha$ using $\tilde O(d/(\alpha\gamma) + d/\alpha^2)$ samples. We also show that this bound is nearly tight. For $\eps$-differentially private prediction we give two new algorithms: one using $\tilde O(d/(\alpha^2\eps))$ samples and another one using $\tilde O(d^2/(\alpha\eps) + d/\alpha^2)$ samples. The best previously known bounds for these problems are $O(d/(\alpha^2\gamma))$ and $O(d/(\alpha^3\eps))$, respectively.} }
Endnote
%0 Conference Paper %T PAC learning with stable and private predictions %A Yuval Dagan %A Vitaly Feldman %B Proceedings of Thirty Third Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2020 %E Jacob Abernethy %E Shivani Agarwal %F pmlr-v125-dagan20a %I PMLR %P 1389--1410 %U https://proceedings.mlr.press/v125/dagan20a.html %V 125 %X We study binary classification algorithms for which the prediction on any point is not too sensitive to individual examples in the dataset. Specifically, we consider the notions of uniform stability (Bousquet and Elisseeff, 2001) and prediction privacy (Dwork and Feldman, 2018). Previous work on these notions shows how they can be achieved in the standard PAC model via simple aggregation of models trained on disjoint subsets of data. Unfortunately, this approach leads to a significant overhead in terms of sample complexity. Here we demonstrate several general approaches to stable and private prediction that either eliminate or significantly reduce the overhead. Specifically, we demonstrate that for any class $C$ of VC dimension $d$ there exists a $\gamma$-uniformly stable algorithm for learning $C$ with excess error $\alpha$ using $\tilde O(d/(\alpha\gamma) + d/\alpha^2)$ samples. We also show that this bound is nearly tight. For $\eps$-differentially private prediction we give two new algorithms: one using $\tilde O(d/(\alpha^2\eps))$ samples and another one using $\tilde O(d^2/(\alpha\eps) + d/\alpha^2)$ samples. The best previously known bounds for these problems are $O(d/(\alpha^2\gamma))$ and $O(d/(\alpha^3\eps))$, respectively.
APA
Dagan, Y. & Feldman, V.. (2020). PAC learning with stable and private predictions. Proceedings of Thirty Third Conference on Learning Theory, in Proceedings of Machine Learning Research 125:1389-1410 Available from https://proceedings.mlr.press/v125/dagan20a.html.

Related Material