Research map / Learning theory and algorithms / Sample complexity
Nearly-Linear Time Private Hypothesis Selection with the Optimal Approximation Factor
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 central-DP hypothesis selection algorithm that runs in nearly-linear time in the number of hypotheses, keeps the optimal approximation factor 3, and uses polylogarithmic samples by privatizing an MDE-based nearly-linear-time method with the exponential mechanism and sparse vector technique.
Problem
Differentially private hypothesis selection: choose from n candidate distributions the one closest in total variation to an unknown distribution from samples, with approximation factor, sample complexity, and running time all good simultaneously in the central DP model.
Approach
Replaces the bucketing of the non-private nearly-linear-time MDE algorithm (Aliakbarpour et al.) with an exponential-mechanism distribution over hypotheses keyed to proxy distances, scores prompting hypotheses by a stable quantile of lift values, selects prompting hypotheses via sparse vector technique, and bounds rounds via a decreasing normalizing constant.
Key results
- Algorithm is an (alpha=3, eps, delta, beta)-proper learner for private hypothesis selection in the central model, matching the optimal non-private approximation factor.
- Uses s = Theta(log^3(n/delta)/(delta^2 beta^2 eps)) samples and runs in time Theta~(n/(delta^4 beta^3 eps)), nearly linear in n.
- Improves over prior private algorithms that required quadratic time O(n^2 · s) at approximation factor 3 or 9.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the proposed private hypothesis selection algorithm instead of prior private algorithms | Private hypothesis selection (central DP) · Private hypothesis selection (central DP) | time complexity: O(\numHypotheses^2 \cdot \numsamples) -> \tilde{O}\left( n \cdot \numsamples \, / \, \totalError \right) | Helped |
| Use the proposed private hypothesis selection algorithm instead of the prior result with approximation factor >54 | Private hypothesis selection (central DP) · Private hypothesis selection (central DP) | approximation factor: >54 -> 3 | Helped |
| Use the proposed private algorithm instead of the minimum distance estimate | Private hypothesis selection (central DP) · Private hypothesis selection (central DP) | sample complexity: O\left(\frac{\log \numHypotheses}{\totalError^2}+ \frac{\log \numHypotheses}{\totalError \epsDP}\right) -> O\left( \frac | Hurt |
| Use the proposed algorithm rather than the private Scheffé tournament | Private hypothesis selection (central DP) · Private hypothesis selection (central DP) | approximation factor: 9 -> 3 | Helped |
Limitations
- Sample complexity has an extra O(log^2 n / beta) factor over prior private methods, not the optimal log n / (beta^2) + log n/(beta eps) form.
- Polynomial dependence on 1/delta (confidence parameter) rather than log(1/delta).
- Privacy is enforced per component with basic composition, leading to suboptimal sample complexity.
Experimental setup
Metrics: total variation distance approximation factor sample complexity time complexity
Baselines: Private Scheffé tournament Bun et al. 2019 private hypothesis selection Minimum distance estimate private algorithm (Aden-Ali et al.)
Builds on: Aliakbarpour et al. nearly-linear time hypothesis selection minimum distance estimate exponential mechanism sparse vector technique
Closest papers by meaning
- Optimal Hypothesis Selection in (Almost) Linear Time (NeurIPS 2024 · similarity 0.92)
- Query-Efficient Locally Private Hypothesis Selection via the Scheffe Graph (NeurIPS 2025 · similarity 0.87)
- On the Computational Complexity of Private High-dimensional Model Selection (NeurIPS 2024 · similarity 0.86)
- Locally Optimal Private Sampling: Beyond the Global Minimax (NeurIPS 2025 · similarity 0.86)
- Optimal Rates for Differentially Private Hypothesis Testing with E-values (NeurIPS 2026 · similarity 0.85)
- Optimal Algorithms for Augmented Testing of Discrete Distributions (NeurIPS 2024 · similarity 0.85)
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.