On the sample complexity of privately learning half-spaces

Yi Hsiang Huang, Wei-Hong Chen, Shi-Chun Tsai
Proceedings of the 16th Asian Conference on Machine Learning, PMLR 260:655-670, 2025.

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 this Paper

BibTeX
@InProceedings{pmlr-v260-huang25b, 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}, pages = {655--670}, year = {2025}, editor = {Nguyen, Vu and Lin, Hsuan-Tien}, volume = {260}, series = {Proceedings of Machine Learning Research}, month = {05--08 Dec}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v260/main/assets/huang25b/huang25b.pdf}, url = {https://proceedings.mlr.press/v260/huang25b.html}, 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.} }
Endnote
%0 Conference Paper %T On the sample complexity of privately learning half-spaces %A Yi Hsiang Huang %A Wei-Hong Chen %A Shi-Chun Tsai %B Proceedings of the 16th Asian Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2025 %E Vu Nguyen %E Hsuan-Tien Lin %F pmlr-v260-huang25b %I PMLR %P 655--670 %U https://proceedings.mlr.press/v260/huang25b.html %V 260 %X 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.
APA
Huang, Y.H., Chen, W. & Tsai, S.. (2025). On the sample complexity of privately learning half-spaces. Proceedings of the 16th Asian Conference on Machine Learning, in Proceedings of Machine Learning Research 260:655-670 Available from https://proceedings.mlr.press/v260/huang25b.html.

Related Material