Improved Distribution Estimation in $\ell_\infty$

Technical Summary: Improved Distribution Estimation in $\ell_\infty$

Problem Statement
The paper addresses the classical problem of estimating an unknown discrete probability distribution $p$ over a countable alphabet from $n$ independent and identically distributed (i.i.d.) samples. While extensive theory exists for $\ell_1$ and $\ell_2$ losses, the authors focus on the $\ell_\infty$ (sup-norm) loss, defined as $\|\hat{p} - p\|_\infty = \sup_{i \ge 1} |\hat{p}_i - p_i|$. This metric is critical in modern applications such as uniform calibration, anomaly detection, and goodness-of-fit testing where the largest coordinate-wise discrepancy triggers a response.

The central challenge is that while a uniform $O(1/\sqrt{n})$ risk decay holds for all discrete distributions, obtaining sharp, distribution-dependent rates and fully empirical bounds (those not requiring knowledge of unknown functionals of $p$) remains difficult. The difficulty is governed not merely by the support size but by the unknown tail profile of $p$. This work builds upon and extends the non-asymptotic study initiated by Kontorovich and Painsky (2025), specifically addressing open questions regarding fully empirical confidence bounds and the identification of the worst-case (least-favorable) distribution.

Methodology and Framework
The authors analyze the Maximum Likelihood Estimator (MLE), denoted as $\hat{p}$, where $\hat{p}_i$ is the empirical frequency of symbol $i$. The analysis relies on two primary theoretical frameworks:

1. Complexity Proxies: The work utilizes distribution-dependent complexity measures introduced by Kontorovich and Painsky (2025), specifically $v^*(p) = \sup_i p_i(1-p_i)$ and $V^*(p) = \sup_i p^\downarrow_i(1-p^\downarrow_i)\log(i+1)$, where $p^\downarrow$ is the non-increasing permutation of $p$.
2. Local Glivenko–Cantelli (LGC) Theory: To refine the understanding of distribution-dependent behavior, the paper incorporates sharp local Glivenko–Cantelli bounds. This involves analyzing two new functionals, $S(p)$ and $M(p)$, which capture different aspects of the tail behavior and variance structure of the distribution.
3. Decoupling and Reduction: For minimax analysis, the authors reduce the dependent multinomial sampling model to an independent Bernoulli model using decoupling inequalities, allowing the application of sharp characterizations available for independent variables (Blanchard and Voráček, 2024).
4. Empirical Plug-ins: To achieve fully empirical bounds, the authors replace unknown population functionals with their empirical counterparts (e.g., $\hat{v}^*$ and $\hat{V}^*$) and utilize concentration inequalities to bound the deviation between the empirical and true functionals.

Key Contributions and Results

• Minimax Rate and Least-Favorable Distribution:
  The paper resolves the structure of the worst-case expected $\ell_\infty$ risk. It establishes that the minimax rate scales as $\Theta(n^{-1/2})$. Crucially, it identifies a simple, fixed least-favorable distribution $p^\star = (1/2, 1/2, 0, \dots)$ that achieves this worst-case risk up to universal constants. This result answers an open question by demonstrating that the hardest instance for $\ell_\infty$ estimation exists on a two-point alphabet and does not require an $n$-dependent effective support size.

• Fully Empirical High-Probability Bound:
  The authors derive a high-probability deviation inequality for $\|\hat{p} - p\|_\infty$ that is fully empirical. The bound depends only on observable plug-in statistics ($\hat{v}^*$ and $\hat{V}^*$) and does not require knowledge of the unknown functionals $v^*(p)$ or $V^*(p)$. The bound adapts automatically to the unknown tail profile of $p$ while retaining the correct $\sqrt{\log(1/\delta)/n}$ behavior in the worst case.

• Refined Distribution-Dependent Regime:
  Using LGC functionals, the paper provides a more granular view of estimation error. It introduces $S(p) = \sup_j p^\downarrow_j \log(j+1)$ and $M(p) = \sup_j \frac{\log(j+1)}{\log(2 + \frac{\log(j+1)}{n p^\downarrow_j})}$.

  • $S(p)$ represents the "sub-Gaussian" part of the error, dominating when a block of coordinates carries sufficient mass for variance fluctuations to be the primary source of error.
  • $M(p)$ represents the "sub-gamma" or Poissonian part, capturing the impact of many low-probability symbols visible at sample size $n$.
    The paper proves that the estimation error is governed by the maximum of these two terms (scaled by $1/n$), illustrating three qualitatively different regimes: variance domination, tail domination, and highly spread-out profiles where both mechanisms yield small errors.

• Lower Bounds:
  The paper provides a minimax lower bound under a constraint on $V^*(p)$, showing that for any estimator, there exists a distribution with $V^*(p) \le V'$ such that the expected error is at least $c\sqrt{V'/n}$.

Significance and Claims
The paper claims to sharpen and extend the existing theory of $\ell_\infty$ distribution estimation in three specific directions:

1. Theoretical Resolution: It settles the question of the least-favorable distribution, showing it is a simple two-point distribution independent of $n$, rather than a complex, $n$-dependent structure.
2. Practical Applicability: By providing a fully empirical confidence bound, the work enables the construction of data-dependent guarantees without requiring prior knowledge of the distribution's tail profile.
3. Nuanced Understanding: The introduction of the $S(p)$ and $M(p)$ functionals offers a "regime picture" that explains when and why different tail behaviors dominate the estimation error, moving beyond global minimax rates to capture the interplay between variance and tail decay.

The authors report encouraging empirical results demonstrating that these bounds are informative in finite samples, though the primary contribution remains the theoretical refinement of the bounds and the identification of the extremal distributions.