# Contraction of Locally Differentially Private Mechanisms

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 82 references that are in the map.
- First posted on arXiv 24 Oct 2022.

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

- [Amplification by Shuffling: From Local to Central Differential Privacy via Anonymity](https://mlsanity.com/paper/1811.12469/) (2018)
- [cpSGD: Communication-efficient and differentially-private distributed SGD](https://mlsanity.com/paper/1805.10559/) (2018)
- [Protection Against Reconstruction and Its Applications in Private Federated Learning](https://mlsanity.com/paper/1812.00984/) (2018)
- [Minimax Optimal Procedures for Locally Private Estimation](https://mlsanity.com/paper/1604.02390/) (2016)
- [Breaking the Communication-Privacy-Accuracy Trilemma](https://mlsanity.com/paper/2007.11707/) (2020)
- [Discrete Distribution Estimation under Local Privacy](https://mlsanity.com/paper/1602.07387/) (2016)
- [Differentially Private Assouad, Fano, and Le Cam](https://mlsanity.com/paper/2004.06830/) (2020)
- [Communication Lower Bounds for Statistical Estimation Problems via a Distributed Data Processing Inequality](https://mlsanity.com/paper/1506.07216/) (2015)
- [Optimal Algorithms for Mean Estimation under Local Differential Privacy](https://mlsanity.com/paper/2205.02466/) (2022)
- [Inference under Information Constraints I: Lower Bounds from Chi-Square Contraction](https://mlsanity.com/paper/1812.11476/) (2018)
- [Optimal Schemes for Discrete Distribution Estimation under Locally Differential Privacy](https://mlsanity.com/paper/1702.00610/) (2017)
- [Lossless Compression of Efficient Private Local Randomizers](https://mlsanity.com/paper/2102.12099/) (2021)
- [Local Privacy, Data Processing Inequalities, and Statistical Minimax Rates](https://mlsanity.com/paper/1302.3203/) (2013)
- [Hadamard Response: Estimating Distributions Privately, Efficiently, and with Little Communication](https://mlsanity.com/paper/1802.04705/) (2018)
- [The Structure of Optimal Private Tests for Simple Hypotheses](https://mlsanity.com/paper/1811.11148/) (2018)
- [Fisher information under local differential privacy](https://mlsanity.com/paper/2005.10783/) (2020)
- [Unified lower bounds for interactive high-dimensional estimation under information constraints](https://mlsanity.com/paper/2010.06562/) (2020)
- [Optimal Compression of Locally Differentially Private Mechanisms](https://mlsanity.com/paper/2111.00092/) (2021)
- [Local Differential Privacy Is Equivalent to Contraction of Eγ-Divergence](https://mlsanity.com/paper/2102.01258/) (2021)
- [Locally Private Mean Estimation: Z-test and Tight Confidence Intervals](https://mlsanity.com/paper/1810.08054/) (2018)
- [The Role of Interactivity in Local Differential Privacy](https://mlsanity.com/paper/1904.03564/) (2019)
- [Local differential privacy: Elbow effect in optimal density estimation and adaptation over Besov ellipsoids](https://mlsanity.com/paper/1903.01927/) (2019)
- [Inference under Information Constraints III: Local Privacy Constraints](https://mlsanity.com/paper/2101.07981/) (2021)
- [Private Frequency Estimation via Projective Geometry](https://mlsanity.com/paper/2203.00194/) (2022)
- [The Role of Interactivity in Structured Estimation](https://mlsanity.com/paper/2203.06870/) (2022)
- [Linear Queries Estimation with Local Differential Privacy](https://mlsanity.com/paper/1810.02810/) (2018)
- [INSPECTRE: Privately Estimating the Unseen](https://mlsanity.com/paper/1803.00008/) (2018)

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

- [Simple Binary Hypothesis Testing under Local Differential Privacy and Communication Constraints](https://mlsanity.com/paper/2301.03566/) (2023)
- [Contraction of Private Quantum Channels and Private Quantum Hypothesis Testing](https://mlsanity.com/paper/2406.18651/) (2024)
- [An invitation to the sample complexity of quantum hypothesis testing](https://mlsanity.com/paper/2403.17868/) (2024)
- [Sample-Optimal Locally Private Hypothesis Selection and the Provable Benefits of Interactivity](https://mlsanity.com/paper/2312.05645/) (2023)
- [Locally Private Sampling with Public Data](https://mlsanity.com/paper/2411.08791/) (2024)
- [Locally Optimal Private Sampling: Beyond the Global Minimax](https://mlsanity.com/paper/2510.09485/) (2025)
- [Query-Efficient Locally Private Hypothesis Selection via the Scheffe Graph](https://mlsanity.com/paper/2509.16180/) (2025)
- [Privacy-Utility Tradeoffs in Quantum Information Processing](https://mlsanity.com/paper/2602.10510/) (2026)

## Abstract (arXiv)

We investigate the contraction properties of locally differentially private mechanisms. More specifically, we derive tight upper bounds on the divergence between PK and QK output distributions of an ε-LDP mechanism K in terms of a divergence between the corresponding input distributions P and Q, respectively. Our first main technical result presents a sharp upper bound on the chi2-divergence chi2(PK|QK) in terms of chi2(P|Q) and varepsilon. We also show that the same result holds for a large family of divergences, including KL-divergence and squared Hellinger distance. The second main technical result gives an upper bound on chi2(PK|QK) in terms of total variation distance mathsfTV(P, Q) and ε. We then utilize these bounds to establish locally private versions of the van Trees inequality, Le Cam's, Assouad's, and the mutual information methods, which are powerful tools for bounding minimax estimation risks. These results are shown to lead to better privacy analyses than the state-of-the-arts in several statistical problems such as entropy and discrete distribution estimation, non-parametric density estimation, and hypothesis testing.