# Differentially Private Top-k Selection via Canonical Lipschitz Mechanism

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 24 references that are in the map.
- First posted on arXiv 31 Jan 2022.

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

- [Private Learning and Sanitization: Pure vs. Approximate Differential Privacy](https://mlsanity.com/paper/1407.2674/) (2014)
- [Practical Differentially Private Top-k Selection with Pay-what-you-get Composition](https://mlsanity.com/paper/1905.04273/) (2019)
- [Near Instance-Optimality in Differential Privacy](https://mlsanity.com/paper/2005.10630/) (2020)
- [Permute-and-Flip: A new mechanism for differentially private selection](https://mlsanity.com/paper/2010.12603/) (2020)
- [Oneshot Differentially Private Top-k Selection](https://mlsanity.com/paper/2105.08233/) (2021)
- [The Permute-and-Flip Mechanism is Identical to Report-Noisy-Max with Exponential Noise](https://mlsanity.com/paper/2105.07260/) (2021)
- [A Joint Exponential Mechanism For Differentially Private Top-k](https://mlsanity.com/paper/2201.12333/) (2022)
- [The Large Margin Mechanism for Differentially Private Maximization](https://mlsanity.com/paper/1409.2177/) (2014)
- [Lost Relatives of the Gumbel Trick](https://mlsanity.com/paper/1706.04161/) (2017)
- [Duff: A Dataset-Distance-Based Utility Function Family for the Exponential Mechanism](https://mlsanity.com/paper/2010.04235/) (2020)

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

- [Feature Selection from Differentially Private Correlations](https://mlsanity.com/paper/2408.10862/) (2024)
- [Unleash the Power of Ellipsis: Accuracy-enhanced Sparse Vector Technique with Exponential Noise](https://mlsanity.com/paper/2407.20068/) (2024)

## Abstract (arXiv)

Selecting the top-k highest scoring items under differential privacy (DP) is a fundamental task with many applications. This work presents three new results. First, the exponential mechanism, permute-and-flip and report-noisy-max, as well as their oneshot variants, are unified into the Lipschitz mechanism, an additive noise mechanism with a single DP-proof via a mandated Lipschitz property for the noise distribution. Second, this new generalized mechanism is paired with a canonical loss function to obtain the canonical Lipschitz mechanism, which can directly select k-subsets out of d items in O(dk+d log d) time. The canonical loss function assesses subsets by how many users must change for the subset to become top-k. Third, this composition-free approach to subset selection improves utility guarantees by an Omega(log k) factor compared to one-by-one selection via sequential composition, and our experiments on synthetic and real-world data indicate substantial utility improvements.