Research map / Federated learning and privacy / Differential privacy
Query-Efficient Locally Private Hypothesis Selection via the Scheffe Graph
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Gives a non-interactive epsilon-LDP hypothesis selection algorithm using Õ(k^{3/2}) samples via a relaxed minimum distance estimator and a new Scheffé graph whose small dominating set bounds the number of queries.
Problem
Non-interactive hypothesis selection under local differential privacy: selecting the near-closest distribution from k candidates with as few samples as possible, previously needing O(k^2) samples non-interactively or interactive protocols.
Approach
Replace the full set of pairwise Scheffé sets with a small dominating set of a directed "Scheffé graph" over pairs of hypotheses, so only Õ(k^{3/2}) non-adaptive binary queries are needed, combined with a relaxed minimum distance estimator and randomized response.
Key results
- Non-interactive epsilon-LDP algorithm with n = Õ(k^{3/2}/(α²ε²)) samples achieving 13·OPT + α ℓ1 error with high probability.
- Scheffé graph (φ=1/6) has domination number at most 4k^{3/2}sqrt(log k), findable in O(k^{5/2} sqrt(log k)) expected time.
- Nearly matching lower bound: domination number of the triangular-substructure graph class is Ω̃(k^{3/2}), and a flattening conjecture is shown false.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the Scheffé graph to select a smaller set of non-adaptive queries | LDP hypothesis selection · LDP hypothesis selection | sample complexity: O(k^2) -> \tilde{O}(k^{3/2}) | Helped |
| Use a non-interactive protocol instead of an interactive protocol | LDP hypothesis selection · LDP hypothesis selection | interactivity: O(k) -> \tilde{O}(k^{3/2}) | Mixed |
| Apply the algorithm recursively for t rounds | Scheffé graph algorithm · LDP hypothesis selection, t rounds | sample complexity: \tilde{O}(k^{3/2}) -> O\left( \frac{k^{1 + \frac{1}{3^t - 1}} t\sqrt{\log{k}}\log(k/\beta)}{\alpha^2\varepsilon^2} \righ | Helped |
| Restrict the query set to a dominating set in the 1/6-Scheffé graph | Scheffé graph algorithm · LDP hypothesis selection | number of queries: \binom{k}{2} -> 4k^{3/2}\sqrt{\log k} | Helped |
Surprising findings
- The natural flattening conjecture used to obtain Õ(k) sample complexity is false (explicit counterexample).
- Triangular substructure alone cannot yield a domination number better than Õ(k^{3/2}), so further graph structure is needed.
Limitations
- Sample complexity remains Õ(k^{3/2}), not the Õ(k) lower bound achievable interactively.
- Domination number bound may be loose; empirical evidence suggests Õ(k) but unproven.
- Preprocessing time Õ(k^{5/2}) is substantial.
Experimental setup
Metrics: sample complexity query complexity domination number l1 approximation factor
Baselines: minimum distance estimator (all pairwise Scheffé sets) interactive O(k) LDP hypothesis selection non-interactive Õ(k) simple hypothesis testing (Gopi et al.)
Builds on: Scheffé test randomized response Gopi et al. LDP hypothesis selection Pour, Ashtiani, Asoodeh interactive LDP hypothesis selection
Closest papers by meaning
- Sort, Partition, Randomize: Optimal Binary Hypothesis Testing under Local Differential Privacy (NeurIPS 2026 · similarity 0.89)
- On Differential Privacy for Adaptively Solving Search Problems via Sketching (ICML 2025 · similarity 0.87)
- Locally Optimal Private Sampling: Beyond the Global Minimax (NeurIPS 2025 · similarity 0.87)
- Minimax Optimal Two-Sample Testing under Local Differential Privacy (NeurIPS 2026 · similarity 0.87)
- Exactly Minimax-Optimal Locally Differentially Private Sampling (NeurIPS 2024 · similarity 0.87)
- Nearly-Linear Time Private Hypothesis Selection with the Optimal Approximation Factor (NeurIPS 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.