# Statistically Near-Optimal Hypothesis Selection

arXiv: https://arxiv.org/abs/2108.07880 · HTML: https://mlsanity.com/paper/2108.07880/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 38 references that are in the map.
- First posted on arXiv 17 Aug 2021.

## Builds on (most cited first, 14 of 14)

- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [Robust Estimators in High Dimensions without the Computational Intractability](https://mlsanity.com/paper/1604.06443/) (2016)
- [Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixtures](https://mlsanity.com/paper/1611.03473/) (2016)
- [Preserving Statistical Validity in Adaptive Data Analysis](https://mlsanity.com/paper/1411.2664/) (2014)
- [List-Decodable Robust Mean Estimation and Learning Mixtures of Spherical Gaussians](https://mlsanity.com/paper/1711.07211/) (2017)
- [Optimal Learners for Multiclass Problems](https://mlsanity.com/paper/1405.2420/) (2014)
- [Relative Loss Bounds for On-line Density Estimation with the Exponential Family of Distributions](https://mlsanity.com/paper/1301.6677/) (2013)
- [Private Hypothesis Selection](https://mlsanity.com/paper/1905.13229/) (2019)
- [Near-optimal-sample estimators for spherical Gaussian mixtures](https://mlsanity.com/paper/1402.4746/) (2014)
- [Faster and Sample Near-Optimal Algorithms for Proper Learning Mixtures of Gaussians](https://mlsanity.com/paper/1312.1054/) (2013)
- [Locally Private Hypothesis Selection](https://mlsanity.com/paper/2002.09465/) (2020)
- [Near-Optimal Density Estimation in Near-Linear Time Using Variable-Width Histograms](https://mlsanity.com/paper/1411.0169/) (2014)
- [Sample-Efficient Learning of Mixtures](https://mlsanity.com/paper/1706.01596/) (2017)
- [Fast and Sample Near-Optimal Algorithms for Learning Multidimensional Histograms](https://mlsanity.com/paper/1802.08513/) (2018)

## Built on by (most cited first, 7 of 7)

- [Distribution Learnability and Robustness](https://mlsanity.com/paper/2406.17814/) (2024)
- [Sample-Optimal Locally Private Hypothesis Selection and the Provable Benefits of Interactivity](https://mlsanity.com/paper/2312.05645/) (2023)
- [No Free Lunch: Fundamental Limits of Learning Non-Hallucinating Generative Models](https://mlsanity.com/paper/2410.19217/) (2024)
- [TURF: A Two-factor, Universal, Robust, Fast Distribution Learning Algorithm](https://mlsanity.com/paper/2202.07172/) (2022)
- [Nearly-Linear Time Private Hypothesis Selection with the Optimal Approximation Factor](https://mlsanity.com/paper/2506.01162/) (2025)
- [Query-Efficient Locally Private Hypothesis Selection via the Scheffe Graph](https://mlsanity.com/paper/2509.16180/) (2025)
- [Hypothesis Selection via Weighted Medians](https://mlsanity.com/paper/2610.20375/) (2026)

## Abstract (arXiv)

Hypothesis Selection is a fundamental distribution learning problem where given a comparator-class Q=q1,ldots, qn of distributions, and a sampling access to an unknown target distribution p, the goal is to output a distribution q such that mathsfTV(p,q) is close to opt, where opt = minimathsfTV(p,qi) and mathsfTV(·, ·) denotes the total-variation distance. Despite the fact that this problem has been studied since the 19th century, its complexity in terms of basic resources, such as number of samples and approximation guarantees, remains unsettled (this is discussed, e.g., in the charming book by Devroye and Lugosi `00). This is in stark contrast with other (younger) learning settings, such as PAC learning, for which these complexities are well understood. We derive an optimal 2-approximation learning strategy for the Hypothesis Selection problem, outputting q such that mathsfTV(p,q) ≤2 · opt + eps, with a (nearly) optimal sample complexity of~tilde O(log n/ε2). This is the first algorithm that simultaneously achieves the best approximation factor and sample complexity: previously, Bousquet, Kane, and Moran (COLT `19) gave a learner achieving the optimal 2-approximation, but with an exponentially worse sample complexity of tilde O(√n/ε2.5), and Yatracos~(Annals of Statistics `85) gave a learner with optimal sample complexity of O(log n /ε2) but with a sub-optimal approximation factor of 3.