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

2025/05/30 by Wang, Erchi, Zhu, Yuqing, Wang, Yu-Xiang
#FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML)

paper · doi:10.48550/arxiv.2505.24737

Abstract

This paper studies the problem of differentially private empirical risk minimization (DP-ERM) for binary linear classification. We obtain an efficient (ε,δ)-DP algorithm with an empirical zero-one risk bound of O((1)/(γ²ε n) + \frac|S_out|γn) where n is the number of data points, S_out is an arbitrary subset of data one can remove and γ is the margin of linear separation of the remaining data points (after S_out is removed). Here, O(⋅) 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 S_out. We also derive a utility bound for the advanced private hyperparameter tuning algorithm.

Citations

• A Near-optimal Algorithm for Learning Margin Halfspaces with Massart Noise
• Learning Noisy Halfspaces with a Margin: Massart is No Harder than Random
• Neural Collapse Meets Differential Privacy: Curious Behaviors of NoisyGD with Near-perfect Representation Learning
• Privacy Profiles for Private Selection
• Revisiting the Last-Iterate Convergence of Stochastic Gradient Methods
• Differentially Private Generalized Linear Models Revisited
• Unlocking High-Accuracy Differentially Private Image Classification through Scale
• Differentially Private Learning with Margin Guarantees
• Hyperparameter Tuning with Renyi Differential Privacy
• Robust and Private Learning of Halfspaces
• An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale
• Efficient, Noise-Tolerant, and Private Learning via Boosting
• Distribution-Independent PAC Learning of Halfspaces with Massart Noise
• Efficient Private Algorithms for Learning Large-Margin Halfspaces
• Private Selection from Private Candidates
• Optimality of the Johnson-Lindenstrauss Lemma
• Deep Residual Learning for Image Recognition
• Complexity Theoretic Limitations on Learning Halfspaces
• The Perceptron with Dynamic Margin
• Differentially Private Empirical Risk Minimization
• The perceptron: A probabilistic model for information storage and organization in the brain.

Related

• Differentially Private Learning with Margin Guarantees
• Differentially Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Bounds
• The Power of Sampling: Dimension-free Risk Bounds in Private ERM
• Adaptive Differentially Private Empirical Risk Minimization
• High-Dimensional Private Empirical Risk Minimization by Greedy Coordinate Descent