On the Sample Complexity of Privately Learning Half-Spaces
Abstract
We present a differentially private learner for half-spaces over a finite domain $\mathcal{X}^d\subseteq\mathbb{R}^d$ with sample complexity $\tilde{O}(d\cdot\log^*\vert\mathcal{X}\vert)$, which improves over $\tilde{O}(d^{2.5}\cdot 8^{\log^*\vert\mathcal{X}\vert})$, the state-of-the-art result of [Kaplan et al., 2020]. The building block of our result is a novel differentially private algorithm that learns half-spaces by iteratively learning thresholds on angles.
Cite
Text
Huang et al. "On the Sample Complexity of Privately Learning Half-Spaces." Proceedings of the 16th Asian Conference on Machine Learning, 2024.Markdown
[Huang et al. "On the Sample Complexity of Privately Learning Half-Spaces." Proceedings of the 16th Asian Conference on Machine Learning, 2024.](https://mlanthology.org/acml/2024/huang2024acml-sample/)BibTeX
@inproceedings{huang2024acml-sample,
title = {{On the Sample Complexity of Privately Learning Half-Spaces}},
author = {Huang, Yi Hsiang and Chen, Wei-Hong and Tsai, Shi-Chun},
booktitle = {Proceedings of the 16th Asian Conference on Machine Learning},
year = {2024},
pages = {655-670},
volume = {260},
url = {https://mlanthology.org/acml/2024/huang2024acml-sample/}
}