# Sample-Optimal Locally Private Hypothesis Selection and the Provable Benefits of Interactivity

Source: [Sample-Optimal Locally Private Hypothesis Selection and the Provable Benefits of Interactivity](<https://www.sota2.com/research/paper/68fa5b361e209131ce9c63e2>)

Collection index: [llms.txt](<https://www.sota2.com/research/llms.txt>)

Data updated: 2026-03-06T05:00:12.548Z

Authors: Alireza F. Pour, Hassan Ashtiani, Shahab Asoodeh

Published: 2023-12-09T19:22:10.000Z

## Abstract

We study the problem of hypothesis selection under the constraint of local differential privacy. Given a class $\\mathcal{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 $\\hat{f}$ whose total variation distance to $h$ is comparable with the best distribution in $\\mathcal{F}$ (with high probability). We devise an $\\varepsilon$-locally-differentially-private ($\\varepsilon$-LDP) algorithm that uses $\\Theta\\left(\\frac{k}{\\alpha^2\\min \\{\\varepsilon^2,1\\}}\\right)$ samples to guarantee that $d\_{TV}(h,\\hat{f})\\leq \\alpha + 9 \\min\_{f\\in \\mathcal{F}}d\_{TV}(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 $\\Omega\\left(\\frac{k\\log k}{\\alpha^2\\min \\{ \\varepsilon^2 ,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 $\\Omega\\left(\\frac{k\\log k}{\\alpha^2\\min \\{ \\varepsilon^2 ,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 \\emph{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.

## Recorded benchmark results

A research result applies to its stated dataset, split, metric and evaluation configuration. Compare like-for-like settings, preserve the metric's unit and direction, and distinguish paper-reported results from independent reproduction. The best result recorded here is not a claim of exhaustive, current global coverage.

- [Hypothesis Selection on Local Differential Privacy (LDP) model](<https://www.sota2.com/research/sota/hypothesis-selection-on-local-differential-privacy-ldp-model.md>): Hypothesis Selection; Local Differential Privacy (LDP) model; Approximation Factor: 9.

## Original sources and implementation

[Original paper](<https://arxiv.org/abs/2312.05645>)

[PDF](<https://arxiv.org/pdf/2312.05645.pdf>)