# Adapting to Linear Separable Subsets with Large-Margin in Differentially Private Learning

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 20 of its 44 references that are in the map.
- First posted on arXiv 30 May 2025.

## Builds on (most cited first, 20 of 20)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale](https://mlsanity.com/paper/2010.11929/) (2020)
- [Prevalence of Neural Collapse during the terminal phase of deep learning training](https://mlsanity.com/paper/2008.08186/) (2020)
- [Unlocking High-Accuracy Differentially Private Image Classification through Scale](https://mlsanity.com/paper/2204.13650/) (2022)
- [Hyperparameter Tuning with Renyi Differential Privacy](https://mlsanity.com/paper/2110.03620/) (2021)
- [Private Selection from Private Candidates](https://mlsanity.com/paper/1811.07971/) (2018)
- [Distribution-Independent PAC Learning of Halfspaces with Massart Noise](https://mlsanity.com/paper/1906.10075/) (2019)
- [Complexity Theoretic Limitations on Learning Halfspaces](https://mlsanity.com/paper/1505.05800/) (2015)
- [Optimality of the Johnson-Lindenstrauss Lemma](https://mlsanity.com/paper/1609.02094/) (2016)
- [Revisiting the Last-Iterate Convergence of Stochastic Gradient Methods](https://mlsanity.com/paper/2312.08531/) (2023)
- [Practical Differentially Private Hyperparameter Tuning with Subsampling](https://mlsanity.com/paper/2301.11989/) (2023)
- [Differentially Private Generalized Linear Models Revisited](https://mlsanity.com/paper/2205.03014/) (2022)
- [Efficient, Noise-Tolerant, and Private Learning via Boosting](https://mlsanity.com/paper/2002.01100/) (2020)
- [Efficient Private Algorithms for Learning Large-Margin Halfspaces](https://mlsanity.com/paper/1902.09009/) (2019)
- [Neural Collapse Meets Differential Privacy: Curious Behaviors of NoisyGD with Near-perfect Representation Learning](https://mlsanity.com/paper/2405.08920/) (2024)
- [Robust and Private Learning of Halfspaces](https://mlsanity.com/paper/2011.14580/) (2020)
- [Differentially Private Learning with Margin Guarantees](https://mlsanity.com/paper/2204.10376/) (2022)
- [A Near-optimal Algorithm for Learning Margin Halfspaces with Massart Noise](https://mlsanity.com/paper/2501.09691/) (2025)
- [Learning Noisy Halfspaces with a Margin: Massart is No Harder than Random](https://mlsanity.com/paper/2501.09851/) (2025)
- [Privacy Profiles for Private Selection](https://mlsanity.com/paper/2402.06701/) (2024)

## Abstract (arXiv)

This paper studies the problem of differentially private empirical risk minimization (DP-ERM) for binary linear classification. We obtain an efficient (varepsilon,δ)-DP algorithm with an empirical zero-one risk bound of tildeOleft(frac1γ2varepsilon n + frac|Sout|γ nright) where n is the number of data points, Sout is an arbitrary subset of data one can remove and γ is the margin of linear separation of the remaining data points (after Sout is removed). Here, tildeO(·) hides only logarithmic terms. In the agnostic case, we improve the existing results when the number of outliers is small. Our algorithm is highly adaptive because it does not require knowing the margin parameter γ or outlier subset Sout. We also derive a utility bound for the advanced private hyperparameter tuning algorithm.