The following problem was considered in Cohen and Kontorovich, "Local Glivenko-Cantelli", https://arxiv.org/abs/2209.04054, to appear in COLT 2023 (henceforth, CK'23).
Let $Y_j$, $j\in\mathbb{N}$ be a sequence of independent $\operatorname{Binom}(n,p_j)$ random variables, where $n\in\mathbb{N}$ and $1/2\ge p_j\downarrow 0$ as $j\to\infty$. Since $\mathbb{E} Y_j=np_j$, let us consider the centered, normalized process $\bar Y_j:= n{^{-1}} Y_j-p_j $.
Finally, we define $\Delta_n$ to be the expected uniform absolute deviation: $$ \Delta_n := \mathbb{E}\sup_{j\in\mathbb{N}}|\bar Y_j|. $$
CK'23 gave an exact characterization of the $p\in[0,{\frac12}]^{\mathbb{N}}_{\downarrow0}$ (that is, $p\in[0,{\frac12}]^{\mathbb{N}}$ with $p_j\downarrow 0$) for which $\Delta_n\to0$ as $n\to\infty$. Namely, they defined the functional $$ T(p) := \sup_{j\in\mathbb{N}}\frac{\log (j+1)}{\log(1/p_j)} . $$ and showed that $\Delta_n\to0$ iff $T(p)<\infty$. They also gave the finite-sample bound $$ \Delta_n \le c\left( \sqrt{\frac{S(p)}{n}} +\frac{T(p)\log n}{n} \right), \qquad n\ge \mathrm{e}^3 \qquad(*) $$ where $c>0$ is an absolute constant and $$ S(p) := \sup_{j\in\mathbb{N}}p_j\log (j+1). $$ We conjecture that the $\log n$ factor in $(*)$ is superfluous. This conjecture is motivated by the asymptotic lower bounds $$ \liminf_{n\to\infty} \sqrt n \Delta_n \ge c\sqrt{S(p)}, $$ $$ \liminf_{n\to\infty} n \Delta_n \ge cT(p) , $$ where $c>0$ is a universal constant. This shows that beyond the conjecturally removable $\log n$ factor, $(*)$ is tight up to constants.
Open problem. Is the $\log n$ factor in $(*)$ necessary, or can it be removed?
UPDATE 21-Jul-2023. This was presented as an open problem at COLT'23: https://proceedings.mlr.press/v195/cohen23b.html
Within days of the announcement and independently of each other, Moïse Blanchard, Václav Voráček, and Jaouad Mourtada obtained essentially the same substantial improvement. Formally, their results show that there is an absolute $c_1>0$ such that for any constant $c>0$ there is an $n_0$ such that for all $n>n_0$ there is a sequence $p\in[0,{\frac12}]^{\mathbb{N}}_{\downarrow0}$ for which $$ \Delta_n(p) > c\sqrt{\frac{S(p)}{n}} + c_1\frac{T(p)\log n}{n\log\log n}. \qquad(**) $$
This certainly dashes any hope of removing the $\log n$ factor in $(*)$ entirely; the best one could aim for is replacing it by $\log(n)/\log\log(n)$.
This raises a number of fascinating questions. First: Is there a fixed sequence $p_j$ (i.e., independent of $n$) for which $$ \liminf_{n\to\infty} \frac{n\log\log n}{\log n} \Delta_n \ge cT(p) , $$ where $c>0$ is a universal constant?
Second: Is there a functional $\tilde T(p)$ and a monotonically increasing $\varphi:\mathbb{N}\to \mathbb{N}$ such that $$ c\tilde T(p) \le \liminf_{n\to\infty} \varphi(n) \Delta_n \le \limsup_{n\to\infty} \varphi(n) \Delta_n \le c'\tilde T(p) $$ for absolute constants $c,c'>0$?
UPDATE 25-Jul-2023. We congratulate Moïse Blanchard on resolving the gap entirely, by exhibiting a $p$ for which $$ \Delta_n(p) > c\sqrt{\frac{S(p)}{n}} + c_1\frac{T(p)\log n}{n} $$ (all constants and quantifiers as in $(**)$).
Additionally, it has been pointed out to us by Moïse, Václav, Jaouad that the "lower bound" $ \liminf_{n\to\infty} n \Delta_n \ge cT(p) $ is trivial, since for nontrivial $p$, $\Delta_n$ will be at least $1/\sqrt n$ for $n$ large enough, meaning that $\liminf_{n\to\infty} n \Delta_n =\infty$. We have corrected this with the following non-trivial lower bound: Theorem (Cohen, K., 2023): There is an absolute constant $c>0$ such that $$ \Delta_n(p) \ge c\left(1\wedge\frac{T}{n}\right), $$ for all $n\in\mathbb{N}$ and $p\in[0,{\frac12}]^{\mathbb{N}}_{\downarrow0}$.
Thus, currently, the two open questions are:
Is there a fixed sequence $p_j$ (i.e., independent of $n$) for which $$ \Delta_n(p) \ge c\left(1\wedge\frac{T\log n}{n}\right), $$ for some $c>0$?
Is there a functional $\tilde T(p)$ and a monotonically increasing $\varphi:\mathbb{N}\to \mathbb{N}$ such that $$ \Delta_n \le c\left( \sqrt{\frac{S(p)}{n}} +\frac{\tilde T(p)}{\varphi(n)} \right) $$ and $$ \Delta_n(p) \ge c'\left(1\wedge\frac{\tilde T(p)}{\varphi(n)}\right), $$ for absolute constants $c,c'>0$ and all $n\in\mathbb{N}$, $p\in[0,{\frac12}]^{\mathbb{N}}_{\downarrow0}$?
