Tight Bounds for Local Glivenko-Cantelli
This paper addresses the statistical problem of estimating the infinite-norm deviation from the empirical mean to the distribution mean for high-dimensional distributions on {0,1}^d, with potentially d=∞. Unlike traditional bounds as in the classical Glivenko-Cantelli theorem, we explore the instance-dependent convergence behavior. For product distributions, we provide the exact non-asymptotic behavior of the expected maximum deviation, revealing various regimes of decay. In particular, these tight bounds recover the known asymptotic sub-Gaussian behavior, and demonstrate the necessity of a previously proposed factor for an upper bound, answering a corresponding COLT 2023 open problem.
READ FULL TEXT