# Efficient Private Algorithms for Learning Large-Margin Halfspaces

arXiv: https://arxiv.org/abs/1902.09009 · HTML: https://mlsanity.com/paper/1902.09009/

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Feb 2019.

## Built on by (most cited first, 13 of 13)

- [A Theory of PAC Learnability of Partial Concept Classes](https://mlsanity.com/paper/2107.08444/) (2021)
- [Differentially Private Generalized Linear Models Revisited](https://mlsanity.com/paper/2205.03014/) (2022)
- [Replicable Learning of Large-Margin Halfspaces](https://mlsanity.com/paper/2402.13857/) (2024)
- [PILLAR: How to make semi-private learning more effective](https://mlsanity.com/paper/2306.03962/) (2023)
- [Neural Collapse Meets Differential Privacy: Curious Behaviors of NoisyGD with Near-perfect Representation Learning](https://mlsanity.com/paper/2405.08920/) (2024)
- [Differentially Private Learning with Margin Guarantees](https://mlsanity.com/paper/2204.10376/) (2022)
- [Borsuk-Ulam and Replicable Learning of Large-Margin Halfspaces](https://mlsanity.com/paper/2503.15294/) (2025)
- [Private Geometric Median](https://mlsanity.com/paper/2406.07407/) (2024)
- [On PAC Learning Halfspaces in Non-interactive Local Privacy Model with Public Unlabeled Data](https://mlsanity.com/paper/2209.08319/) (2022)
- [Privately Learning Decision Lists and a Differentially Private Winnow](https://mlsanity.com/paper/2602.07370/) (2026)
- [Differentially-Private Bayes Consistency](https://mlsanity.com/paper/2212.04216/) (2022)
- [Adapting to Linear Separable Subsets with Large-Margin in Differentially Private Learning](https://mlsanity.com/paper/2505.24737/) (2025)
- [Private Component-by-Component Learning](https://mlsanity.com/paper/2610.05102/) (2026)

## Abstract (arXiv)

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.