Erik Learned-Miller: Confidence bounds on the mean: what is possible?
Abstract
I will describe a long term effort to explore confidence bounds on the mean of an unknown distribution from iid samples. In particular, I will focus on small samples sizes (n<30), where the traditional reliance on the Central Limit Theorem may break down. There are two major settings I have considered in my work, the case where the support of the distribution is known, and where it is unknown. In this talk, I will mostly focus on the former. First, I will address notions of the optimality and admissibility of such bounds: do optimal bounds even exist? Answer: for common definitions of optimal, there exist no such optimal bounds. However, there are a great number of admissible bounds, and we give a precise characterization of them, as solutions to particular optimization problems.
The next issue is that many of these admissible bounds are computationally intractable, requiring time exponential in the sample size (or support size) to compute. However, we present a single admissible bound which appears to be computable in linear time, but only an (unproven) conjecture that the algorithm guarantees the best result. Perhaps one of you will finish the proof :)