Sample-Optimal Locally Private Hypothesis Selection and the Provable Benefits of Interactivity
Not on the map. Why?
Abstract (arXiv)
We study the problem of hypothesis selection under the constraint of local differential privacy. Given a class F of k distributions and a set of i.i.d. samples from an unknown distribution h, the goal of hypothesis selection is to pick a distribution hatf whose total variation distance to h is comparable with the best distribution in F (with high probability). We devise an varepsilon-locally-differentially-private (varepsilon-LDP) algorithm that uses Thetaleft(frackα2min varepsilon2,1right) samples to guarantee that dTV(h,hatf)≤ α + 9 minf∈ FdTV(h,f) with high probability. This sample complexity is optimal for varepsilon<1, matching the lower bound of Gopi et al. (2020). All previously known algorithms for this problem required Omegaleft(fracklog kα2min varepsilon2 ,1 right) samples to work. Moreover, our result demonstrates the power of interaction for varepsilon-LDP hypothesis selection. Namely, it breaks the known lower bound of Omegaleft(fracklog kα2min varepsilon2 ,1 right) for the sample complexity of non-interactive hypothesis selection. Our algorithm breaks this barrier using only Theta(log log k) rounds of interaction. To prove our results, we define the notion of critical queries for a Statistical Query Algorithm (SQA) which may be of independent interest. Informally, an SQA is said to use a small number of critical queries if its success relies on the accuracy of only a small number of queries it asks. We then design an LDP algorithm that uses a smaller number of critical queries.
Key facts. Cited by 3 papers in the map (data through 13 Oct 2026). Builds on 56 of its 96 references that are in the map. First posted on arXiv 9 Dec 2023.
Builds on
56 of 96 references.
References · 56
- 2019Advances and Open Problems in Federated Learningcited by 3,040
- 2014RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Responsecited by 271
- 2016Robust Estimators in High Dimensions without the Computational Intractabilitycited by 209
- 2017Collecting Telemetry Data Privatelycited by 149
- 2016Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixturescited by 115
- 2016Minimax Optimal Procedures for Locally Private Estimationcited by 106
- 2018Privately Learning High-Dimensional Distributionscited by 104
- 2017Finite Sample Differentially Private Confidence Intervalscited by 103
- 2020CoinPress: Practical Private Mean and Covariance Estimationcited by 74
- 2020Private Mean Estimation of Heavy-Tailed Distributionscited by 73
- 2020Breaking the Communication-Privacy-Accuracy Trilemmacited by 68
- 2019Private Hypothesis Selectioncited by 60
38 more
- 2015Between Pure and Approximate Differential Privacycited by 56
- 2015Communication Lower Bounds for Statistical Estimation Problems via a Distributed Data Processing Inequalitycited by 50
- 2022Robustness Implies Privacy in Statistical Estimationcited by 47
- 2020On the Sample Complexity of Privately Learning Unbounded High-Dimensional Gaussianscited by 41
- 2021Private and polynomial time algorithms for learning Gaussians and beyondcited by 39
- 2021Private Robust Estimation by Stabilizing Convex Relaxationscited by 38
- 2022Optimal Algorithms for Mean Estimation under Local Differential Privacycited by 36
- 2021FriendlyCore: Practical Differentially Private Aggregationcited by 34
- 2021A Private and Computationally-Efficient Estimator for Unbounded Gaussianscited by 34
- 2018Geometric Lower Bounds for Distributed Parameter Estimation under Communication Constraintscited by 33
- 2022Private Estimation with Public Datacited by 32
- 2019The Power of Factorization Mechanisms in Local and Central Differential Privacycited by 30
- 2016A General Characterization of the Statistical Query Complexitycited by 27
- 2019Differentially Private Algorithms for Learning Mixtures of Separated Gaussianscited by 27
- 2014Near-optimal-sample estimators for spherical Gaussian mixturescited by 26
- 2018The Structure of Optimal Private Tests for Simple Hypothesescited by 26
- 2020Unified lower bounds for interactive high-dimensional estimation under information constraintscited by 22
- 2013Faster and Sample Near-Optimal Algorithms for Proper Learning Mixtures of Gaussianscited by 20
- 2017Heavy Hitters and the Structure of Local Privacycited by 20
- 2023Polynomial Time and Private Learning of Unbounded Gaussian Mixture Modelscited by 19
- 2020Locally Private Hypothesis Selectioncited by 17
- 2021Differentially-Private Clustering of Easy Instancescited by 17
- 2015Sample-Optimal Density Estimation in Nearly-Linear Timecited by 16
- 2019The Role of Interactivity in Local Differential Privacycited by 15
- 2019Private Identity Testing for High-Dimensional Distributionscited by 15
- 2020A bounded-noise mechanism for differential privacycited by 15
- 2023Fast Optimal Locally Private Mean Estimation via Random Projectionscited by 14
- 2023Private Distribution Learning with Public Data: The View from Sample Compressioncited by 14
- 2018Test without Trust: Optimal Locally Private Distribution Testingcited by 13
- 2021Inference under Information Constraints III: Local Privacy Constraintscited by 13
- 2021Privately Learning Mixtures of Axis-Aligned Gaussianscited by 13
- 2022Private High-Dimensional Hypothesis Testingcited by 12
- 2019The Optimal Approximation Factor in Density Estimationcited by 11
- 2023Simple Binary Hypothesis Testing under Local Differential Privacy and Communication Constraintscited by 10
- 2022Contraction of Locally Differentially Private Mechanismscited by 8
- 2018Locally Private Learning without Interaction Requires Separationcited by 7
- 2018Locally Private Gaussian Estimationcited by 7
- 2022The Role of Interactivity in Structured Estimationcited by 7
50 most cited of 56 All 56 (JSON)
Built on by
Citing papers per year: 2025: 2; 2026: 1.
3 papers.