How fast can you find a good hypothesis?

Abstract

Hypothesis selection asks for a distribution close to an unknown P, given samples from P and access to n candidate hypotheses. We study the computational complexity of achieving statistically optimal sample complexity and approximation constants.