Optimal Confidence Regions for the Multinomial Parameter
This addresses a long-standing question in statistical inference, providing foundational tools for decision-making in machine learning, though it is incremental in building on existing theory.
The paper tackles the problem of constructing tight confidence regions for categorical data, showing how to build minimum average volume confidence regions for multinomial parameters, which leads to optimal confidence intervals for linear functionals and improvements in sample complexity and regret for adaptive machine learning algorithms.
Construction of tight confidence regions and intervals is central to statistical inference and decision making. This paper develops new theory showing minimum average volume confidence regions for categorical data. More precisely, consider an empirical distribution $\widehat{\boldsymbol{p}}$ generated from $n$ iid realizations of a random variable that takes one of $k$ possible values according to an unknown distribution $\boldsymbol{p}$. This is analogous to a single draw from a multinomial distribution. A confidence region is a subset of the probability simplex that depends on $\widehat{\boldsymbol{p}}$ and contains the unknown $\boldsymbol{p}$ with a specified confidence. This paper shows how one can construct minimum average volume confidence regions, answering a long standing question. We also show the optimality of the regions directly translates to optimal confidence intervals of linear functionals such as the mean, implying sample complexity and regret improvements for adaptive machine learning algorithms.