mlsanityData to 14 Oct 2026

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

arXiv 2505.24737 ↗First posted 30 May 2025cs.LG stat.MLcited by 0

Not on the map. Why?

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.

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

20 of 44 references.

References · 20

  1. 2015Deep Residual Learning for Image Recognitioncited by 52,096
  2. 2020An Image is Worth 16x16 Words: Transformers for Image Recognition at Scalecited by 30,186
  3. 2020Prevalence of Neural Collapse during the terminal phase of deep learning trainingcited by 719
  4. 2022Unlocking High-Accuracy Differentially Private Image Classification through Scalecited by 224
  5. 2021Hyperparameter Tuning with Renyi Differential Privacycited by 104
  6. 2018Private Selection from Private Candidatescited by 75
  7. 2019Distribution-Independent PAC Learning of Halfspaces with Massart Noisecited by 54
  8. 2015Complexity Theoretic Limitations on Learning Halfspacescited by 50
  9. 2016Optimality of the Johnson-Lindenstrauss Lemmacited by 42
  10. 2023Revisiting the Last-Iterate Convergence of Stochastic Gradient Methodscited by 38
  11. 2023Practical Differentially Private Hyperparameter Tuning with Subsamplingcited by 19
  12. 2022Differentially Private Generalized Linear Models Revisitedcited by 17
8 more
  1. 2020Efficient, Noise-Tolerant, and Private Learning via Boostingcited by 15
  2. 2019Efficient Private Algorithms for Learning Large-Margin Halfspacescited by 13
  3. 2024Neural Collapse Meets Differential Privacy: Curious Behaviors of NoisyGD with Near-perfect Representation Learningcited by 8
  4. 2020Robust and Private Learning of Halfspacescited by 7
  5. 2022Differentially Private Learning with Margin Guaranteescited by 7
  6. 2025A Near-optimal Algorithm for Learning Margin Halfspaces with Massart Noisecited by 6
  7. 2025Learning Noisy Halfspaces with a Margin: Massart is No Harder than Randomcited by 5
  8. 2024Privacy Profiles for Private Selectioncited by 2

Built on by

Not cited yet.