Optimal Confidence Regions for the Multinomial Parameter

Abstract

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 $\hat{\mathbf{p}}$ generated from $n$ iid realizations of a random variable that takes one of $k$ possible values according to an unknown distribution $\mathbf{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 $\hat{\mathbf{p}}$ and contains the unknown $\mathbf{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.

References in corpus (7)

• Empirical Bernstein Bounds and Sample Variance Penalization
• lil' UCB : An Optimal Exploration Algorithm for Multi-Armed Bandits
• Informational Confidence Bounds for Self-Normalized Averages and Applications
• Confidence regions for the multinomial parameter with small sample size
• On Finding the Largest Mean Among Many
• Concentration Inequalities for the Empirical Distribution
• Tighter Confidence Intervals for Rating Systems

Cited by in corpus (1)

• Sharp Concentration Inequalities for the Centered Relative Entropy