Unverified

The log n Factor in Local Glivenko–Cantelli

For every sequence $p\in[0,1/2]^{\mathbb N}$ with $p_j\to0$ , is there a universal constant $C>0$ such that, for all sufficiently large $n$ ,

\Delta_n(p) \leq C\left( \sqrt{\frac{S(p)}n}+\frac{T(p)}n \right)?

Equivalently, is the $\log n$ factor in the known term $T(p)\log n/n$ necessary, or can it be removed?

Download

Abstract

Let $Y_j$ be independent $\operatorname{Binomial}(n,p_j)$ variables for a sequence $p_j\to0$ , and consider the expected uniform deviation of $Y_j/n$ from $p_j$ . A finite-sample upper bound contains a $\log n$ factor, while matching asymptotic lower bounds do not. Is this factor necessary, or can it be removed?

Background and progress

Let $p=(p_j)_{j\in\mathbb N}\in[0,1/2]^{\mathbb N}$ with $p_j\to0$ , and let $Y_j\sim\operatorname{Binomial}(n,p_j)$ independently. Define

\Delta_n(p)=\mathbb E\sup_{j\in\mathbb N}\left|\frac{Y_j}{n}-p_j\right|, \quad S(p)=\sup_j p_j\log(j+1), \quad T(p)=\sup_j\frac{\log(j+1)}{\log(1/p_j)}.

Cohen and Kontorovich proved that $\Delta_n(p)\to0$ if and only if $T(p)<\infty$ , and established, for $n\geq e^3$ ,

\Delta_n(p)\leq c\left( \sqrt{\frac{S(p)}n}+\frac{T(p)\log n}{n} \right)

for a universal constant $c>0$ [Cohen and Kontorovich, 2023]. They also proved the asymptotic lower bounds

\liminf_{n\to\infty}\sqrt n\,\Delta_n(p)\geq c\sqrt{S(p)}, \qquad \liminf_{n\to\infty}n\Delta_n(p)\geq cT(p).

Thus the upper bound is tight up to constants except for the $\log n$ factor.

The same quantity arises as the expected $\ell_\infty$ error of the empirical mean for a product distribution on $\{0,1\}^{\mathbb N}$ . The restriction to probabilities at most $1/2$ , converging monotonically to zero after reordering, loses no generality for this question.

Reference papers

Local Glivenko--CantelliDoron Cohen, Aryeh KontorovichConference on Learning Theory · 2023

The log n Factor in Local Glivenko–Cantelli

Coming soon

Organizer