Research map / Federated learning and privacy / Differential privacy
Adapting to Linear Separable Subsets with Large-Margin in Differentially Private Learning
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes an efficient, parameter-free (ε,δ)-DP algorithm for agnostic linear classification whose zero-one risk adapts to the margin of the best outlier-removed subset, via JL projection, noisy gradient descent, and private margin tuning.
Problem
x
Approach
Defines margin inliers/outliers as a generalization of geometric margin, uses a data-independent JL projection of dimension ~1/γ² plus noisy gradient descent with hinge loss, and privately selects the margin over a logarithmic grid (brute-force or advanced tuning) so the risk bound adapts to the best outlier subset without knowing γ or S_out.
Key results
- Achieves (ε,δ)-DP with empirical and population zero-one risk bound Õ(1/(γ²εn) + |S_out|/(γn)) without knowing γ or S_out, a √n improvement over prior agnostic results when |S_out| = o(√n).
- In the realizable case the bound recovers the Õ(1/n) rate of known-margin methods without requiring the margin as input.
- Advanced private hyperparameter tuning yields a utility bound scaling as log(|Θ|n/δ) instead of |Θ|^{1/2} for brute-force selection.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| adapt to the margin and outlier subset without knowing either in advance | DP Adaptive Margin · Binary linear classification, agnostic case | population zero-one risk bound: \bigOt(1/\sqrt{n}) -> o(1/\sqrt{n}) when |S_{\mathrm{out}}| = o(\sqrt{n}) | Helped |
| replace brute-force tuning with advanced private hyperparameter tuning | DP Adaptive Margin · Hyperparameter tuning | utility-bound dependence on the number of configurations: |\Theta|^{1/2} -> \log(|\Theta|n/\delta) | Helped |
| use advanced private tuning instead of brute-force tuning | DP Adaptive Margin · K hyperparameters, each with grid size m | utility upper-bound scaling: m^{\mathcal{O}(K)} -> \mathcal{O}(Km) | Helped |
| remove margin-outlier adaptation | DP Adaptive Margin · Binary linear classification, agnostic case | population zero-one risk bound | Hurt |
Limitations
- Proper learning dependence |S_out|/(γn) cannot be removed by the convex-ERM approach; open question left.
- Advanced tuning with truncated negative binomial needs expected repetitions polynomial in n for polynomial failure probability, so it is not logarithmic in runtime.
- Empirical margin motivation is shown only on CIFAR-10 classes 1 and 9 with pre-trained features.
Experimental setup
Datasets: CIFAR-10 (pre-trained ViT and ResNet-50 features, margin illustration)
Metrics: zero-one risk bound empirical zero-one risk population zero-one risk
Baselines: Bassily et al. 2021 (known-margin DP-ERM) Nguyen et al. confidence-margin DP algorithm Kuditipudi et al. DP large-margin learning pure-DP exponential-mechanism methods
Builds on: noisy gradient descent (Bassily et al.) Johnson-Lindenstrauss lemma private hyperparameter tuning (Liu and Talwar style)
Closest papers by meaning
- Differentially Private High-dimensional Variable Selection via Integer Programming (NeurIPS 2025 · similarity 0.88)
- The importance of feature preprocessing for differentially private linear optimization (ICLR 2024 · similarity 0.87)
- Differential Privacy in Scalable General Kernel Learning via $K$-means Nystr{\"o}m Random Features (NeurIPS 2024 · similarity 0.87)
- Private Gradient Descent for Linear Regression: Tighter Error Bounds and Instance-Specific Uncertainty Estimation (ICML 2024 · similarity 0.86)
- Differentially Private Optimization with Sparse Gradients (NeurIPS 2024 · similarity 0.86)
- Oracle-Efficient Differentially Private Learning with Public Data (NeurIPS 2024 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.