The Empirical Mean is Minimax Optimal for Local Glivenko-Cantelli
Authors: Doron Cohen
Aryeh Kontorovich
Roi Weiss
Venue: ICML 2025 poster (2025)
Keywords: Maximum Likelihood Estimator
Local Glivenko-Cantelli
Symmetry
Statistical Estimation
Minimax
Machine Learning
Primary area: theory->learning_theory
TL;DR: A simple empirical mean is optimal in the Local Glivenko-Cantelli problem

Abstract: We revisit the recently introduced Local Glivenko-Cantelli setting, which studies distribution-dependent uniform convergence rates of the Empirical Mean Estimator (EME). In this work, we investigate generalizations of this setting where arbitrary estimators are allowed rather than just the EME. Can a strictly larger class of measures be learned? Can better risk decay rates be obtained? We provide exhaustive answers to these questions—which are both negative, provided the learner is barred from exploiting some infinite-dimensional pathologies. On the other hand, allowing such exploits does lead to a strictly larger class of learnable measures.

The Empirical Mean is Minimax Optimal for Local Glivenko-Cantelii
Doron Cohen Aryeh Kontorovich" Roi Weiss 2
Abstract
X μ are mutually independent), E Elp pll recovers the expression in (1). Despite its austere appearance, the binomial empirical process with independent coordinates Yj under -nom deviation already captures much of the richness of problem. Extensions to more general product distributions μ over [0, 1] are straightforward (Blanchard Voráček, 2024, Corollary 6) and the behavior under l, norms for < oo is considerably simpler (Proposition 7 ibid.). Finally, the in-expectation bounds are readily converted to high-probability tail bounds (Proposition ibid.), and all of the upper bounds stated for product measures hold verbatim for arbitrary correlations.
We revisit the recently introduced Local Glivenko- Cantelli setting, which studies distribution- dependent uniform convergence rates of the Em- pirical Mean Estimator (EME). In this work, we investigate generalizations of this setting where arbitrary estimators are allowed rather than just the EME. Can a strictly larger class of measures be learned? Can better risk decay rates be ob- tained? We provide exhaustive answers to these questions-which are both negative, provided the learner is barred from exploiting some infinite- dimensional pathologies. On the other hand, al- lowing such exploits does lead a strictly larger class of learnable measures.
For the purpose of analyzing (I), Cohen Kontorovich showed that there no loss of generality in restricting p to the set [0, 1.8 2.10- consisting of all p [0, 1 with Pj 0. They defined LGC c [o, 11N
2- as the family of p for which An - and showed that LGC consists of exactly those p n-000 for which
1. Introduction
Cohen & Kontorovich (2023) initiated the study of the lo- cal Glivenko Glivenko-Cantelli setting: laws of large numbers that uniform over function class but rather than being uni- versal over all distributions, feature a delicate dependence of the risk decay on the (local) sampling measure. This naturally led to the binomial empirical process: for a fixed E [0, 11 and each n E N, we have a sequence in- dependent Y, ~ Binomial(n, Pz). which are centered and normalized obtain Y, := n -y Pj- The object of interest is the expected uniform absolute deviation:
log(i + 1) T(p) = sup jEN (og(1))))
E 10,
I 2
(2)
is finite. They also characterized up constants the asymp- totic decay of A., (whenever Tpp) < oc) via the functional
S(p) = supp; log(i + 1), p [0, 2030: (3) jEN
I
establishing that (p) decays as Sp)/nn. Additional finite-sample bounds provided therein were tightened by Blanchard & Voráčck (2024) as follows:
A
E sup Y,l- JEN
(L)
(V S())
log(í + 1)
(p X1A
+ sup
121 n log 2 + log(i+1)
More generally, one could imagine fixing distribution μ on (0, sampling (L), ( ,..., (n) i.i.d. from jr, and estimating p= == E (1) via the Maximum-Likelibon Estimator (MLE) و = Σm= ((). In the case where μ a product measure (that is, the components of the vector
np;
if sup 2jp; 1,
j21
(1()) A
Pj.
J21
'Department of Computer Science, Ben-Gurion University of the Negev (BGU), Israel 'Department of Computer Science, Ariel University, Israel. Correspondence to: Doron Cohen <doronv @ bos...bu.aac.i..
otherwise.
In later work, Blanchard et al. (2024) extended some of the analysis to the much more difficult case where is not a product measure (i.e., the coordinates of ~ μ have correlations). In the present paper, we return to the product- measure case and investigate a different extension: How
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

The EME is minimax optimal for LGC
does An behave if rather than restricting the estimator to the MLEE P, we allow arbitrary estimators p?
2023, Proposition 1). Cohen & Kontorovich further moti- vated their choice of the foc norm as the most interesting of all the b, norms, in well-defined sense (see Blanchard & Voráček (2024, Proposition 7)). Blanchard & Voráček (2024) fully closed the gaps in the analysis of Cohen & Kon- torovich, and Blanchard et al. (2024) took the first nontrivial steps in analyzing non-product sampling distributions.
Actually, a bit of a refinmment in terminology is necessary. When considering (essentially) unrestricted classes of dis- 1 IN the Empirical Mean Estimator (EME) and the Maximum Likeli- hood Estimator (MLE) coincide. However, for more general families P C 11%. this is no longer the case: the like- lihood of given sample might be maximized over P by some i other than the EME. Hence, in the sequel, we shall be pedantic about this distinction, focusing on the EME as the more natural candidate.
tributions such as those parametrized by E [o, 2
Notation. The measure-theoretee subtleties of defining dis- tributions on (0, 1)" are addressed in Cohen & Kontorovich (2023). Our logarithms will always be base e by default; other bases will be explicitly specified. The natural numbers are denoted by N- = 21, and for k E N, we write [k] = fi E N: i S k}. The floor and ceiling functions, [4]. [1], map & E R to its closest integers below and above, respectively; also, & V vt:= max (s. 1), 8 A == min (s, t)- Unspecified constants such as c, c' may change value from line to line. We use superscripts denote distinct random vectors and subscripts to denote indices within a given vec- tor. Thus, if ( > ....., X are independent copies of X, then x denotes the jth entry of the ith copy.
Formally, an estimator ý is any mapping from ((0, 1)" to [0, 11, Any p e [0, 11 induces the product measure
=== ((p) = Bernoulli(p:) @ Bernoulli(p2) ..... (4)
on {0, 111......... ( x ((m) H. then these induce A, == E lp plloe. We say that a family of product distributions induced by P c [o, 1 is learnable by i if An -> O for each p E PP and just n-000 learnable if it is learnable by some p. (Since the sequence p fully determines the measure p(p), it is fitting to say that ø "learns" p- and hence also ppp)..
are sampled i..dd from
.....
When considering the EME as the sole estimator (as in previous works), no generality was lost in restricting the range of p to [0, 1
2 and assuming sequences monotonically decreasing to 0 (i.e., [o, 211))- The definitions of T and S in (2, 3) were based on this assumption. In this work, we will need their slightly generalized versions. With the convention & = min f2, 15--x) x), we define
This general setting immediately raises the natural questions: Can LGC be expanded to a larger learnable family via some estimator ş different from the EME? Can some estimator p achieve better decay rates for Ån than the EME?
log(i + 1)
Our contributions. Modulo some technical caveats, we resolve both questions above in the negative. If the learner is barred from exploiting some pathological quirks of the infinite-dimensiin setting, then essentially LGC as defined above is the largest Iearnable family (Theorem 2.1). Fur- thermore, the EME achieves the minimax risk decay rate over non- pathollogol distribution families (Theorem 2.2). Finally, in Theorem 2.3 we show that non-trivial extensions of LGC become possible once the restrictions are relaxed.
T(p) = inf sup
(5)
o:N-N jEN log(1 (1/Po))))
S(p) == inf suppo log(j + 1),
(6)
a: a:N-N jeN
for p E [0, 1J, where the infimum is over all permutations over N. Whenever pú + 0, a unique non-increasing permutation it exists, and it is easily seen to be the one achieving both infima above; thus, for p E [0, 2 20 definitions in (5, 6) coincide with those in (2, 3).
1 the
Related work. Estimating the mean of high-dimensional distribution from independent draws is among the most basic problems of statistics. Much of the earlier theory has focused on obtaining efficient estimators mn of the true mean m and analyzing the decay of ||m mll, as a function of sample size n, dimension d, and various moment assumptions on X (Catoni, 2012; Devroye et al., 2016; Lugosi & Mendelson, 2019a;b; Cherapanamjeri et al., 2019; 2020; Diakonikolas et al., 2020; Hopkins, 2020; Lu- gosi & Mendelson, 2021; Lee & Valiant, 2022). For d- dimensional distributions on {0, 1,dd, Chernoff and union bounds yield (H) X VIn(d + 1)/n for the EME, and
Any p [0, 11sh defines the product measure μر =u() as in (4). An estimator ğ and its induced deviation A, are defined just above (4), and the learnability of family P c [0, 1)" is defined just below it.
We say that a family P C [0, 1J is decaying if lim P3 = 0 3-000
for all p E P. For p E 10 and b E 13 we say that
p' p'= E 1gx
is b-reflection of p about } if
a simple information -thooreti argument shows that this is minimax optimall up to constants (Cohen & Kontorovich,
1 1
p'J bū bū
Pj 2
j jeN.
2'
2

---

The EME is minimax optimal for LGC
We say that P [0, 1| strongly symmetric about 1/2 if () b) E P for all P and b {-1.1}"
we have
inf sup Esup P6 - psl 2 1 (v/z v Q(1,)). pePa.t
The family LGC c [0, 2 was defined Cohen & Kon- torovich (2023) as the one learnable by the EME p. and char- acterized therein as consisting precisely of those p E [o, 2)M for which T(p) co. Since in this work do not restrict the range of [0, 2) define
JEN
where the infimum is over all estimators p that are based on ii.dd samples drawn from p. and
LGC
{pe [0, T(p) )0)
log 1 log log
=(t,s)=C
for T as defined in (5). It is straightforward to extend the arguments of Cohen & Kontorovich (2023) to show that LGC consists precisely of those p E [0, 1] for which the EME p yields A, +
Remark. The logarithmic factor and restrictions on the range of n are likely artifacts of the argument, which we kept streamlined for space and readability. We look forward to removing both in the extended version.
2. Main Results
Finally, we show that if the learner is allowed to "cheat" by exploiting the information contained in the infinitely many bits of each example (+),, then LGC can indeed be non-trivially expanded. Let us elaborate a bit on the nature of these exploits. The elements of LGC have a "generie," " unstructured flavor: knowing the values of pj for j E [N] reveals no useful information regarding the remaining, j > N; all the learner knows is that these must decay some power of j in order be in LGC. On the other hand, one might consider adjoining "structured" sequence to LGC, such as = (3 .... Because single X ~ ia provides a bit drawn from each of the Bernouli(p;)) ), the learner (as we show below) able to first test whether the unknown sequence has the given structure (in this case, whether it was generated by p = ()) and not, then reverts to the standard EME for learning the unstructured sequences in LGC.
Our first result may be informally summarized thus: "morally" speaking, LGC is the largest family that is learn- able by any fixed estimator.
Theorem 2.1 (expanding LGC). Suppose that P [0, 1] defines family of product distributions in (4) and fur- thermore
1. P is decaying
2. P is strongly symmetric about))
3. P is learnable.
Then P C LÉC.
Theorem 2.3 (Relaxing decay and symmetry). Define the family const c [0, 1 by
Remark. Strong symmetry about } forces the sequences in P to be "generic" and prevents the learner from beating the EME by exploiting some special structure. Note that this condition is very much absent in Theorem 2.3, where indeed such exploits become possible.
const
:(c. [0,
Then P LGC U const is learnable, meaning that there exists an estimator P such that (,) - 0fror all E P.
Having established that (modulo pathologies) LGC is the largest learnable family, next show that the EME is nearly minimax-optimal for this family.
Remark. The techniques of Theorem 2.3 are applicable considerably more broadly than just to the family Q = const. For example, the argument can be casily adapted to show that LGC U is learnable for any finite Q. The following proposition shows a nontrivial Q which strongly symmetric and learnable, implying that the decay condition of Theorem 2.1 is necessary.
Theorem 2.2 (Minimax bound). There exist universal con- stants c, C > 0 such that the following holds. For n E N and s, > 0 satisfying log
< I c-1, let
Pa.s = {p E 11 S(p) S T(P)
Proposition 2.4 (Relaxing decay). Let > 0 be universal constant, and define the family of distributions
Then, whenever
e' logn
< 5 -1 and
n
2 = PE P -
C Vi
C. log
2
Blog 4
f log
log
Then, Q is learnable.
3

---

The EME is minimax optimal for LGC
Open problems. Two natural directions for future study extensions of Theorems 2.1 and 2.3. For the former, it is likely that the conditions P are too stringent and can be significantly relaxed; in particular, requiring that P be decaying is quite probably unnecessary. Thus, we seek a larger family p' whose learnability implies p - L&C. Regarding Theorem 2.3, we again anticipate the existence of considerably richer families Q for which LGC U is learnable. One such family is proposed in the conjecture below.
where Y is the random sign vector and X (x(), ..... x(m) denotes the observed data.
Now
1 P(Y + y 1 X = 2)
= =PYY = y X = x)
PP(Y = y1 X = x).
PPY2 9/2 X x. V1 = y1)
F(Y: ys X Y1 -11 = 122
Conjecture. Let Q C [0, 1J be a countable family of sequences with the following property: for each n' E Ω there an E > and an infinite J c: N such that (g ofl > & for all j E J. Then LGC U Q is learnable.
Since the Y, are mutually independent, each of the factors above has the simpler form
3. Proofs
IP = yk
X = xz Y1 = y1.... x = 9k-1)
+P yk X z).
3.1. Proof of Theorem 2.1
Assume, for the sake of contradiction, that there exists estimator ş and family P C [0. 118 satisfying the condi- tions of the theorem, such that P is learnable by f but there exists pp E P LGC. Based on p". we will construct a family P C P and argue that A, (p) - cannot hold for all p E pt.
We conclude that the events E, (Y, & y3 XX] are mutu- ally independent. Thus
P(Y #
x=
Since P is strongly symmetric about 3. for any E P and any sign vector b E 1 the b-reflection p' (p. b) defined by p' = (p, - - +))++ +
= P
U JEN
Ej
also belongs to P.
N
Consider the following randomized experiment:
= lim
IP
Fj
N
1=1
Let Y = (Yi)jeN be a sequence of independent Rademacher random variables, i.c. IYY 1)
= -lim ON ...E. ..EN))
N
P(Y, 1)
Define (0) E 1 as the --reflection of p" about I 2, Pj
where the second equality holds by regularity of prob- ability measures (Kechris, 1995, Theorem 17.10), and oN : [0, 1j [o, is the inclusion-excllsion function defined inductively by a (z) and
(8) Yn(r) +
Generate independent draws X(), ...., ,().,))))))))....) E 10, from the product distribution (Y) as in (4).
a'+1( 22.... 2N+1) = =IN+1 + (1- 1N (2........
The assumption that Dj E [0, M incurs no loss of general- ity, since the decay condition implies that pj < 1/ will hold for all sufficiently large j. We ignore P ( 2. this would only decrease the estimation error A,,
11 since
By Kontorovich (2012, Lemma 4.2), ax is monotonically increasing in each argument. Hence, the optimal estimator may minimize each PPEE)) individually and so may define A, as the estimator for the j-th coordinate, where A₁ (0. 1] 1 - [0. 1] is any mapping from the j-th row of the data matrix to an estimate of / Let B, be the event that A, and p (Y) belong to different intervals, i.e., either Ay E [0, 11) and (X) E (1) 1] or vice versa. To establish lower bound on the error of any estimator, consider the
We follow the standard reduction from the harder problem of estimating ( the easier problem of recovering the sign vector y E (1,, 1 that defines the y-reflection pY)). By the Jeyman-Pearson lemma, an optimal estimator ý is one that minimizes the posterior probability of error, i.c.,
Ú arg min P(Y Fy X =x),
ve v=111

---

The EME is minimax optimal for LGC
minimax risk:
and for 1 S k J take the same step profile but with
additional bump position k
inf sup E sup A, Pyl pEP X jEN
9: j [J+ and j + k.
+
inf sup AAj 1 Y X JEN
Pj
q', j j= k,
0, j> ++1.
2 inf EE sup 1[ A Y JEN
1
2
The construction of these profiles is illustrated in Figure 1.
2 inf E sus 1Bb}}
A YX xxjEN JEN
- inf TP AYX Y.X
UB JEN
q
q
inf # A aEfo,1IM
IP
UB, Bj X x
/1 dPx(1)
JEN
min P(Y # 0 X xx))x(1)- 2 =E{0,1]8x= 1,1j
1
2
2
+
By the Neyman-Pearson lemma, the optimal choice of d according to the majority vote! of the vector (x) ,...,,,'" x In the event that (x(") ....., x("))
(J+1)
(1,1, 1), but 1 1² A p ) the estimator makes mis- take. The probability of such event, conditioned on the other random variables Xj: Yg where j' * j. is exactly (, Since we assumed p" & LGC and thus p" &f LGC, we have T = co. Since أ + O, we may assume with- out loss of generality that it is decreasing monotonically, By Cohen & Kontorovich (2023, Lemma 3), it follows that for all N. we have
9
0
3
1+1
J ++2
J
1
Σ (p)) = DC.
Figure I. Illustration of the step profile construction for (
(top)
and the special case for p p1)41) (bottom). Each bar represents the value of p) (k) at position j. Values are shown above the bars.
Since the events of ūú being wrong are mutually indepen- dent, the second CantelCat lemma implies that almost surely at least one of them will occur. follows that lim = (p() 2 1. contradicting the learnability assumption.
Note that for all i E [J [J+1] 1] have (1 - 110) lg' q). In addition, for k: J 1.
S(n(+t1)) = q log( J +
and
3.2. Proof of Theorem 2.2
T(b(++1)) log( (J 1)
log
We reduce the minimax lower bound problem finite set of hypotheses. For 2 < J E N and 0 < s o' < 1/2 to be chosen below, we consider J + 11 profiles [J + 1]. For J + we take the (k)) E [o, 11 for l: E
and for k [J].
(()(k)) max log(] + 1), of log 2}
step profile
and
T() = max
log(J log
log
g, j J - 1]. 0,
(J+1) Dj
log
j>J+1,
Given s S as in the Theorem statement, we choose E [0, f and J as
'The issue of optimally breaking ties or allowing randomized decision rules is somewhat delicate and is exhaustively addressed in Kontorovich & Pinelis (2019, Eq. (2.7)). In our setting, these do not affect probability of error.
t
and
log(J + 1) = t log
1 log
5

---

The EME is minimax optimal for LGC
Then
for an appropriate value of the constant C > 0.
S(p()+1)) [log(J
(J + +1) = 8,
(9) We analyze o' (q) for (q) satisfying (14) as in Blanchard et al. (2024) and consider two regimes for ((gllg)+hhggllll
T(b(++1))= log(J- +1)
t. (1+
log t
-1
For any 0 < S o S 2. we have
log
log log? 1
(q' g)² S h( + M(d(1a)) - 2(d' - q)² q'
(10)
(15)
9
Below we set o' 1 1/2 such that o' 2 and for all & E [V].
So, by the right inequality in (15).
)) s S(p(++1)) =8
9 (h(all9' (4)) + h(g (1))
and ()) S T(p L
(11)
d'(g)= -2))-921
V
2
Thus, p(t) E Pa,t for all & E [J + 1] and
9 [lgg(J +1)
4Cn
inf sup Esup F3 Psl
pEP,, JEN
S(pJ41)
2 inf max P [E(J+1] Xamg
E
lz(x,)
(12)
4Cn
8
(16)
To lower bound the right-hand side of (12) we apply the gen- eralized Fano method. For & E [J+1], let (k) = p(p(k) be the product measure over {0, 13 N as defined in (4) and note that Ex {X] (()) We denote by (((k.) the product measure of n independent copies of X ~ (e( We invoke Lemma 3.1 with the J J+1 1 measures (u1, (V.....,J++]) = (u(2., ..... "....,((++10)) (J++)))), the distance function p ||lloc and the parameters (()(kx)))
4Cn
In addition, by the left inequality in (15),
q' d'log(J+]
d S q +
2Cn
1/ v [oog(J +1)
S V
(v++/
2C'
Ex (X) (k)) for [J + 1]. Note that p(O(ultm)), 0(2))) = l4' - ql for all + de [J+ 1] and that
which implies
2
log (J + 1)
DKL (a( S n(hlalla')) + h(d'(111))))
q' Va++
2On
where
1 yogg( J + 1)
log( J + 1)
h(glld') = q log g + (1-
2 2) log o'
1 1- g
= + + 2/
+
2Cn
2Cn
Then Lemma 3.1 implies
= 1 1
log( (J +
log(J 1)
2Cnq
2Cng
inf max kE[J+1] X, Namuitiin)
E (I((Xn) - (A)) 1100
Since by assumption Can
Ct
c' log 2, we have
q 1
(n(blglla') + h(d (lg)) + log 2)
I Flog( 5)
that for sufficiently large constant e',
log(J +1)
(13)
d' I 9 glog(J + 1)
log 2
We now fix d'44) = 2 q to be the solution to the equation
This verifies (11) and establishes the term c/ 7 in (8).
(g)) + h(d(()))l)) log(J + 1) 2Cn
Next, we assume + 2 CVV. For any 0 S q S o' S 1/2 we have h(gllg') < h(q (l)) and for q' 2 9g, it holds that (see, e.g., Blanchard et al. (2024))
(14)
Below we verify that (11) indeed holds with this choice of (') Substituting (14) into (13), we obtain the lower bound
1 h(gllg) + h(g1)))))))))))))))))))))))))h <4
(17)
2
(((9)= (1
log([ + 1)/C + log
4
2
log(J + 1)
For 2 the solution x the equation x log x
(q)
1
log 2
satisfies x 2 log (Corless et al., 1996). Taking c > 0
sufficiently large such that
2
C
log 3
g'
('(4) q
log(J+++
12
2 = 20qm
log 2 (t)
>
2 e,
2Cns
2C
6

---

The EME is minimax optimal for LGC
we have that (() satisfies (14) if (q()) - q 8q and
As in the proof of Theorem 2.1, applying Lemma 3.2 with
(4)
log(J+1)
A
2G
log q
[+g(
{x/] (x.")...,,,)")) = (1, I,, 1), but - 13 + }
20'g
namely,
log(J~ J
+ +1)
where y, Bernoull((12) and Pj (1 - Pj), we get that the minimax rate is lower bounded by universal constant.
0 Yjp
d'(g) - 2
1og(J+1)
2Cn log
20
T(ps+1)
log
2On 22n
log
(J+()+1)
3.3. Proof of Theorem 2.3
20
T(p++1)
log !
We aim prove that the family
2Cn
log IOng"
P == LGCU ((c.c....) [0,
T(p++1)
is learnable by an estimator Pa. Choose some p E P. The general strategy is construct estimator that can dis- tinguish between cases where T(p) = oo and cases where T(p) < co, based on the sample.
4Cn
(1+
log
4Cn
log log
where in the last inequality we used the fact that 2cm I 1. Lastly, we verify that (4) is such that (11) holds, namely,
Step 1: Testing if T(p) = co. We begin by defining a test & to check whether T(p) = co. The idea is to check the first half of the sequence x x ....., x x()) are all ones and the second half are all zeros. Formally, the test function is defined as:
log < log(J+1), The left inequality in (17) implies that
log p(
log
(4 $ q C C for some constant C", Putting this and q : and log(J 1) = t tlog s. we have that (11)
holds if
& (xx(), (
x(1) =1 [lim Ej)
l log 4)
t flog ! log 2
+
l & log 9) log(1 ( +
Ons log (
12
where we define the event
This is satisfied when
Fg = { x = 0 for i S n
and x/10 = for i
n
2
2
log
Cs
Note that, for each j, we have
n
log
f logg
log
P P(E)) = p. n/2] (1 py)
p3) Tn/21
Finally, we consider the case where 1 2 We repeat the arguments in the proof of Theorem 2.1 to show that in this case the minimax rate is bounded from below by a constant. Taking any p* E Pe.e such that T(p")= 2 n, and assuming without loss of generality that p² is non-increasing, j be such that
and because {E,}, are independent, by the two Borell- Cantelli lemmas, + = 1 almost surely if and only if
Σ
pj In/21 (1 P.)
p)) 1n/21
oo.
The above sum can be estimated by the following sums,
log(1 1 + j¹)
T(p') 2
log(1 (1/0.)))
oc
Σ j=1
[n/2]
(1 pT) nn/2]
p 1n2] (18)
Then
(p3) >
T(()
Step 2: Consistency of the Test. We now show that the test tb is consistent. First, assume T(p) = co, which means T(p1o) xc, then by Cohen & Kontorovich (2023, Lemma 3), we have Σ 13 co for all n, then by (18) we have $- almost surely.
1=1
Σ
(5))
On the other hand, if (p) < oo, again by Cohen & Kon- torovich (2023, Lemma 3), we have Σド P3) < oo for large enough n, which means that for large enough n we have + = 0 almost surely, as before.
2
5'
N 2
1 3
7

---

The EME is minimax optimal for LGC
Step 3: Defining the Estimator. Once the test & has been applied, define the estimator Pn as follows:
ensures this probability vanishes. Thus, with high probabil- ity,
(1) 1. I (1), i xn)= 1, (1)
)
(V log k(n)
-pyl=O sup (px(1) -pyl= =0 jSk(n)
otherwise.
In words, if the test + indicates that T(p) = 0o, we use the average of all (i) (as this is consistent with the as- sumption that p is a constant sequence). If & indicates that T(p) < 00, we use the EME/ Pr. (j) directly.
For j k(n), since py is approximated by 1/2:
sup [pj 1/21 2 sup = (0( j>k(n)
jzk(n) Vj
Vi(n)
Step 4: Consistency of the Estimator. We now verify
that the estimator Pn is consistent.
Choosing k(n) (n) ensures this term vanishes. Thus, combining both terms.
If p E LGC, then (p) < oo, and the test & will eventually return 0. In this case, the estimator Pm (j) is simply the EME, which is known to be consistent for all E LGC. Therefore, Pr. + p loc as n + oo.
E (l - -Ploo = =0(1
log k(1)
(vkmm)
+0 Vi(n)
71
p (..) for some constant e E [0, 1), then T(p) = oc, and the test & will always return 1. In this case, the estimator (j) is the average of all (n) which, by the law of large numbers, will converge to c. Thus, pn( + as n + 0c.
which converges zero - Therefore, Q is learn- able.
3.5. Auxiliary lemmas
Conclusion.
The estimator P., correctly learns all distri- butions in the family LÔC u ((...,...) )::...:):.. : [0, 1]}, com- pleting the proof.
Lemma 3.1 (Yu (1997)). For 2 2, let 1e, 11, V2,..., be
collection of r probability measures with some parameter of interest ((v) taking values in pseudo-metric space (0, p) such that for all j + k.
3.4. Proof of Proposition 2.4
p(Olvs),0(vz)) a
Define the estimator (j) as follows:
and
(KslU;l S SB.
For indices j < k()), where k(n) is chosen later, estimate p3 using the empirical mean:
Then
a 1 (--8++ (1 log 2 2 inf max E ((0(Z), kElrl Z~ne
( logr
(n)
1 n
Σ
where the infimum is over all estimators 0 Z + O.
where x Bernoull((p))
Lemma 3.2 (Van Handel (2014) Problem 5.1a). If
For indices) j k(n), Pr. (J) 1/2.
A AN are independent events, then
Using Chernoff's bound, for any e <> 0.
[
N
(1 (1-o-) 1A ((Ae))
P
A k=1
P (1) - Pyl 2 c) < 2 exp( 22nc?).
k=1
Applying the union bound over j < k(n),
A Acknowledgements
The authors gratefully acknowledge financial support from the Data Science Research Center at BennGu University of the Negev (DSRC-BGU) through its 2025 Student Travel Support Program, which funded their participation in ICML 2025. This support is deeply appreciated. Roi Weiss was supported in part by the Israel Science Foundation (grant No. 2442/24)
P sup (p)()) pyl 2 20 < 2k(n)) exp(- 2nnc
jsk(n)
Choosing
6, 0 (v
log llgg(() k(n)
n
8

---

The EME is minimax optimal for LGC
Impact Statement
Diakonikolas, I., Kane, D. M., and Pensia, A. Outlier bust estimation with subgaussian rates via stability. Advances in Neural Information Processing Systems, 33: 1830-1840, 2020.
This paper presents work whose goal to advance the field of Machine Learning. There are many potential societal consequences of our work, none which feel must be specifically highlighted here.
Hopkins, B. Mean estimation with sub-Gaussian rates in polynomial time. The Annals of Statistics, 48(2):1193- 1213, 2020, doi: 10.1214/19-AOSI 1843, URL https: / //doi. org/ 10. 1 11211111-A011814
References
Blanchard, M. and Voráček, V. Tight bounds for lo- cal glivenko-cantell. In Algorithmic Learning Theory, ALT 2024, Proceedings of Machine Learning Research. PMLR, 2024.
Kechris, A. S. Classical Descriptive Set Theory. Springer- Verlag New York, 1995.
Kontorovich, A. Obtaining measure concentration from Markov contraction. Markov Processes and Related Fields, 4:613 2012.
Blanchard, M., Cohen, D., and Kontorovich, A. Correlated binomial process. In Agrawal, S. and Roth, A. (eds.), The Thirty Seventh Annual Conference on Learning Theory, June 30 July 2023, Edmonton, Canada, volume 247 of Proceedings of Machine Learning Research, pp. 551- 595. PMLR, 2024. URL https::tp/.ccc.. /ttp://///ooeeeeeeeeeeeoooo mlr. mlr.press/veal htte:///222///laaacca2222224 html.
Kontorovich, A. and Pinelis, I. Exact lower bounds for the agmostic wooball-approximmtely.comm learning model. Ann. Statist., 4765):2822-2854, 2019, ISSN 0090-5364. doi: A-011/666
(pac) machine
Lee, J. C. and Valiant, P. Optimal sub gausssan mean esti- mation in RR. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pp. 672-683. IEEE, 2022.
Catoni, O. Challenging the empirical mean and empirical variance: A deviation study. Annales de l'Institu Henri Poincaré, Probabilités et Statistiques, 48(4); 148 8- 1185, 2012. doi: 10. 10.121411-AHHP445 URL hwtphttps///c //doi.
org 100. 120.1224444 1214 / /11--1111-0 10/44/11AAIA -AIHP454
Lugosi, G. and Mendelson, S. Gaussian estimators of the mean of random vector. The Annals of Statistics, 47 (2):783 794, 2019a. doi: 10. 10.1214117-00S1639) URL https: /ttss://dooss
Cherapanamjeri, Y., Flammarion, N., and Bartlett, L. Fast mean estimation with sub-gaussian rates. Beygelzimer, A. and Hsu, D. (eds.). Conference Learning Theory, COLT 2019, 25-28 June 2019, Phoenix, AZ, USA, volume 99 of Proceedings of Machine Learning Research, pp. 786-806. PMLR, 2019. URL http: httt:://proceedingg www.mlrr.ssss.. v99 209/cherapanamjeer
121 111.....111111111111111
Lugosi, G. and Mendelson, S. Mean estimation and regression under heavy-tailed distributions: A survey, Found. Comput. Math., (455):145-11999 2019b. doi: 10. 10.1007/s110200-00199994477----1 URL https:/ /tte://ddo... /doi. org/10. 10.00..000//s//
01 09427-x.
html.
Lugosi, G. and Mendelson, S. Robust multivariate mean estimation: The optimality of trimmed mean. The An- nals of Statistics, 49(1):393 410, 2021. doi: 10.1214/ 20-A0S1961. URL https: / /oi.. otg//0..11111.... 20 AOS1A0195550 961.
Cherapanamjeri, Y., Tripuraneni, N., Bartlett, P. L., and Jordan, M. Optimal mean estimation without a variance. CoRR, abs/201 I. 12433, 2020. URL org/ abs brg/abs/220 /ttss/2211.0 2011. 12433.
Cohen, D. and Kontorovich, Local Glivenko-Cantelli. Conference on Learning Theory, Proceedings of Machine Learning Research, 2023.
Van Handel, R. Probability in high dimension. Technical report, PRINCETON UNIV NJ, 2014.
Yu, B. Assouad, Fano, and Le Cam. Festschrifi for Lucien
Corless, R., Gonnet, G., Hare, D., Jeffrey, D., and Knuth, D. On the lambertw function. Advances in Computational Mathematics, 5(1):329-359, 1996. ISSN 1019-7168. doi: 10. 10.1107/BFF211245500 URL http: / dx. doi. / 10. 1 00000000////27777
Le Cam: research papers in probability and statistics, pp. 423 423-435, 1997.
Devroye, L., Lerasle, M., Lugosi, G., and Oliveira, R. I. Sub- Gaussian mean estimators. The Annals of Statistics, 44 (6):2695 - 2725, 2016. doi: 10. 10.12144/1-A0S144M URL https: ///////oo/ /10 121 6- 440.
9

---

The EME is minimax optimal for LGC
A. Simulation Results
To support our theoretical findings, we present two sets of simulations. The first demonstrates the tightness of the lower bound Theorem 2.2, while the second highlights a specific setting where the simple average estimator outperforms the Empirical Mean Estimator (EME), complementing the results of Theorem 2.3.
A.1. Tightness of the Lower Bound in Theorem 2.2
The first simulation aims validate the theoretical bounds presented in Theorem 2.2. Specifically, we compare the empirical average supremum deviation A., with the theoretical predictions for different values of g (variance control parameter) and sample sizes
We consider six values of 0.1, q 0.2. 0.05, q 0.01, 0.005, and 0.002. For each configuration, empirical results are averaged over J = 100, 1000, and 10000 repetitions to ensure stability. The empirical deviations are plotted alongside theoretical predictions in a log-log scale to capture the decay behavior as n increases.
Figure 2 shows the results. The empirical deviations (dashed lines) closely follow the theoretical bounds (solid lines), confirming the tightness the lower bound in Theorem 2.2. As expected, larger values of lead to smoother empirical curves, emphasizing the role of averaging in reducing variance. Notably, the empirical deviations converge the theoretical decay rate as grows.
A.2. Performance Comparison: Theorem 2.3 Complement
In the second simulation, explore specific setting where the simple average estimator surpasses the performance of the EME. This complements the findings of Theorem 2.3 by demonstrating that allowing certain structured distributions can yield better decay rates with alternative estimators.
We evaluate the performance of the EME and the simple average estimator under six different distributions: uniform, triangular, Beta(2,2), exponential, 1/n-scaled, and Gaussian. For each distribution, we vary the number of trials k {10, 50, 100, 500) and compute the error as function the sample size n. The results, plotted on a log-log scale, are shown in Figure 3.
The plots reveal that the simple average estimator achieves lower error rates compared to the EME across all settings as k increases. This improvement is most pronounced for structured distributions like 1/n-scaled, Beta(2,2), and Gaussian, where the averaging process effectively captures the underlying structure. These findings corroborate the theoretical insights of Theorem 2.3, showcasing that the choice of estimator can significantly impact performance specific scenarios.
A.3. Discussion
The results of these simulations provide strong empirical support for our thcoretical findings. The first simulation confirms the tightness of the lower bound in Theorem 2.2, while the second demonstrates the practical advantages alternative estimators, as predicted by Theorem 2.3. These findings highlight the robustness and relevance of our theoretical framework for analyzing the Local Clivenno-Cantelli (I.GC) class.
10

---

The EME is minimax optimal for LGC
0.1
0.2
Average Supremum Deviation (log scalo)
Average Supremum Devitton [log scale]
10-1
10-1
Empirical (J-100)
Empirical (j-100)
10-2
Empirical (J-1000)
10-2
Empirical (|1000))
Empirical (J100000
Empirical (I-10000)
Theoretical (-100)
Theoretical (j-100)
Theoretical (J10000)
Theoretical (J10000)
Theoretical (=10000)
Theoretical (J-10000)
101
10a
10a
10a
10a
10a
Number Samples (n) [log scale]
Number samples scale]
0.05
= 0.01
Empirical (j1100)
Empirical ()-100)
Empirical ()10000
Empirical ()11000)
Average Supremum Doviation (l0g scale]
Theoretical (J1000)
Empirical (J100000)
Average Supremum Deviation [log scale]
Empirical (1100000)
Theoretical (j=100)
Theoretical (-1000)
Theoretical (J~1000)
Theoretical (=10000)
Theoretical (j=10000)
10-1-
10-1
1-
10-2
20
10a
10
101
10a
Number Samples (n) (log scale]
Number Samples (n) [log scale]
= 0.005
0.002
Empirical (J-100)
Empirical (j-100)
Empiriaal (J-0000)
Empirical (j-1000)
Average Supremum Deviation (log scale]
Theorstical (J-100)
Empirical (J-10000)
Average Supremum Deviation [lgg scale]
Theoretical (j-100)
Empirical (J100000)
Theoretical (J-1000)
Theoretical (J-1000)
Theoretical (J-10000)
Theoretical (j-10000)
10-1-
10"1-
10-2-
10-2
103
102
10a
10a
Number of Samples (n) [log scale]
Number of Samples (n) [log scale]
Figure 2. Average supremum deviation A. as a function of sample size n on log-log scale for varying y values (q 0.1, 0.2, 0.05, 0.01, 0.005, 0.002). Empirical results (dashed lines) are averaged over = 100, 1000, and 10000 repetitions and are compared to theoretical predictions (solid lines).

---

The EME is minimax optimal for LGC
Uniform
Triangular
10-
10"1
10
10
10
10"1
EMt trner (K=10)
Errer (k=10)
Averaging Froo (k=10))
Averaging Frim (km10)
Erer (K-50)
Avrraging troor (k-50)
Averaging trrer (kw50)
EME Ernor (k- (001
EME Eroo (k-100)
Averaging
Averaging (k=100)
EME Ermor (k-500)
EME Error (k-500)
trtrr (k=500)
Averaging Erior (km50u)
Sample Size (n)
Sample Size (n)
Exponential
10
10-1
10
10-2
10
10
EME Error (k-10)
EME Error (k-10)
Avetaging Ertor (km10)
Averaging Erion (km10)
(c-50)
Averaging Ener (k=30)
Averaging Eraor (km50)
EME Error (k-100)
EME Errr (k-100)
Avereging
Averaging
EMC Error (k-500)
EMI ertor (k-200)
Eror (k=500))
Averaging (k-500)
10-4
302
101
Sample Size (n)
Sample Size (n)
10
10-3
10-
10
EME Ererr (k- 101
Ener Uc-101
Averaging Error (k=10))
Averaging Error (k=10)
(K-50)
Averaging Error (0=
Averacing Erao (k=50)
EME Emerr (k-100)
EME Erro (k=100)
Averaging Eroo
Averaging
EME Ernor (k-500)
EME Error (k-500)
Emer lk- 500)
(k:500)
30
Sample Size (n)
Sample Size
Figure comparison between the EME and the simple average estimator for varying sample sizes n under different distributions: uniform, triangular, Beta(2,2), exponential, 1/n, and Gaussian. Results are plotted for E {10, 50, 100, 500) to illustrate the effect of averaging.
12


Reviews:
[{"review_id": "06I9Oic6IT", "reviewer": "Reviewer_cB2y", "summary": "This paper focus on the Local Glivenko Cantelli setting, which studies the uniform convergence rates of Empirical Mean Estimator (EME).", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your constructive feedback. We fully agree that presenting the key questions in an intuitive way is valuable. In our work, we carefully balanced the need to convey the underlying ideas with the necessity of rigorous technical proofs, given the inherent complexity of the Local Glivenko-Cantelli setting. We did strive to emphasize the logical development and core insights, but simplifying the exposition further proved challenging without compromising the correctness of our results.\n\n\n> While I appreaciate the technical rigor, I believe the main paper should focus on the intuition and logical development instead of technical proofs.\n\nIn the revision, we will be happy to expand upon the intuition and logical development.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "No.", "experimental_designs_or_analyses": "No.", "relation_to_broader_scientific_literature": "It should be worthwhile to focus on the key questions without introducing much technicality in the introduction section to make the topic more appealing to the broader scientific literature.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "While I appreaciate the technical rigor, I believe the main paper should focus on the intuition and logical development instead of technical proofs.", "other_comments_or_suggestions": "No.", "questions_for_authors": "No.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "XO6QBQJ4i4", "reviewer": "Reviewer_Frhk", "summary": "This paper investigates the mean estimation problem in the binomial empirical process. First, under mild technical conditions, it establishes that the LGC class, as defined in Cohen & Kontorovich (2023), is the largest class that is learnable by any estimator. Furthermore, it demonstrates that the empirical mean estimator (EME) achieves the minimax optimal rate. Finally, the paper provides examples of learnable classes that do not require a decaying assumption, broadening the scope of learnability beyond previously studied settings. Overall, this work offers a more comprehensive understanding of mean estimation in the binomial empirical process.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thorough and encouraging evaluation. We appreciate your recognition of the soundness and clarity of our theoretical contributions and proofs. Regarding the observation that the problem might appear somewhat standalone, we would like to emphasize that the original LGC paper by Cohen & Kontorovich (2023) provides a detailed discussion on its broader connections to machine learning, notably illustrating how the problem emerged from an analysis of the multiplicative weights algorithm. Uniform convergence in the Glivenko-Cantelli sense remains a cornerstone for deriving generalization bounds, which underscores the relevance of our investigation to the wider ML community.\n\n> The main limitation is that the problem is somewhat standalone and lacks strong connections to broader machine-learning topics. The paper could be strengthened by exploring its relationship with general empirical process theory and highlighting its relevance.\n\nIn the revision, we will elaborate upon the motivation and better situate the paper in the context of recent developments.", "claims_and_evidence": "Yes. The claim is clear and well-supported by theorems and proofs.", "methods_and_evaluation_criteria": "Does not apply.", "theoretical_claims": "This is a theory paper. While I did not verify every detail of the proofs, they appear sound at a glance. The contribution is solid.", "experimental_designs_or_analyses": "Does not apply.", "relation_to_broader_scientific_literature": "The problem is a bit standalone and a bit disconnected from broader machine learning literature.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "The paper is well-written, and the contribution is solid. \n\nThe main limitation is that the problem is somewhat standalone and lacks strong connections to broader machine-learning topics. The paper could be strengthened by exploring its relationship with general empirical process theory and highlighting its relevance.", "other_comments_or_suggestions": "No", "questions_for_authors": "No", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ijPlnNsko5", "reviewer": "Reviewer_TTqR", "summary": "The paper discusses the \"Local Glivenko Cantelli\" problem focusing on families of product distributions. There are three main results:\n\nThe first main theorem (Theorem 2.1) argues that LGC (the family of product measures that is learnable by the empirical mean estimator EME) is the largest family learnable by any fixed estimator, by showing any family of product measures that decays, is strongly symmetric about 1/2, and is learnable belongs to LGC.\n\nThe second main theorem (Theorem 2.2) argues that EME is nearly minimax-optimal by establishing a minimax lower bound for any estimator based on n i.i.d. samples from the latent distribution and comparing it with established bounds from results in the literature.\n\nThe third main theorem (Theorem 2.3) shows that LGC can be expanded if the learner can exploit structural knowledge of the problem. In these scenarios, some assumptions about decay and symmetry may be relaxed.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for your detailed and insightful evaluation and for your positive comments regarding the clarity of our main results and the rigor of our proofs. Below, we address your specific concerns:\n\n1. Regarding the assumption $\\dot{p}_j^*\\in[0,1/4]^\\mathbb{N}$, note that we can disregard any values where $\\dot{p}_j > 1/4$ without loss of generality. In fact, excluding these values only serves to decrease the supremum in our minimax analysis, which we have shown is lower bounded by 1/4. We will clarify this point further.  \n2. We acknowledge the importance of the optimality criteria provided by the Neyman-Pearson lemma. In our current draft, we refer to the lemma without additional discussion; we will expand on its role to clarify how minimizing the posterior error probability aligns with minimizing the expected $L_{\\infty}$ norm.  \n3. Concerning the inequality in Theorem 2.2, there is no need to assume $q'\\geq 2q$. The equality $\\|p^{(k)}-p^{(\\ell)}\\|_\\infty = |q'-q|$ follows directly from our construction, as it represents the maximum coordinate-wise difference between $p^{(k)}$ and $p^{(\\ell)}$.  \n4. We agree that the notation is inconsistent; $B_j$ should indeed be $E_j$, and this will be corrected.  \n5. We will also include an explicit statement of the referenced lemma from Cohen & Kontorovich (2023) to ensure clarity.\n\nAdditionally, we appreciate your suggestion to provide a description of the simple average estimator used in our simulations. Finally, we note your inquiry regarding the broader significance of our work; our study builds upon a well-established framework with direct implications in learning theory, and the technical challenges we address are of independent interest.\n\nWe thank you again for your constructive feedback.", "claims_and_evidence": "The paper is mostly theoretical, and the claims are clear. There are some questions about the proofs that are stated in a later section of the review. The paper explains the main results clearly and provides proof for each of the main theorems.", "methods_and_evaluation_criteria": "Since the paper is mainly theoretical, there are limited discussions about empirical methods or evaluation criteria. Some simulations are provided for the EME and the \"simple average estimator\", showing that the latter performs better, while both illustrate tightness of minimax bounds presented in Theorem 2.2.", "theoretical_claims": "I read the proofs for all three theorems but did not check all proofs rigorously. Some questions are listed below in the \"questions for authors\" section.", "experimental_designs_or_analyses": "There are not many experiments provided in the paper. It would be helpful to give a description of the simple average estimator, which was not included in the paper although it was used extensively to compare against the EME.", "relation_to_broader_scientific_literature": "Based on the descriptions in the paper, there were multiple related problem settings in the literature that have been explored with fruitful results. This paper identifies a new direction but borrows many tools and techniques from the literature.", "essential_references_not_discussed": "N/A.", "other_strengths_and_weaknesses": "Overall, I found the paper to be a nice read. The authors did a great job describing the problem setting and presenting the main results.\n\nOne small concern is that the main results are quite short -- descriptions, main results, and discussions were mostly within the first three pages, while the remaining main text were dedicated to proofs of main theorems. Considering there have been multiple papers in the literature on LGC, I think it would be helpful if the paper contains a section highlighting novelties in proof techniques that this paper introduces. It would also be great if the paper could contain some discussions of applications or implications to real-world scenarios.", "other_comments_or_suggestions": "One minor typo:\n\n1. Line 145 on the right side: \"Theorems 2.1\".", "questions_for_authors": "I have some questions related to proofs:\n\n**Proof of Theorem 2.1**\n\n1. I did not fully understand why the assumption $\\dot{p}_j^*\\in[0,1/4]^\\mathbb{N}$ incurs no loss of generality, especially when it is used to lower bound the minimax risk later.\n2. It might be worthwhile to elaborate what optimality criteria the Neyman-Pearson lemma gives to an estimator. For instance, how do we guarantee the optimal estimator $\\hat{y}$ that minimizes the posterior probability of error also minimizes the expected $L_\\infty$ norm? It would be helpful to clarify these since the argument of the contradiction builds heavily on analysis of the posterior probability.\n\n**Proof of Theorem 2.2**\n\n3. In line 260 on the left side, why is $\\|\\|p^{(k)}-p^{(\\ell)}\\|\\|_\\infty = |q'-q|$? Are we missing an assumption that $q'\\geq 2q$? A similar statement is also used later around line 283-284 on the left side.\n\n**Proof of Theorem 2.3**\n\n4. The definition of the test function is a bit ambiguous. Is it safe to presume $B_j$ in line 355-356 on the right side should be $E_j$?\n\n5. It would be helpful to provide statements referenced from literature. For instance, in Step 2., Lemma 3 of Cohen & Kontorovich 2023 are repeatedly referenced. It would be helpful to state the lemma.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethical_review_concerns": "N/A."}}, {"review_id": "FQtLDcf8UI", "reviewer": "Reviewer_4ufE", "summary": "In the local Glivenko-Cantelli setting, one seeks to learn an unknown distribution $\\mu$ over $\\{0,1\\}^\\mathbb{N}$ from samples. In the case where $\\mu$ is a product measure, as considered in this paper, it is fully described by a vector $p \\in [0,1]^{\\mathbb{N}}$. One natural estimate for $p$ is the empirical mean. In previous work, the performance of this estimator (in terms of the expected $\\ell_\\infty$ error) was tightly characterized. In particular, the class LGC (local Glivenko-Cantelli) of those $p$ for which this error vanishes as the sample size $n$ grows is tightly characterized. This work asks how this landscape changes if one allows alternative estimators (the answer: not too much).\n\nIn particular, if a class $\\mathcal{P}$ satisfying some rather mild regularity conditions is learnable by any estimator, they prove that $\\mathcal{P}$ is essentially a subset of LGC (up to a minor, natural tweak to this class). They also provide counter examples showing that these regularity conditions cannot be fully removed (although there are some interesting questions about relaxing them a bit). Moreover, they prove a minimax lower bound showing that the risk bound achieved by the empirical mean estimator cannot be improved too much (for any estimator).\n\n## Update after Rebuttal\nI maintain my positive score.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your constructive review. We appreciate your insights and address your key concerns below:\n\n1. Parameter Tuning and Proof Clarity (Theorems 2.2 and 2.3):\n   We recognize that parameter tuning in Theorem 2.2 is indeed the main challenge. We intend to offer clearer intuition on how these parameters are selected and why they yield the stated minimax bound. In Theorem 2.3, we will correct the minor issues concerning the estimator’s definition at Step 3 (e.g., using $\\hat{p}^n(i)$ instead of $\\hat{p}^n(j)$) and refine the discussion on uniform convergence to avoid confusion regarding a fixed $j$.\n\n2. Significance and Applications:\n   We understand your request for a broader context of potential applications of LGC. While our primary focus is the Local Glivenko-Cantelli framework, we will highlight possible connections to mean estimation in correlated or more complex settings. Where relevant, we will also discuss why simpler approaches do not suffice, underscoring the nontriviality of our techniques.\n\n3. Minor Corrections and Notational Consistency:  \n   We will fix the missing indices in the expression for $p^{(Y)}$ (page 4, bottom right) and replace $B_j$ with $E_j$ on page 7 (Step 1), ensuring accuracy and consistency throughout.\n\n4. Beyond Product Distributions:  \n   As for extending these findings to mean estimation in non‐product settings, note that $\\ell_\\infty$ mean estimation is not widely studied beyond the references cited in our introduction, and we are not aware of additional relevant work.\n\nWe appreciate your thoughtful review and hope these clarifications address your concerns.", "claims_and_evidence": "The proof of Thm 2.1 uses some careful applications of Neyman-Pearson and a lemma from a previous paper in this area. I did not dig into the previous proof of that lemma, but the argument otherwise looks sound.\n\nThe proof of Thm 2.2 begins with a natural construction and application of Fano's inequality. However, the exact tuning of the parameters requires a lot of care, and I think this could be better explained. I followed the individual steps of the proof, and, assuming that cited results are true, it appears sound. However, I would feel more comfortable vouching for correctness if there was more high-level discussion about parameter tuning.\n\nI think there are some easily fixed issues with the proof of Thm 2.3, which I mention below. But I am sure the result is true.\n\nProposition 2.4 has a direct and complete proof.", "methods_and_evaluation_criteria": "n/a", "theoretical_claims": "Yes, as discussed above. \n\nIn the proof of Thm 2.3, the estimator defined at Step 3 should involve a sum over $\\hat{p}_n(i)$ rather than $\\hat{p}_n(j)$, I believe. Moreover the discussion at Step 4 is of convergence for fixed $j$, when the question is really about uniform convergence over $j$. Without the need for a uniform guarantee there is no need to use the alternate estimator. Of course, it is clear that the authors understand this, and it is easy to fix.", "experimental_designs_or_analyses": "There are a few supporting plots in the Appendix. At a skim, they look good (but even if there were issues I do not think they play a critical role).", "relation_to_broader_scientific_literature": "The study of the local Glivenko Cantelli class was initiated pretty recently and this paper cites the relevant work that I know if, though I am not an expert on this specific problem. The existing work focused on the empirical mean estimator, whereas this work considers the limits of learnability using any estimator.", "essential_references_not_discussed": "n/a", "other_strengths_and_weaknesses": "The paper is generally well written and nice to read.\n\nAs someone familiar with the methods in this work and some of the earlier results on LGC, I have a bit of a hard time assessing significance of this paper's results. Are there any interesting applications of LGC to other statistical / learning theoretic problems? Also, I am not viewing any of the proof techniques as primary contributions in their own right. If there is any major technical difficulty to one of the proofs that would rule out simpler approaches, this should be highlighted.\n\nThe statement of Thm 2.2 is a bit funny. It seems that first string of inequalities on $n,s,t$ can be removed, since they appear again right afterwards. I think some further discussion is warranted on the gap between this LB and the UB. I also think the proof could use some more high-level discussion, as mentioned above.", "other_comments_or_suggestions": "On page 4, bottom right, there are some missing indices from the $p^{(Y)}$ vector on the second and third lines.\n\nOn page 7, in the first equation block of Step 1, $B_j$ should be $E_j$.", "questions_for_authors": "Suppose I am interested in mean estimation, rather than distribution estimation. What does known estimation landscape look like there beyond product distributions, and would any of your results translate?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "TgNV9772hM", "reviewer": "Reviewer_vocu", "summary": "Background: In this work the authors investigate the question of estimating densities on $\\lbrace 0,1\\rbrace^\\mathbb{N}$ where it is assumed that each index is independent and a sample has the form of a sequence of iid $Bern(p_i)$ random variables, so the density has the form $\\mu = \\prod_{i \\in \\mathbb{N}} \\mu_i$, from iid samples of $\\mu$. The authors are interested in the estimation loss of $\\Delta_ n= \\mathbb{E}\\Vert p - \\hat{p}\\Vert_\\infty$. Its not hard to see that without any assumptions on $(p_i)^\\infty_{i=1}$, one cannot control $\\Delta_n$ for any estimator, and especially not using the empirical PMF (EME). Previous work has looked into this and established a class of sequences $\\mathsf{LGC}$ where the $\\Delta_n$ can be bounded for the EME. In particular sequences $\\mathsf{LGC}$ are sequences of $[0,1]^\\mathbb{N}$ where all entries are less than or equal to 1/2, $p_i \\downarrow 0$ and $(p_i)_{i=1}$ must go to zero a certain rate ((2) in the paper). \n\nContribution: In this work the authors look at relaxed versions of the above setting by considering estimators other than EME and larger classes of densities. The larger class of densities they look at a class that is similar to $\\mathsf{LGC}$, which we will call $\\mathcal{P}$. In this $\\mathcal{P}$ the authors relax $p \\in [0,1/2]^\\mathbb{N}$ to $p \\in [0,1]^\\mathbb{N}$ and instead of sequences going to zero they must concentrate near $\\lbrace 0,1 \\rbrace$ as $i\\to nfty$: so $1/2- |p_i-1/2| \\infty$, and that, for all $p \\in \\mathcal{P}$ fliping any number of entires (finite or infinite) about 1/2 (e.g. 0.1 \\to 0.9) also lies in $p$. In Thm 2.1 the authors show that any learnable set of $\\mathcal{P}$ must have a decay of $1/2- |p_i-1/2| \\infty$ at the same rate as $\\mathsf{LGC}$ thereby tightly delineating the boundary of this expanded collection of densities and showing that this expanded $\\mathsf{LGC}$ in some sense contains all learnable densities. In Thm 2.2 they show that EME is nearly minimax optimal for learning $\\mathsf{LGC}$. I would call these the _core_ results of the work, with 2.3 and 2.4 exploring the boundaries of the setting a bit more.\n\n## Update after rebuttal\n\nI have raised my score by one. While I appreciate the clarifications provided in the rebuttal, I still find the contribution to be relatively modest for a purely theoretical result. It is uncommon for a theory paper to present a complete proof within the main text, which suggests a limited depth. Although the significance remains somewhat unclear in my view, the rebuttal has helped to improve my assessment in that regard. I would strongly recommend that the authors include more context regarding the practical implications (or potential practical implications) of their work.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thorough evaluation. We address your concerns below:\n\n1. Relevance and Venue Suitability  \n   We recognize that our work is theoretical. However, uniform convergence in the Local Glivenko-Cantelli sense is fundamental to learning theory, informing both risk bounds and distribution‐estimation methods. While we considered submitting to a more theory‐focused venue such as COLT, we also believe there is an audience at ICML that values rigorous foundational work in ML.  We can point to dozens of papers published in ICML at a comparable level of theoretical abstraction.\n\n2. Minor Theoretical / Textual Points  \n   - Line 188 (right): We agree that $\\alpha_1(x)$ should be $\\alpha_1(x)=x$.  \n   - Line 197 (left): We will justify the assumption more rigorously.  \n   - Definition Timing: We will introduce $\\mu^{(k,n)}$ earlier for clarity.  \n   - Line 44 (left): We will correct the alignment with $\\mathbb{E}X^{(1)}$.  \n   - Line 121 (left): We will replace “morally” with a more precise term.  \n   - Lines 144 (right) vs. 158 (right): We acknowledge the apparent contradiction concerning the necessity versus the stringency of the decay condition. We do believe the condition can be replaced with weaker assumptions in certain scenarios, and we will clarify this nuance.\n\n3. Broader Motivation and Applications  \n   Although the problem may appear standalone, it initially arose from analyzing practical algorithms, as detailed in the Local Glivenko-Cantelli paper by Cohen & Kontorovich (2023), which stems from the multiplicative weights method. Additional ties to CDF estimation are found in the work of Blanchard & Voráček (2024), where a modified Dvoretzky-Kiefer-Wolfowitz (DKW) approach is employed. Given the inherent space limitations of a conference paper, we chose to prioritize presenting novel results over a recapitulation of well-established motivation in recent literature. That said, we take this critique to heart and will expand upon the motivation -- including genuinely \"applied\" ramifications -- in the revision. In particular, we will delve into the original motivation behind the LGC question: Multiplicative Weights algorithm for online learning or solving a repeated zero-sum game, with a distribution-dependent, dimension-free dependence on the number of \"experts\".\n\nWe appreciate your feedback and hope these clarifications address your concerns while underscoring both the importance and rigor of our contributions.", "claims_and_evidence": "N/A, the work is purely theoretical.", "methods_and_evaluation_criteria": "N/A, the work is purely theoretical.", "theoretical_claims": "I checked the proofs Theorems 2.1 and 2.2 somewhat carefully and did not find any significant issues although I admittedly did not do a 100% assiduous check of these proofs, e.g., check the references or double check every single step of algebra. The proof techniques are very standard, in a setting that isn't terribly delicate, and the general techniques and results align well with what one would expect in this setting. That being said, I think there may be a few (non-critical) issues.\n\n* I think there may be a small error on l. 188 right. Should \"$\\alpha_1(x) = 1$\" instead be \"$\\alpha_1(x) = x$\"? For clarity I would just write $\\alpha_1(x_1) = x_1$. My understanding is that we want to write $P(\\cup E_i)$ as the $P(E_1) + P(E_1^C\\cap E_2) + P(E_1^C \\cap E_2^C \\cap E_3) + \\cdots$, where we replace the intersects with products due to independence, in which case we want $\\alpha_1(P(E_1)) = P(E_1)$.\n\n* Line 197 left: I agree that this assumption should be nonproblematic, but I think this should be dealt with rigorously.\n\n* $\\mu^{(k,n)}$ is defined three sentences later. Please introduce this before or immediately after using it.", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "This work is an extension of a line of research that was started very recently on estimating densities on infinite bit strings, where all the bits are independent. Judging from the recent research this is, surprisingly, a setting that has only been explored recently. Beyond this it is difficult for me to contextualize this more. This work seems to be a natural extension of discrete density estimation to an alphabet that is uncountable. The rates achieved match the well known $1/\\sqrt{n}$ rate for estimation over a finite or countable alphabet. Naturally we need some regularity conditions (functions T and S) to make this problem tractable. This work relaxes the regularity condition and shows that a previous work was minimax optimal, which is always nice to know.", "essential_references_not_discussed": "This seemed fine to me.", "other_strengths_and_weaknesses": "There are a few issues with this work:  \n\n- While I personally appreciate fundamental questions about learnability, I don’t think this topic is a good fit for ICML. This paper extends work from a previous COLT paper, which seems like a more appropriate venue. The broader significance for the ML community is quite limited—I struggle to see any practical applications or significant implications beyond a purely academic exploration of density estimation. Theory papers at ICML should either offer insights relevant to practitioners or shed light on important settings, and this work does neither.  \n\n- The proofs are fairly standard. If the paper introduced a genuinely novel technique or a powerful new idea, it might justify acceptance despite its lack of practical impact. However, everything here looks quite routine to me.", "other_comments_or_suggestions": "- l. 44 left: Fix aligment with $\\mathbb{E} X^{(1)}$.\n- l. 121 left: \"morally\" sounds very strange to me here.\n-l. 144 right vs 158 right: I think I'm just missing an implication of your results but it see \"implying that the decay condition of Theorems 2.1 is necessary.\" and \"Two natural directions for future study are extensions of Theorems 2.1 and 2.3. For the former, it is likely that the conditions on P are too stringent and can be significantly relaxed; in particular, requiring that P be decaying is quite probably unnecessary.\" Which seem to contradict each other. Maybe this should be elaborated on a bit.\n\nI don’t see any major issues with the work itself, but the results seem like such a poor fit for ICML that I was considering giving it a 1 (Reject). As someone who regularly submits highly theoretical papers to major ML conferences, I would expect this work to receive virtually no attention in this venue. It would likely have much more impact at COLT or another more topically appropriate venue, such as ITA.", "questions_for_authors": "My main question is: why should the broader ML community be interested in these results? Does this type of estimation problem arise in any important setting? From the name, I assume there’s some connection to CDF estimation, but the link isn’t clear to me. I’m actually surprised by how little motivation is provided, especially for an ICML paper.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: As described by the reviewers, the paper presents new important results for the estimation of the mean in binomial empirical processes. The paper provides a significant theoretical contribution for the study of uniform convergence of mean estimation.

Some reviewers have pointed out the somehow unclear connection with a broader machine learning community. I would like to encourage the authors to further describe the relevance of the results presented for general machine learning methods, in particular for more general empirical processes. In that sense, the authors can update the paper based on the discussions with the reviewers during the rebuttal.
Decision: Accept (poster)