Statistically Near-Optimal Hypothesis Selection

Hypothesis Selection is a fundamental distribution learning problem where given a comparator-class$\mathcal{Q}=\{q_{1}, \ldots, q_{n}\}$of distributions, and a sampling access to an unknown target distribution$p$, the goal is to output a distribution$q$such that$\mathsf{TV}(p, q)$is close to opt, where$\mathsf{opt}=\min\nolimits_{i}\{\mathsf{TV}(p, q_{i})\}$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,$\mathsf{TV}(p, q)\leq 2\cdot\text{opt}+\varepsilon$, with a (nearly) optimal sample complexity of$\tilde{O}(\log n/\varepsilon^{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}(\sqrt{n}/\varepsilon^{2.5})$, and Yatracos (Annals of Statistics '85) gave a learner with optimal sample complexity of$O(\log n/\varepsilon^{2})$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.