Research map / Learning theory and algorithms / Sample complexity
Optimal Hypothesis Selection in (Almost) Linear Time
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 the first almost-linear-time proper hypothesis selection algorithms achieving accuracy alpha=3 (time ~O(n s/(δ^3 ε))) and alpha=4 (time ~O(n s log(1/δ))), via bucketed semi-distance updates and seed boosting.
Problem
Hypothesis selection (density estimation over a finite class): select a distribution from n candidates whose total variation distance to an unknown P is at most alpha*OPT + eps, with near-optimal sample size and fast running time; prior algorithms achieving alpha<5 needed Omega(n^2) time.
Approach
Replace the quadratic minimum distance estimate by maintaining approximate score values in buckets and repeatedly finding "prompting" hypotheses that move a constant fraction of a bucket, plus a seed-boosting scheme with sampled approximate maxima, achieving alpha=3 in near-linear time (and alpha=4 with better eps dependence).
Key results
- Algorithm 1 is an (alpha=3, eps, delta)-proper learner using s=O(log(n/delta)/eps^2) samples and ~O(n/(delta^3 eps^3)) time, the first almost-linear-time algorithm with alpha=3.
- Algorithm 4 achieves alpha=4 in ~O(n*log^2(1/delta)/eps^2) time, linear in n for fixed eps and delta.
- Prior linear-time algorithms achieved alpha=9 (AJOS14, AFJ+18) or alpha=5 (ABS23); previous alpha<5 algorithms required Omega(n^2) time.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Algorithm 1 instead of the minimum distance estimate [DL01] | Hypothesis selection · Hypothesis selection | time complexity: O(n3 · s) -> ˜O(n · s / ϵ) | Helped |
| Use Algorithm 1 instead of the minimum distance estimate [DL01] | Hypothesis selection · Hypothesis selection | accuracy parameter α: 3 -> 3 | No clear effect |
| Use Algorithm 4 instead of [ABS23] | Hypothesis selection · Hypothesis selection | time complexity: ˜O(n · s) -> ˜O (n · s) | Helped |
| Use Algorithm 4 instead of [ABS23] | Hypothesis selection · Hypothesis selection | accuracy parameter α: 5 -> 4 | Hurt |
| Use Algorithm 1 rather than Algorithm 4 | Hypothesis selection · Hypothesis selection | accuracy parameter α: 4 -> 3 | Helped |
| Use Algorithm 1 rather than Algorithm 4 | Hypothesis selection · Hypothesis selection | time complexity: ˜O (n · s) -> ˜O(n · s / ϵ) | Hurt |
Surprising findings
- Confidence parameter delta enters polynomially (1/delta^3) in the alpha=3 algorithm, unlike standard log(1/delta) amplification, because boosting by repeated runs would multiply alpha.
Limitations
- The alpha=3 algorithm has polynomial dependence on 1/delta and 1/eps, off from optimal O(n s) time by a 1/(delta^3 eps) factor.
- The alpha=4 algorithm has a worse accuracy parameter than the optimal alpha=3.
- Results are theoretical; no empirical evaluation is reported.
Experimental setup
Metrics: total variation distance guarantee (alpha, eps, delta) running time
Baselines: Scheffé tournament minimum distance estimate Mahalanabis-Stefankovic AJOS14/AFJ+18 linear-time alpha=9 ABS23 alpha=5 AAC+23
Builds on: minimum distance estimate (Devroye and Lugosi) Mahalanabis and Stefankovic minimum distance estimate Acharya-Bhattacharyya-Sun hypothesis selection
Closest papers by meaning
- Nearly-Linear Time Private Hypothesis Selection with the Optimal Approximation Factor (NeurIPS 2025 · similarity 0.92)
- Hypothesis Selection with Memory Constraints (NeurIPS 2023 · similarity 0.89)
- Optimal Algorithms for Augmented Testing of Discrete Distributions (NeurIPS 2024 · similarity 0.85)
- Towards a statistical theory of data selection under weak supervision (ICLR 2024 · similarity 0.85)
- One Sample Fits All: Approximating All Probabilistic Values Simultaneously and Efficiently (NeurIPS 2024 · similarity 0.85)
- Statistical-Computational Trade-offs for Density Estimation (NeurIPS 2024 · similarity 0.84)
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.