Tight Bounds for Local Glivenko-Cantelli

08/03/2023

∙

by   Moise Blanchard, et al.

∙

0

∙

share

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.