Efficient Private Algorithms for Learning Large-Margin Halfspaces

Huy Lê Nguyễn, Jonathan Ullman, Lydia Zakynthinou
Proceedings of the 31st International Conference on Algorithmic Learning Theory, PMLR 117:704-724, 2020.

Abstract

We present new differentially private algorithms for learning a large-margin halfspace. In contrast to previous algorithms, which are based on either differentially private simulations of the statistical query model or on private convex optimization, the sample complexity of our algorithms depends only on the margin of the data, and not on the dimension. We complement our results with a lower bound, showing that the dependence of our upper bounds on the margin is optimal.

Cite this Paper

BibTeX
@InProceedings{pmlr-v117-nguy-en20a, title = {Efficient {P}rivate {A}lgorithms for {L}earning {L}arge-{M}argin {H}alfspaces}, author = {Nguy\~{\^{e}}n, Huy L\^{e} and Ullman, Jonathan and Zakynthinou, Lydia}, booktitle = {Proceedings of the 31st International Conference on Algorithmic Learning Theory}, pages = {704--724}, year = {2020}, editor = {Kontorovich, Aryeh and Neu, Gergely}, volume = {117}, series = {Proceedings of Machine Learning Research}, month = {08 Feb--11 Feb}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v117/nguy-en20a/nguy-en20a.pdf}, url = {https://proceedings.mlr.press/v117/nguy-en20a.html}, abstract = {We present new differentially private algorithms for learning a large-margin halfspace. In contrast to previous algorithms, which are based on either differentially private simulations of the statistical query model or on private convex optimization, the sample complexity of our algorithms depends only on the margin of the data, and not on the dimension. We complement our results with a lower bound, showing that the dependence of our upper bounds on the margin is optimal.} }
Endnote
%0 Conference Paper %T Efficient Private Algorithms for Learning Large-Margin Halfspaces %A Huy Lê Nguyễn %A Jonathan Ullman %A Lydia Zakynthinou %B Proceedings of the 31st International Conference on Algorithmic Learning Theory %C Proceedings of Machine Learning Research %D 2020 %E Aryeh Kontorovich %E Gergely Neu %F pmlr-v117-nguy-en20a %I PMLR %P 704--724 %U https://proceedings.mlr.press/v117/nguy-en20a.html %V 117 %X We present new differentially private algorithms for learning a large-margin halfspace. In contrast to previous algorithms, which are based on either differentially private simulations of the statistical query model or on private convex optimization, the sample complexity of our algorithms depends only on the margin of the data, and not on the dimension. We complement our results with a lower bound, showing that the dependence of our upper bounds on the margin is optimal.
APA
Nguyễn, H.L., Ullman, J. & Zakynthinou, L.. (2020). Efficient Private Algorithms for Learning Large-Margin Halfspaces. Proceedings of the 31st International Conference on Algorithmic Learning Theory, in Proceedings of Machine Learning Research 117:704-724 Available from https://proceedings.mlr.press/v117/nguy-en20a.html.

Related Material