# Differentially Private Learning with Margin Guarantees

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 58 references that are in the map.
- First posted on arXiv 21 Apr 2022.

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

- [Private Stochastic Convex Optimization with Optimal Rates](https://mlsanity.com/paper/1908.09970/) (2019)
- [Private Stochastic Convex Optimization: Optimal Rates in Linear Time](https://mlsanity.com/paper/2005.04763/) (2020)
- [Deep Learning with Label Differential Privacy](https://mlsanity.com/paper/2102.06062/) (2021)
- [Private Stochastic Convex Optimization: Optimal Rates in ℓ1 Geometry](https://mlsanity.com/paper/2103.01516/) (2021)
- [Private PAC learning implies finite Littlestone dimension](https://mlsanity.com/paper/1806.00949/) (2018)
- [Differentially Private Release and Learning of Threshold Functions](https://mlsanity.com/paper/1504.07553/) (2015)
- [Non-Euclidean Differentially Private Stochastic Convex Optimization: Optimal Rates in Linear Time](https://mlsanity.com/paper/2103.01278/) (2021)
- [Differentially Private Stochastic Optimization: New Results in Convex and Non-Convex Settings](https://mlsanity.com/paper/2107.05585/) (2021)
- [Optimality of the Johnson-Lindenstrauss Lemma](https://mlsanity.com/paper/1609.02094/) (2016)
- [Fast Sketching of Polynomial Kernels of Polynomial Degree](https://mlsanity.com/paper/2108.09420/) (2021)
- [Label differential privacy via clustering](https://mlsanity.com/paper/2110.02159/) (2021)
- [Relative Deviation Learning Bounds and Generalization with Unbounded Loss Functions](https://mlsanity.com/paper/1310.5796/) (2013)
- [Efficient Private Algorithms for Learning Large-Margin Halfspaces](https://mlsanity.com/paper/1902.09009/) (2019)
- [The Large Margin Mechanism for Differentially Private Maximization](https://mlsanity.com/paper/1409.2177/) (2014)
- [Relative Deviation Margin Bounds](https://mlsanity.com/paper/2006.14950/) (2020)

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

- [Differential Privacy has Bounded Impact on Fairness in Classification](https://mlsanity.com/paper/2210.16242/) (2022)
- [Replicable Learning of Large-Margin Halfspaces](https://mlsanity.com/paper/2402.13857/) (2024)
- [Initialization Matters: Privacy-Utility Analysis of Overparameterized Neural Networks](https://mlsanity.com/paper/2310.20579/) (2023)
- [Optimal Unbiased Randomizers for Regression with Label Differential Privacy](https://mlsanity.com/paper/2312.05659/) (2023)
- [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)
- [Adapting to Linear Separable Subsets with Large-Margin in Differentially Private Learning](https://mlsanity.com/paper/2505.24737/) (2025)

## Abstract (arXiv)

We present a series of new differentially private (DP) algorithms with dimension-independent margin guarantees. For the family of linear hypotheses, we give a pure DP learning algorithm that benefits from relative deviation margin guarantees, as well as an efficient DP learning algorithm with margin guarantees. We also present a new efficient DP learning algorithm with margin guarantees for kernel-based hypotheses with shift-invariant kernels, such as Gaussian kernels, and point out how our results can be extended to other kernels using oblivious sketching techniques. We further give a pure DP learning algorithm for a family of feed-forward neural networks for which we prove margin guarantees that are independent of the input dimension. Additionally, we describe a general label DP learning algorithm, which benefits from relative deviation margin bounds and is applicable to a broad family of hypothesis sets, including that of neural networks. Finally, we show how our DP learning algorithms can be augmented in a general way to include model selection, to select the best confidence margin parameter.