Efficient Private Algorithms for Learning Large-Margin Halfspaces
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
Text
Nguyễn et al. "Efficient Private Algorithms for Learning Large-Margin Halfspaces." Proceedings of the 31st International Conference on Algorithmic Learning Theory, 2020.Markdown
[Nguyễn et al. "Efficient Private Algorithms for Learning Large-Margin Halfspaces." Proceedings of the 31st International Conference on Algorithmic Learning Theory, 2020.](https://mlanthology.org/alt/2020/nguyen2020alt-efficient/)BibTeX
@inproceedings{nguyen2020alt-efficient,
title = {{Efficient Private Algorithms for Learning Large-Margin Halfspaces}},
author = {Nguyễn, Huy Lê and Ullman, Jonathan and Zakynthinou, Lydia},
booktitle = {Proceedings of the 31st International Conference on Algorithmic Learning Theory},
year = {2020},
pages = {704-724},
volume = {117},
url = {https://mlanthology.org/alt/2020/nguyen2020alt-efficient/}
}