Statistically Near-Optimal Hypothesis Selection
Statistically Near-Optimal Hypothesis Selection
Hypothesis Selection is a fundamental distribution learning problem where given a comparator-class <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\mathcal{Q}=\{q_{1}, \ldots, q_{n}\}$</tex> of distributions, and a sampling access to an unknown target distribution <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$p$</tex> , the goal is to output a distribution <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$q$</tex> such that <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\mathsf{TV}(p, q)$</tex> is close …