# The Large Margin Mechanism for Differentially Private Maximization

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Sep 2014.

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

- [How to DP-fy ML: A Practical Guide to Machine Learning with Differential Privacy](https://mlsanity.com/paper/2303.00654/) (2023)
- [Adaptive Private-K-Selection with Adaptive K and Application to Multi-label PATE](https://mlsanity.com/paper/2203.16100/) (2022)
- [Differentially Private Learning with Margin Guarantees](https://mlsanity.com/paper/2204.10376/) (2022)
- [Differentially Private Top-k Selection via Canonical Lipschitz Mechanism](https://mlsanity.com/paper/2201.13376/) (2022)
- [Answering Private Linear Queries Adaptively using the Common Mechanism](https://mlsanity.com/paper/2212.00135/) (2022)
- [Differentially-Private Bayes Consistency](https://mlsanity.com/paper/2212.04216/) (2022)
- [Private Selection with Heterogeneous Sensitivities](https://mlsanity.com/paper/2501.05309/) (2025)

## Abstract (arXiv)

A basic problem in the design of privacy-preserving algorithms is the private maximization problem: the goal is to pick an item from a universe that (approximately) maximizes a data-dependent function, all under the constraint of differential privacy. This problem has been used as a sub-routine in many privacy-preserving algorithms for statistics and machine-learning. Previous algorithms for this problem are either range-dependent---i.e., their utility diminishes with the size of the universe---or only apply to very restricted function classes. This work provides the first general-purpose, range-independent algorithm for private maximization that guarantees approximate differential privacy. Its applicability is demonstrated on two fundamental tasks in data mining and machine learning.