# Private Selection with Heterogeneous Sensitivities

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 15 of its 26 references that are in the map.
- First posted on arXiv 9 Jan 2025.

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

- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016)
- [Embarrassingly Shallow Autoencoders for Sparse Data](https://mlsanity.com/paper/1905.03375/) (2019)
- [Differentially Private Contextual Linear Bandits](https://mlsanity.com/paper/1810.00068/) (2018)
- [Private Selection from Private Candidates](https://mlsanity.com/paper/1811.07971/) (2018)
- [A Contextual Bandit Bake-off](https://mlsanity.com/paper/1802.04064/) (2018)
- [Locally Differentially Private (Contextual) Bandits Learning](https://mlsanity.com/paper/2006.00701/) (2020)
- [Generalized Linear Bandits with Local Differential Privacy](https://mlsanity.com/paper/2106.03365/) (2021)
- [Local Differential Privacy for Regret Minimization in Reinforcement Learning](https://mlsanity.com/paper/2010.07778/) (2020)
- [Permute-and-Flip: A new mechanism for differentially private selection](https://mlsanity.com/paper/2010.12603/) (2020)
- [The Permute-and-Flip Mechanism is Identical to Report-Noisy-Max with Exponential Noise](https://mlsanity.com/paper/2105.07260/) (2021)
- [Efficient Lipschitz Extensions for High-Dimensional Graph Statistics and Node Private Degree Distributions](https://mlsanity.com/paper/1504.07912/) (2015)
- [Popularity Bias in Collaborative Filtering-Based Multimedia Recommender Systems](https://mlsanity.com/paper/2203.00376/) (2022)
- [The Large Margin Mechanism for Differentially Private Maximization](https://mlsanity.com/paper/1409.2177/) (2014)
- [Randomized algorithms for precise measurement of differentially-private, personalized recommendations](https://mlsanity.com/paper/2308.03735/) (2023)

## Abstract (arXiv)

Differentially private (DP) selection involves choosing a high-scoring candidate from a finite candidate pool, where each score depends on a sensitive dataset. This problem arises naturally in a variety of contexts including model selection, hypothesis testing, and within many DP algorithms. Classical methods, such as Report Noisy Max (RNM), assume all candidates' scores are equally sensitive to changes in a single individual's data, but this often isn't the case. To address this, algorithms like the Generalised Exponential Mechanism (GEM) leverage variability in candidate sensitivities. However, we observe that while these algorithms can outperform RNM in some situations, they may underperform in others - they can even perform worse than random selection. In this work, we explore how the distribution of scores and sensitivities impacts DP selection mechanisms. In all settings we study, we find that there exists a mechanism that utilises heterogeneity in the candidate sensitivities that outperforms standard mechanisms like RNM. However, no single mechanism uniformly outperforms RNM. We propose using the correlation between the scores and sensitivities as the basis for deciding which DP selection mechanism to use. Further, we design a slight variant of GEM, modified GEM that generally performs well whenever GEM performs poorly. Relying on the correlation heuristic we propose combined GEM, which adaptively chooses between GEM and modified GEM and outperforms both in polarised settings.