Statistically Near-Optimal Hypothesis Selection

Olivier Bousquet, Mark Braverman, Gillat Kol, Klim Efremenko, Shay Moran

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Hypothesis Selection is a fundamental distribution learning problem where given a comparator-class Q={q1,.., qn} of distributions, and a sampling access to an unknown target distribution p, the goal is to output a distribution q such that TV(p, q) is close to opt, where opt=\min\nolimitsi TV(p, qi) and TV (.,.) 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, TV(p, q)≤q 2 opt+varepsilon, with a (nearly) optimal sample complexity of 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 tildeO}(√n2.5), and Yatracos (Annals of Statistics '85) gave a learner with optimal sample complexity of O(log n varepsilon2) but with a sub-optimal approximation factor of 3. We mention that many works in the Density Estimation (a.k.a., Distribution Learning) literature use Hypothesis Selection as a black box subroutine. Our result therefore implies an improvement on the approximation factors obtained by these works, while keeping their sample complexity intact. For example, our result improves the approximation factor of the algorithm of Ashtiani, Ben-David, Harvey, Liaw, and Mehrabian (JACM '20) for agnostic learning of mixtures of gaussians from 9 to 6, while maintaining its nearly-tight sample complexity.

Original languageEnglish (US)
Title of host publicationProceedings - 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science, FOCS 2021
PublisherIEEE Computer Society
Number of pages11
ISBN (Electronic)9781665420556
StatePublished - 2022
Event62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021 - Virtual, Online, United States
Duration: Feb 7 2022Feb 10 2022

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
ISSN (Print)0272-5428


Conference62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021
Country/TerritoryUnited States
CityVirtual, Online

All Science Journal Classification (ASJC) codes

  • General Computer Science


Dive into the research topics of 'Statistically Near-Optimal Hypothesis Selection'. Together they form a unique fingerprint.

Cite this