Optimal Confidence Regions for the Multinomial Parameter

Matthew L. Malloy, Ardhendu Tripathy, Robert D. NowakarXiv 2020 · arXiv

Introduction

Estimating the underlying probability distribution of categorical data—the multinomial parameter—is a foundational task in statistics and machine learning. Whether analyzing user click-through rates, rolling a loaded die, or sampling from discrete distributions in reinforcement learning, researchers must quantify uncertainty through confidence regions. Ideally, these regions should be as small as possible while maintaining a strict coverage guarantee (e.g., 95%).

Historically, this problem has been addressed using two main approaches: asymptotic approximations, which often fail to provide rigorous coverage guarantees in small-sample regimes, or concentration inequalities (such as Hoeffding, Sanov, or Bernstein bounds), which guarantee coverage but often produce excessively large, conservative regions. This paper introduces a "level-set" construction for multinomial confidence regions and proves that they are mathematically optimal, achieving the minimum average volume among all valid constructions.

Methodology

Minimal Volume Regions

The authors extend the logic of exact Clopper-Pearson intervals for binomial distributions to the multinomial case. They define a "covering collection"—a set of empirical outcomes that captures at least $1-\delta$ of the probability mass under a given parameter. By inverting this mapping, they construct a confidence region in the probability simplex.

Theoretical Optimality

The core contribution of the paper is Theorem 1, which rigorously proves that minimizing the cardinality of the covering collection directly minimizes the average Lebesgue measure (volume) of the resulting confidence region. This property holds regardless of whether the average is taken over all empirical outcomes or assumes a uniform prior over the unknown multinomial parameter.

Linear Functionals and Computational Efficiency

While the primary region exists within the probability simplex, many applications require confidence intervals for linear functionals, such as the mean. The authors demonstrate that projecting these optimal simplex regions onto a linear functional produces intervals that are significantly tighter than those derived from standard concentration inequalities.

To address the computational complexity of exact enumeration—which scales as $O(n^k)$ for $n$ samples and $k$ categories—the authors introduce an outer bound based on Kullback-Leibler (KL) divergence. This allows for a faster search process by quickly ruling out parameters that could not possibly be within the optimal region, maintaining theoretical guarantees while improving practical utility.

Key Insights

  • Shape Awareness: Unlike Hoeffding bounds, which assume a worst-case variance, or empirical Bernstein bounds, which can be loose for small samples, the proposed level-set method inherently accounts for the exact geometry of the distribution within the simplex.
  • Small Sample Advantage: The benefits of these exact regions are most pronounced in the small-sample regime. This is critical for sequential decision-making algorithms, where the initial exploration phase relies heavily on the tightness of confidence bounds to avoid suboptimal actions.
  • Prior Independence: The optimality of the minimum average volume is a robust property that does not depend on a specific Bayesian prior, making it a powerful frequentist tool.

Empirical Results

The authors validated their approach through simulations of a 5-arm bandit problem where each arm follows a 3-category probability mass function.

  1. Interval Tightness: For mean functionals, the proposed method consistently yielded tighter intervals than sub-Gaussian/Chernoff and empirical Bernstein bounds across sample sizes ranging from $n=10$ to $n=200$.
  2. Bandit Performance: In Best-Arm Identification tasks using the LUCB (Lower and Upper Confidence Bound) algorithm, the tighter bounds led to a dramatic reduction in sample complexity. The proposed method reached a median stopping time of approximately 120 samples, whereas Hoeffding bounds required ~350 samples and empirical Bernstein bounds required ~600 samples to achieve the same confidence level.

Limitations and Future Directions

The primary limitation of the exact method is its computational cost, $O(n^k)$, which becomes prohibitive as the number of categories or the sample size increases. While the KL-divergence outer bound mitigates this, the method is currently best suited for small-to-medium sample sizes where traditional asymptotic methods are unreliable.

Future research directions include extending these level-set techniques to construct confidence sets for nonlinear functions and generalizing the framework to broader measure spaces with conditional probability measures.

Summary updated

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 $\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.
BibTeX
@misc{malloy2020optimal,
  author = {Matthew L. Malloy and Ardhendu Tripathy and Robert D. Nowak},
  title = {{Optimal Confidence Regions for the Multinomial Parameter}},
  year = {2020},
  eprint = {2002.01044},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2002.01044},
}
Figure