Uniform Mean Estimation for Heavy-Tailed Distributions via Median-of-Means
Authors: Mikael Møller Høgsgaard
Andrea Paudice
Venue: ICML 2025 poster (2025)
Keywords: Median-of-Means
Uniform Convergence
Heavy-Tailed Distributions
Primary area: theory->learning_theory
TL;DR: In this work we provide upper estimates to the sample complexity of Median-of-Means at performing uniform mean estimation.

Abstract: The Median of Means (MoM) is a mean estimator that has gained popularity in the context of heavy-tailed data. In this work, we analyze its performance in the task of simultaneously estimating the mean of each function in a class $\mathcal{F}$ when the data distribution possesses only the first $p$ moments for $p \in (1,2]$. We prove a new sample complexity bound using a novel symmetrization technique that may be of independent interest. Additionally, we present applications of our result to $k$-means clustering with unbounded inputs and linear regression with general losses, improving upon existing works.

Uniform Mean Estimation for Hleay--Talle Distributions via Median-of-Means
Mikael Møller Høgsgaard
Andrea Paudice
Abstract
& Yudin, 1983; Jerrum et al., 1986; Alon et al., 1996). Its popularity is largely due to its simplicity and efficiency. In- deed, its computation only requires splitting the sample into K batches, computing the sample mean in each batch, and then returning the median of these sample means, with an overall runtime that is quasi-linear in the number of obser- vations. Notice that the user is only required to specify the number of batches, which should be of order (og(1/6) for optimal performance.
The Median of Means (MoM) is a mean estima- tor that has gained popularity in the context of heavy-tailed data. In this work, analyze its performance in the task of simultaneously esti- mating the mean of each function in class F when the data distribution possesses only the first p moments for p (1, 2]. We prove new sample complexity bound using a novel symmetrization technique that may be of independent interest. Ad- ditionally, we present applications of our result to memns clustering with unbounded inputs and linear regression with general losses, improving upon existing works.
In this work, we analyze the performance of the MoM esti- mator in solving the following significant generalization of the mean estimation task, a problem typically referred to as uniform convergence. Given set of real-valued functions F over a domain X, and distribution supported over X' we consider the problem of estimating, simultaneously for each f E F, the mean juf) [[ from i.i.d. sample X ~ DD' generated from D. In particular, our goal is to estimate the sample complexity of the MoM estimator, i.e., the smallest sample size n² = r2(E, F) that suffices to guarantce that for all E, 5 E (0, 1) and n 2 n", the following holds:
1. Introduction
The problem of estimating the mean of random variable from finite sample of its i.i.d. copies is fundamental in statistics and machine learning. When the random variable has exponentially decaying tails, the sample mean exhibits optimal or near-optimal performance. In particular, for E, E (0, 1), it is known that POLYLOG(1/00) (1/))/ samples suffice to obtain an E-close estimate with probability at least 1 8. Recent studies have shown that heavier-tailed distri- butions, possessing only the first p moments for p E (1, 2]. better suited to model several important cases, includ- ing but not limited to, large attention and language models (Zhang et al., 2020; Zhou et al., 2020; Gurbuzbalaban et al., 2021; Gurbuzbalaban & Hu, 2021), certain applications in cconometrics (Bradley& & Taqqu, 2003) and network science (Barabási, 2016), and some classes of extremal processes (Nair al., 2022). Under this model, the sample mean suffers from sub-optimal performance with a polynomial de- (MoM)
P X~D"
supi MoM(f, -M()) JEF
S 21 (1)
Uniform convergence has fundamental applications in ma- chine learning. First, given an estimator satisfying (1), one can learn Fy minimizing O(ʃ, X) over F. Notice that if θ is the sample mean, this corresponds to the standard Empirical Risk Minimization (ERM) paradigm. Second, such an estimator can be used to estimate the risk of any function in F using the same data as for training. This is particularly useful when a test set cannot be set aside, or only an approximate solution to the empirical problem can be computed. Third, as the sample complexity of 9 features dependence on some complexity measure of F, it can be used to perform model selection, i.e., to select class of functions for the learning problem at hand before having a look at the data.
pendence on 1/6 (Catoni, 2012). Median-of- is a mean estimator that provides optimal performance guar- antees even under heavy-tailed distributions (Nemirovskij
'qqual contribution 'Department of Computer Science, Aarhus University, Denmark. Conresoondence Mikael Møller Høgsgaard boogsgaard@cs.au.kk.. Andrea Paudice <apau- dice@ ck..
Contributions.
We provide the following contributions.
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
We show that, upon F admitting a suitable distribution-ded -eabbdden--deeeddent approximation of size Ne (1011)) where up is a uniform upper

---

Uniform Mcan Estimation for Heavy-Tailed Distributions via Median-of-Means
bound to the Lp norm of the functions in F, the sample complexity of the MoM estimator is most of order (11//=)))/<=-)) log(NN(e, (tp///)//(/>1)))))
scales (Alon et al., 1997; Bartlett al., 1996; Colomboni et al., 2025). In particular, the best known upper bounds on the sample complexity of the sample mean are of the order of E - + log( 1 (/))), where fat, denotes the fat- shattering dimension of F at scale e.
Specifically, we require that: given E, 8 > 0 and m E N, there exists a finite set ml) of size at most ND(E, m) s.t. for a large enough K, with probability at least ô the functions in F can be s-approximated on most of the x batches of i..dd random samples We argue that this condition
The variant of the uniform convergence problem considered in this work is a special case of the formulation given in (Oliveira & Resende, 2023) except we don't consider ad- versarial contaminations. Differently from our work, the authors in (Oliveira & Resende, 2023) analyzed the perfor- mance of the trimmed mean with a focus on the estimation error. Their bounds feature a dependence on a quantity related to Rademacher complexity (Bartlett & Mendelson, 2003). Similar results, but in the more restrictive case of p E (2,3), have also been obtained by (Minsker, 2019), who considered different class of estimators interpolat- ing between the Catoni is estimator (Catoni, 2012) and the MoM. The estimation error of the MoM has been studied in (Lugosi & Mendelson, 2019; Lecué et al., 2020) for 2. These works also feature a dependence on a quantity related to Rademacher complexity of F. Compared to this line of work focussing on the estimation error, our focus is on the sample complexity and is thus more aligned with the results discussed earlier in this section of (Alon et al., 1997; Bartlett et al., 1996; Colomboni et al., 2025). We notice that the Rademacher Complexity depends on the sample size, and thus it is sometimes problematic to derive an explicit sample complexity bound from an estimation error bound. Taking a sample complexity perspective allows for coping with function classes that are otherwise difficult to handle through the Rademacher Complexity such as k-means clus- tering with unbounded input and center spaces, and linear regression with general continuous losses. In that respect, we see our results for = 2 as a complement to these works. We remark that our proof technique differs from the bounded difference arguments proposed in (Lugosi & Mendelson, 2019; Lecué et al.. 2020), and instead is based novel symmetrization argument that we believe may be of independent interest. In contrast, while (Oliveira & Resende, 2023; Minsker, 2019; Lecué et al., 2020) consider both heavy-tailes distributions and adversarial contamina- tions, in this work, we focus exclusively on heavy-tailed distributions.
Xo, X1, X2 of size on F is mild, and in addition to capture the canonical case of functions with bounded range, it also captures important classes of unbounded functioon.
To illustrate this we show that our result applies to two important class of unbounded functions. First, we prove a novel relative generalization error bound for the classical k-means problem that, compared with prior work, features an exponential improvement in the confidence term 1/6. Second, we use the MoM estima- tor to derive sample complexity bounds for a large class of regression problems. Our sample complexity bound only requires continuity of the loss function along with bound on the norm of the weight vectors. We also provide a more refined bound in the more specific case of Lipschitz losses, Moreover, our sample complex- ity bounds match the known results for exponentially tailed distributions, only assuming the existence of the p-th moments for p E (1,2].
To derive the main result, we introduce a novel sym- metrization technique based on the introduction of an additional ghost sample, compared to the standard ap- proach using only one ghost sample. While the first ghost sample is used symmetrize the mean, the sec- ond ghost sample is used to symmetrize the MoM. Analyzing two ghost samples simultaneously requires non-trivia modifications to the canonical discretiza- tion and permutation steps. The new discretization step allows for relaxing a uniform approximation over the functions to an approximation at the sample mean level, only requiring most of the sample means to be approx- imated, which is desirable feature when dealing with unbounded functions and heavy tailed data.
2. Related Work
3. Sample Complexity Bound
The study of uniform convergence for classes of real-valued functions is fundamental topic in statistical learning theory. In the special case of binary-valued functions, complete (worst-case) characterization is provided by the Vapnik- Chervonenkis dimension of the class (Vapnik & Chervo- nenkis, 1971). When the range of the functions in F is bounded within an interval, the problem is known to be solved by the sample mean as soon as the fat-shattering dimension (Kearns& & Schapire, 1994) of F is finite at
In this section, we describe our main result and provide a sketch of its proofs (we refer to Appendix B for the details).
3.1. Notation
We will use boldface letters for random variables and non-boldface letters otherwise. Throughout the section, b ~ {0, 1} will always denote the random variable de-
2

---

Uniform Mcan Estimation for Heavy-Tailed Distributions via Median-of-Meant
VXXXXXXXX
VXVXXXXXX
wwXXXXXX
wVVXXXXX
pxx
3
Payz
3
Berx
MOM
MOM
MOM
MOM
f
Step
Stop 2
Stop
Payat
Aujxy
Rap
MOMgtoost ghost
MOM
ghost
MO M ghost
Figure 1. Proposed symmetrization approach. Red crosses and green ticks denote mean estimates that failed or succeeded respectively. Step Symmetrization the MoM with ghost sample, Step 2: Imbalance preserving discretization the class F. Step Permutation of the sample means between the MoM of interest and the "ghost" MoM.
fined Pb (b- =0 = Pb (b= 1/2. For natu- ral number E N we define the set [x] = (1....:M) k). Given two sets A and B, BA denotes the set of all func-
there must exist function f F for which least half of its x. mean estimates in the MoM fail to be s-close to the true mean. However, for fixed function f. we know that the MoM is likely to have almost all of its x mean estimates correct. We now leverage this in the first step of the analysis by introducing "ghost" MoM, that has almost all of its x mean estimates correct for the function MoM of interest had at least half of its mean estimates incorrect. This step is depicted in Figure 1 as "Step 1," where the red crosses indicate whether mean estimate is correct or not. We observe that the MoM of interest has at least half of its x mean estimates incorrect, whereas the "ghost" MoM has very few errors among its mean estimates for the function f F. This imbalance between incorrect mean estimates in the MoM of interest and the "ghost" MoM is key for "Step 3," which argues that such an imbalance is unlikely due to the symmetry introduced in this step - "Step 1" can be seen as a symmetrization of the MOM.
tions from to B. For a function f E F S R
m E N. X E Xmm and a distribution D over X, the no- tations P(r.)) and μ denote the sample mean of f on X, L.. P(F.X) Din /m and its expectation over D Hy ExnD [f(X]] Furthermore, for p E (1, we write F (D) iff Sup E [S(X)P] < 00.
F, on which the
For E N, if a1 ai,..,,,, Ox E IR and we let d(1) ...., a(x) denote the numbers in ascending order, we define their median as
(((x)))2)) i is odd ((x/2) if is even.
MEDIAN((1, axx)
With the definition of the median, we can now define the MoM estimator.
Algorithm 1 Median of Means (MoM) Estimator
The next step in the analysis involves discretizing the func- tion class F into finite-sized function class F. Normally, this step would be performed by creating net over the func- tion class F for any possible estimating sequence. However, since we aim to provide bounds for potentially unbounded function classes, with finite moments, we adopt an alter- native discretization. Specifically, we only require the dis- cretization f of the function class F to ensure that most of the mean estimates in both the MoM of interest and the "ghost" MoM remain the same thus preserving the im- balance between incorrect mean estimates in the MoM of interest and the "ghost" MoM created in "Step 1". Further- more, we also allow the discretization to fail for negligible amount of mean estimates. This step is depicted as "Step 2" in Figure 1, where we observe that the discretization F of F preserves the imbalance between incorrect mean estimates of the MoM of interest and the "ghost" MOM.
Input: Sample X (X) ,...,,,.",,,,.. Xx), X pm m,K E N. function f X
Return:
MoM(f, X) (E ,ffx*).
In words, the MOM takes as input sample consiting of blocks of m samples in each, and a function ff wanting the mean estimate of.
Finally, for m, & E N, and X1, X2, X3 E (X'')*, for each E (1,2,3) we rely on the following notation,
X1 = (X)
XI
X X
3.2. Proof Overview
Here, we provide high-level and intuitive explanation of the proof for our main theorem, we here provide Figure as way of thinking about the proof pictorially.
The final step of the analysis is due to the previous two steps, to analyze the probability of the existence of function f E F for which the MOM of interest has close to half
The first thing we observe that for the MoM to fail in providing a uniform error bound over the functions in F,
3

---

Uniform Mcan Estimation for Heavy-Tailed Distributions via Median-of-Means
or more of its mean estimates incorrect, while the "ghost" MoM has very few incorrect mean estimates. First, since F is finite, it suffices to analyze a fixed f E F and then do union bound over F. For fixed f. we leverage the symmetry introduced in "Step I", namely using that the mean estimates of both the MoM of interest and the "ghost" MoM are i.i.d. Thus, we may view the x mean estimates of the MoM of interest and the "ghost" MoM as being "assigned" as follows: Draw two mean estimates, f1j,x and M22 f.x and with probability 1/2, assign 11 j.x to the MoM of interest and f.2. to the "ghost" MoM. Otherwise, assign f. to the MoM of interest and f.fxx to the "ghost" MOM. Repeat this process K times. Under this perspective, it is intuitively that having large imbalance between the number of incorrect mean estimates for the MoM of interest and the "ghost" MoM the MOM of interest has close to half more of its mean estimates incorrect while the "ghost" MoM has very few incorrect mean estimates- - is unlikely. This final step is depicted as "Step 3" in Figure I, where the mean estimates of the MoM of interest and the "ghost" MoM are permuted.
if there exists a threshold function Ko E No.1, threshold En > 0 size function ND E NR s.t. for any 0 e < co. 0 < ô < 1, m 1, and 2 ko(o), with probability at least 1 - 8 (over X1. X2 ~ (D"))*) it holds that: F admits a (e, m)-dscrretizzatoon F(E.m) on Xo, X1, X2 and
[F(E.m) I (E).
Remark 3.3. The following comments are in order.
If a function class F S R* and > 0 is such that for any distribution D' over X' and any 0 < & S so. F Ne' e L1) in L1 with respect to D', i.e. for any f F there exists (f) E NeDD'', FD,.F,K. L1)
admits a E-net
such that
E 11(X) -())))I()XXX] X
(3)
then for any < E S Eu. m, E N. X1, X2 (X F admits (c, discreetttinnninnn of size most supp | (2' any data generating distribution D over X, F has D-discretization with threshold function Ko = 1, threshold En and size function No(e, m) = supp (te/187s(D',, F)). See the Appendix A for a proof of this claim.
Furthermore, for
The above high-level analysis contrasts with the conven- tional aammmttrzatonn-diccretaatttooo on the estimating sequence level, where the above analysis symmetrizes, discretizes, and permutes the mean estimates.
argument,
Let p 2 For a function class F, it is known that the existence of a s-net w.r.t. I,, implies the existence of E-net w.r.t. (D')). Thus, each F admitting net w.r.t. to the L, metric, would also admit a (c, m)- discretization and D-discretization.
3.3. Main Result
To present our main result, we need the following definitions of discretization for function class F.
Any function class F bounded between |-1, 1] and featuring finite fat shattering dimension FAT, at every scale E > O, admits a E E-net ((s,, (L),L (D)) for any D of size at most exp (O(FATo(e) In (1/e))) (see Corollary 5.4 in Rudelson & Vershynin (2006)). This result can be also be extended to classes bounded in M for M 2 with appropriate rescaling.
Definition 3.1 ((E, miDsseeretizztion) Let 0 < e, m, E N. X2 E (z A function class FÇR R admits a m)) discretization on X1. if there exists a set of functions F(c.m) defined on Xo, X,,X1, X2 satisfying the following: for each f E F, there exists (ff) E F(e.)) and I5 [x] s.t.: | <
2x and for each 025
i [n] and VI E {0, 1, 2). it holds that
We remark that the definition of D-Discretization is allowed to depend on realizations of the samples, oppose to the stricter definition of having one fixed discretization which holds for all realizations of the samples. This view of considering discretizations that depend on the samples is (to our knowledge) the most common in the literature, see e.g. Shalev-Shwarrd & Ben-David, 2014) Defiiniinnn 27.1], (Kupavskii & Zhivotovskiy, 2020)[Lemma 7] and (Rudelson & Ver- shynin, (T06)rene 4.4 and Corollary 5.4).
m ((xi,) +()(Xt))
SE.
(2)
m
We call (F(.m))l the size of the e-discretization of F on Xo, X1, X2.
The above definition requires only that we can approximate most of the K sample means of function f E F appearing in its MoM with those of its neighbor xff) E Fic.m). all
three samples X1, X2, X3. The following definition extends this idea at distribution level, by requiring that with large probability, the samples Xo, X1, X2 allows F to admit a (e, discrettttzz....n
We are now ready to present our main result.
Theorem 3.4 (Main theorem). Let Ff C R. and D be a distribution over X. Suppose that F. admits a D- discretization with threshold function Ko E 1100.1,, thresh- old Eo. and size function ND E N Moreover. sup- pose that for some p E (1, F C (D)( and let vp Z
Definition 3.2 (D-Diseretization). Let D be a distribution over X. A function class J C R admits a D-discretization
4

---

In words $6²) (f,e) is the fraction of the k mean estimates of f that are c-away from the mean estimates of f on the sample X2, and (f,e) is the fraction of the mean Uniform Mcan Estimation for Heavy-Tailed Distributions via -edian-of-Means
SUP EX~D (X) Ex~D [[()) P.. Then, there ex- ist absolute numerical constants c2 Cg > s.t., for any E (0, and ò E (0,1). if
To derive sample complexity bound from this, one should be able to get an explicit estimate of ((F, n) in terms of n. This has already been done for cer- tain classes of bounded or well-behaved functions (see for example (Bartlett & Mendelson, 2003; Maurer & Pontil, 2010)), it may be intersting to see if a relaxed notation of discretization, the same spirit of Defini- tion 3.2, can lead to explicit bounds even for broader classes of functions.
400 16
I
m 2
EP
10 In (2)
8N (1/16, m)
M max
ko()/8),
50 In
99
8
holds
We remark here that the magnitude of the constants in Theorem 3,4 is rather large. This is due to the sym- metrization, discretization, and permutation arguments, and was not optimized. Notice that it is not uncom- mon for symmeerivationnddicretiiazzio aatprionnnnniieeiiititooereaaiai permuutatoonn ar- guments to yield large constants, for instance: (Bartlett et al., 1996) having constant of approximately 1500 (read from proof of Theorem 9 (5)), and later improved, asymptotically, by (Colomboni et al., 2025) having a constant of approximately 5000 (read from point (i) page 13), and (Long, 1999) having constant of ap- proximately 500 (read from lemma 9).
P X-(D")*
sup MMM -m(I se) 21 8.
f
(4)
Remark 3.5. The following comments are in order.
To provide some intuition on the MoM parameters m, K,E,8, 8, we start noting that the dependency on s decides the number of samples m needed for each of the mean estimates, and is chosen such that they are within (e)) distance from the true expectation with constant probability. Furthermore, both ε and d also into the number of mean estimates, K. The intuition for the choice of K, is that the MOM, which is based on aggregation of и mean estimates, boosts the constant success probability to 1 - 6/ND(e, (e, m) probability for any function in the discretization, and one can then do union bound.
3.4. Analysis
We now give the proof of Theorem 3.4. We start by noting that for the MoM to fail, it must be the case that least 1/2 of the mean estimates tion, as in the converse case the median is E-close to the expectation. Thus, to bound the failure probability of the MoM it suffices to upper bound the probability of the for- mer event. Before presenting the upper bound, we introduce the following auxiliary random variables that will be useful throughout this section. For à {>, S}, K,,.m m E N, >> O, Xo, X1, X2 ((D)") "","""" Xo, X1 X2 E ((x)))) and random vector b E {0, 1)xh with independent coordinates with P b. = 0] = P [b, 1] 1/2, we define
E-away from the expecta-
The sample complexity bound implied by our theorem is of the order of
Up EP)
(ogoNo((/11...0//))))) + log (5) (5)
when not taking into account No (6/)8), and there- fore of order (cp/es)1/te-1) log(v,/(s0)) (=6)) as soon as ND(E/16, (up) 1)) (1pp/))) for some constant a. We notice that this is optimal (up log factors) (Devroye al., 2016).
" 1 11 Ms (b}}
(f,
K
a
11 MAxyylk
In order to apply this result, one needs to find a D- discretization of F. In Remark 3.3 we have seen that this is possible if F is bounded. In the next section, we show two concrete examples of unbounded classes that admit such cover.
se Σ
K
The estimation error bound in (Lecué al., 2020), holding for p 2, instead is of the order of
estimates of f that are E-close to the mean estimates of f on the sample X2. We also consider {(b) (I E) and S E), where 1 1-b b (1- .i...,, b,). Now we can state our symmetrization lemma.
R(F,Do D, n)
(1g(1
n
n
where n is the sample size and R(F, D,n) n) is the Rademacher complexity of F over a sample of size n.
Lemma 3.6 (Symmetrization). Letp p E (1, 2], > 0, and D a distribution over X. Suppose that F C (D), and
5

---

Uniform Mcan Estimation for Heavy-Tailed Distributions via -fdian-of-Means
let vp 2 sup Ex~D (X)
Ex-D [f(X)
Then, we have that
Lemma 3.8 (Permutation). Let m, R. E N O, and
Xo, X1, X2 E (2 Then, for any f E R it holds that
if ffm² 2
1000100p0/
I
and x =
110 la (2)
20
99
P
(s()
(5.
12c
2 c, S (>)
1-b (5.
12e
<d)
11 - -myl >}}
b-(0,13"
16
16
P DmmDm
FfFF:
2
I exp
50
34 P (BFF: ((0))(((()))))
(1,
15s)
2 a.
( (1:
(1.
23 >b)
where e =
4769
and d
331
16
16
10000
10000'
X X1x2
We are now ready to show the proof of Theorem 3.4.
where a Xo, X2 ~ (D x
4801
b
9701 10000
b
{o, 10. and
10000
Proof of Theorem 3.4. For the MoM to fail to provide uniform estimation for F it must be the case that there exists function f E F s.t. at 1/2 of the mean estimates of its MoM fails. That is
We notice that the above lemma captures the situation de- scribed in "Step 1" of Figure 1. That is, we have related the event of the MoM failing, with the event that one MoM has many incorrect mean estimates (with the true mean being estimated), and second MoM has few incorrect mean esti- mates. Notice the b, 's have been set up for the permutation argument, which will show that this imbalance is unlikely.
sup MOM(1.)) - -M()>> ) NEEF
P X~(Dm)"
111s, - -M41 > 5]
1
P Xn(Dmje
FfEF:
2 2
Before applying the permutation step, we discretize the function class to enable a union bound over the event that the mean estimate fails for each function in the class. The following lemma relies on the existence of (e, m)- discretization: by definition, moving from F to its discretiza- tion only changes the number of mean estimates that are good approximations of the "true" mean estimate yy,x; or, conversely, the number of bad mean estimates, slightly. In other words, this discretization preserves, the imbalance created in the symmetrization step.
Since m 2 yields
100-16"02
and K 2
10" Iu (2)
Lemma 3.6
EP
99
P XN(Dijjn
(3f
E MMM x) 1uy > E)
(JEF: : (,,
15g
<4 P b
2 a,
16
X X1"""""""'0"""""
$ f, 2
>b)
Lemma 3.7 (Discretization). Let m, K. E N,E > O, and Xo, X1,X, E (Z Suppose that F admits ( m)- discretization F(s/16,m) over Xo, X1, X2. Then, it holds that
16
with a = 10000 and = 9701
4801
10000 Now let G denote the event
that the samples Xg, X,, X2 are s.t. F admits (c/16, m)- discretization of size most ND(e/16, m) over them. Then, since by hypothesis x 2 ko(6/8), it holds that
(3SEF: s(>) b-10.13
(1:
15e
2
25 a 1-b (1:16)
>b)
16
16
$ |F(c/10,))
sup
P
(st)) ff
12g
2 c,
P X X~(
(
F:: ::FF:MMMM[N MOM(J,
SEFle/1a,
(011
16
12
S
X (D
11-b
16
(IEEF: (f,
15s
1(G)
P (0.1"
2a,
where a 10000:
4801 b-
9701
4769
d
331
16
10000
10000
10000
The above lemma is described as "Step 2" in Figure 1. That is, the function class has been discretized while preserving the imbalance in the number of incorrect mean estimates, and the problem has now been reduced to analyzing an imbalance of correct mean estimates between two MoMs for single function.
8 b
25 ff
>6] + 55/2.
(5)
16
Since for each realization Xo. X1, X2 of Xo, X1, X2 E G, F admits a (s/16, m)- -idcerreetizaiinn, Lemma 3.7 implics that
P b0.0111"
(3 (3SEF:$()) (1,
15
2e 2a, S
8(5) (
>b) 16
16
The following permutation lemma, states that having two sets of mean estimates that differ widely on their quality happens with exponentially small probability, in the number of estimates k. This lemma models the situation depicted as "Step 3" in Figure 1.
( (1,
12s
< |/(e/16.m)
sup
P
2g
fEfie/10.m.
b" (0.13
16
12c f,
S 1
<d)
16
6

---

Uniform Mcan Estimation for Heavy-Tailed Distributions via Median-of-Means
where c 10000
4769 and d 10000 Notice that the term on
mits a D-discretization with
the right-hand side, by Lemma 3.8, can be bounded with exp (-x/50). Thus, if we take K 2 50 In (1.
Ro(d) 2- 2-8000 In (e/0),
the above it is at most 6/8, which, combined with (5), im- plies that
en 1
ND(E, m) =8 72 10 8000c
140kd (ok)
(3/ EFEF: |MM[M -myl e) S 8 (-mDm)s
P
Moreover let =, E (0, 1), if
and concludes the proof.
400 vp
m 2
8P
4. Applications
10c In (2)
(8ND(E/16, m)
K 2 max
(oo(0/8)
,,50 In
99
6
In this section we present two applications of Theorem 3.4.
then
4.1. k-Means Clustering over Unbounded Spaces
P xx(Dm)
sup fefx
(
21-6. 8.
k-means clustering is one of the most popular clustering paradigms. Here, we provide a new sample complexity bound that improves upon existing works for the case of unbounded input and centers.
)
Remark 4.2. The following comments are in order.
The sample complexity bound implied by Proposi- tion C.3 is of the order of
Preliminaries. Given 2, V E Rd, we let d(x,y)² = || - v1l2. We use k E N to denote the number of cen- ters, and Q E gaak to denote the centers meant the columns of Q. For x E Id and Q E Rdxi we let the loss of Q on x be defined as d(x,, Q)² = mingeQ || - gll.. where the minimum is taken over the columns of Q. For a distribution DD over Rdd we let μ = Ex~D [X] and d² Ex-D ()
Up E
log log is log + log )
dk
(6)
Notice that the dk log k-term depends on the number of centers k and the dimensionality of the problem d, and resembles complexity term.
The literature on generalization bounds for k-means is rich and has mostly focussed on distributions with bounded support and centers lying in norm ball of given radious (Linder et al., 1994; Bartlett et al., 1998; Levrard, 2013; Antos et al., 2005; Maurer & Pontil, 2010; Telgarsky & Dasgupta, 2013). The work closer to ours, in that it considers inputs and centers from unbounded sets, is Bachem et al. (2017). In that work, authors analyze the problem of uniform estimation over Fx with the sample mean and show a sample complexity bound of the order of
In the k-means clustering problem, we are given random ii.d. samples from D. and the objective if to minimize risk R(Q)= = [xXX, Q)²] over Q E Rdxk Our goal is to provide a uniform estimation bound for all possible sets of k-centers. We consider the class normalized loss functions defined below. For Q d we define
2d(x, Q)²
fo(x) 0² + EX [d(X,Q)) Q
and F& (folQ Rack). The class F& has been intro- duced in Bachem al. (2017) and provide several advan- tages compared to the standard loss class including scale- invariance, and that it allows to derive uniform bounds even when the support of 'D is unbounded and Q E IRdd The next theorem provide a bound on the sample complexity of the MoM for this problem.
K.
dk log k + log ))
E28
where K. = E[[(X, p)) is the kurtosis of D.
We start noticing that Bachem et al. (2017) requires the finiteness of the kurtosis, while our result only re- quires D to have finite variance and Fg S (D) for some p E (1, 2). To see that our condition is weaker, observe that when K. < oo then Fs C L2(D) (See Lemma C.I and the relation between f E Fx and s). Focussing on the case of p = 2, we have the following
E N and let D be a distribu- < co. Suppose that, there ex- ists a P E (1,2) s.t. FR c LD) and xo > Up 2 supfer, Ex-D [Xx) EX [[X)) PP) Then, Fe ad-
Theorem 4.1. Let k
tion over Rd s.t. o²
7

---

Uniform Mcan Estimation for Heavy-Tailed Distributions via Median-of-Means
observations. First, notice that our sample complexity bound is exponentially better in the confidence term 1/6, this is due to the stronger concentration properties of the MoM compared to the sample mean. Second, in (7) the confidence term 1 multiplies the complexity term dk log & which is undesirable. contrast, in our sample complexity bound these two terms are decou- pled. We finally note that our bound suffers from a slightly worse dependence on due to the extra log term.
Then Fw admits a D-discretization with
Ko(ō) -4 -12502 In (e/5),
6o xx,
6W
ND(
((,, m, D)
where
W
(x(),e)
B( m, D) min
3750 (E [|| + E (IY
We have focussed on providing uniform estimation guarantees for the class F& of normalized losses. In practice, one may be instead intered in bounding the
J= (3W/2 1) 3750 (E X [1] + E [Y]])
Moreover let E (0, bo) and 5 E (0, 1), if
risk R(Q) of certain set of centers Q, given its per- formance on the sample. Calculations show that one can get such a bound from Proposition C.3 (see the Appendix for details). particular, under the same assumptions of Proposition C.3, for each Q E R (dxk) the following holds with probability least 1 1 5
m 7400- 16
8P
10 In (2)
(8ND(e/16, m)
K 2 max
Ko(6//8)
..50m
99
8
then
(1 e ( (d(,, Q)2 X) + EO²
(8)
p XDm(D
sup fEFw
MMMM(f - 21-8,
4.2. Linear Regression with General Losses
where Z = Y) ((Dx x Dy)""
Linear regression is a classical problem in machine learning and statistics. This problem is typically studied either in the special case of the squared loss or for (possibly) non-smooth Lipschit losses. We consider instead the more general class of continuous losses and show a sample complexity result that holds for broad class of distributions.
Remark 4.4. The following comments are in order.
If we omit the dependence Up, the sample com- plexity bound implied by Theorem 4.3 is of the order of
WJ log (oe()))))
log (5))
Preliminaries. In this section é E [0, oo) will denote continuous loss function unless further specified. We con- sider the function class obtained composing linear predictors with bounded norm with f. That is, for W > 0, we define
(9)
Notice that, for a given loss function f, the d dloog (..) depends both on d, E and W as well J. Which resembles complexity term, depending on the distribution via J, the complexity of l via az, and the norm of the regressor and its dimension d.
Fw {((((w,)) ) -) | w IRd
(R4,1/u)) ||w/|| S WW.
Thus, if f E Fw, then f((z, y)) e((((w (I, v))) = {((w; 2) - y), for any x E Rdd y E R. For a, > 0, the define number ar(a, b) as the largest positive real s.t. for x, E I-a,at a] and jz - yl S ae(a,b) b) we have that [[(x)) - {(v) I b. Since é is continuous and [-a, a] is compact interval, ae(a, b) is well-defined. Thus, l is uniform continuous [-a a). Furthermore, when e is L-Lipschitz, then az(a, 6) = b/L.
the loss function is also I.-L.isshitzz and ((0) = possible to obtain more explicit bound. In particular, calculations (see Appendix D for details) show that, if SUPWEB(W) E [Kw X) + E [|Y) < oc, and omitting it in the following expression omitting up ). the sample complexity is at most of the order oa(sasuuingg W 2 1)
The next result provides a uniform bound that holds for general continuous losses.
dlog (W) + log (t))
(10)
Theorem 4.3. Let W > 0 and Dx and Dy be distributions over Rd and R respectively and let D = Dx x Dy. Suppose
that, there exists a p E (1 s.t. Fw [ (D),, and 0o > Up 2 supjeFw Ex-D [X) - Ex [
In this case, the dependence in is explicit and of the order of -ー log(1/s).
8

---

Uniform Mcan Estimation for Heavy-Tailed Distributions via Median-of-Means
We notice that the rate 10 matches, in terms of the
computing, pp. 20-29, 1996.
dependence in e and ó and up to log factors, the know
rates of the sample average when the distributions of
Alon, N., Ben-David, S., Cesa-Bianchi, N., and Haussler, D. Scale-sensitive dimensions, uniform convergence, and learnability. J. ACM, 44(4):615-63) 1997.
|| and Y are exponnenoetal (see for example Mau- rer & Pontil (2021)). For this class of distributions, all moments exist, while our result only requires the existence of the p-th moment for p E (1, We also point out that similar generality on the distribution is also achieved by Lecué et al. (2020) which also relied the MoM estimator. The main difference is that their bound has dependence on the Rademacher com- plexity of Fw. which as far as we know, is not explicit for this class distribution.
Antos, A., Gyorfi L., and Gyorgy, A. Individual conver- gence rates in empirical vector quantizer design. /EEE Transactions on Information Theory, 51(11):4013-444 4022, 2005.
Bachem, O., Lucic, M., Hassani, H., and Krause, A. Uniform deviation bounds for k-means clustering. In Proceedings of the 34th International Conference Ma- chine Learning, pp. 283-291, 2017.
5. Conclusions
Barabási, A.-L. Network science. Cambridge University Press, 2016.
In this work, made novel analysis of the MoM for the problem of estimating the expectation of all functions in a class only assuming that moments of order up to p (1 exist. We have focussed on the sample complexity and identified a new notation of discrctization that allows the MoM to solve the task. To obtain this result, we have also developed new symmetrization technique. We also showed that it is possible to find such a discretization in two important cases: k-means clustering and linear regression. It is interesting to find other applications where a discretization of the function class is possible. Finally, another problem is to match asymptotically lower and upper bounds to the sample complexity of uniform mean estimation under heavy tails, as done in Lee & Valiant (2022) for the single mean estimation problem. We leave these questions for future work.
Bartlett, P. L. and Mendelson, S. Rademacher and gaussian complexities: risk bounds and structural results. 3(null); 463-482, 2003.
Bartlett, P. L., Long, P. M., and Williamson, R. C. Fat- shattering and the learnability of real-valued functions. J. Comput. Syst. Sci., 52(3):433 452, 1996.
Bartlett, P. L., Linder, T., and Lugosi, G. The minimax dis- tortion redundancy in empirical quantizer design. IEEE Transactions on Information theory, 44(5):1802-1813, 1998.
Bradley, B. O. and Taqqu, M. S. Financial risk and heavy tails. In Handbook of heavy tailed distributions in finance, pp. 35-103. Elsevier, 2003.
Acknowledgement
Catoni, O. Challenging the empirical mean and empirical variance: deviation study. In Annales de I'IHP Proba- bilités et statistiques, volume 48, pp. 1148-1185, 2012.
Mikael Møller Høgsgaard is supported by DFF Sapere Aude Research Leader Grant No. 9064-00068B by the Inde- pendent Research Fund Denmark. Andrea Paudice is sup- ported by Novo Nordisk Fonden Start Package Grant No. NNF240C099436 (Actionable Performance Guarantees in Machine Learning).
Colomboni, R., Esposito, E., and Paudice, A. An improved uniform convergence bound with fat-shattering dimen- sion. Information Processing Letters, 188: 106539, 2025.
Devroye, L., Lerasle, M., Lugosi, G., and Oliveira, R. I. Sub-gaussian mean estimators. 2016.
Impact Statement
"This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here."
Gurbuzbalaban, M. and Hu, Y. Fractional moment- preserving initialization schemes for training deep neu- ral networks. In Proceedings of the 38th International Conference Artificial Intelligence and Statistics, pp. 2233-2241, 2021.
References
Gurbuzbalaban, M., Simsekli, U., and Zhu, L. The heavy- tail phenomenon in sgd. In Proceedings of the 38th Inter- national Conference on Machine Learning, volume 139, pp. 3964-3975, 2021.
Alon, N., Matias, Y., and Szegedy, M. The space complexity of approximating the frequency moments. In Proceed- ings of the 28th annual ACM symposium on Theory of

---

Uniform Mcan Estimation for Heavy-Tailed Distributions via Median-of-Means
Jerrum, M. R., Valiant, L. G., and Vazirani, V. V. Random generation of combinatorial structures from uniform distribution. Theoretical computer science, 43:169-188, 1986.
Nemirovskij, A. S. and Yudin, D. B. Problem complexity and method efficiency in optimization. 1983.
Oliveira, R. and Resende, L. Trimmed sample means for robust uniform mean estimation and regression, 2023. URL https: arxiv. org/ /a/s//////// abs/2302. 06710.
Kearns, M. J. and Schapire, Efficient distribution- learning of probabiliittic concepts. Journal of Computer and System Sciences, 48(3):464 497, 1994.
Rudelson, M. and Vershynin, R. Combinatorics of ran- dom processes and sections of convex bodies. Annals of Mathematics, 164:603-648, 2006.
Kupavskii, A. and Zhivotovskiy, N. When are epsilon-nets small? Journal of Computer and System Sciences, 110:22-36, 2020. ISSN 0022- 0000. doi: http:///boi.rr///0.0066ii 006. URL
Shalev-Shwartz, S. and Ben-David, S. Understanding Ma- chine Learning: From Theory to Algorithms. Cambridge University Press, 2014.
Telgarsky, M. J. and Dasgupta. S. Moment-based uniform deviation bounds for k-means and friends. Advances in Neural Information Processing Systems, 26, 2013.
Lecué, G., Lerasle, M., and Mathieu, T. Robust classifi- cation via mom minimization. Machine learning. 109: 1635-1665, 2020.
Vapnik, V. N. and Chervonenkis, A. Y. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability & Its Applications, 16(2):264-28) 280, 1971.
Lee, J. C. and Valiant, P. Optimal sub- -oo--aaussinnn mean esti- mation in R. In 2021 IEEE 62nd Anmual Symposium on Foundations of Computer Science (FOCS), pp. 672-683, 2022. doi: 10.1 10110/0C/5299999 2021.0001..
von Bahr, B. and Esseen, C.-G. Inequalities for the rth Absolute Moment of a Sum of Random Variables, 1 S r 2. The Annals of Mathematical Statistics, 36(1):299 303, 1965.
Levrard, C. Fast rates for empirical vector quantization. 2013.
Linder, T., Lugosi, G., and Zeger, K. Rates of convergence in the source coding theorem, in empirical quantizer design, and in universal lossy source coding. IEEE Transactions on Information Theory, 40(6)):728-17477 1994.
Zhang, J., Karimireddy, S. P., Veit, A., Kim, S., Reddi, S., Kumar, S., and Sra, S. Why adaptive methods good for attention models? In Proceedings of the 34th Annual Conference on Neural Information Processing Systems, pp. 15383-15393, 2020.
Long, P. M. The complexity of learning according to two models of drifting environment. Machine Learn- ing, 1999. URL https: /tt////oi.. httpiioogg///./1.111 1007666507971.
Zhou, P., Feng. J., Ma, C., Xiong, C., Hoi, S. C. H., et al. Towards theoretically understanding why sgd general- izes better than adam in deep learning. In Proceedings of the 34th Annual Conference on Neural Information Processing Systems, pp. 21285 1188522129,, 2020.
Lugosi, G. and Mendelson, S. Near-optimal mean estimators with respect to general norms. Probability theory and related fields, 175(3):957-973, 2019.
Maurer, A. and Pontil, M. K-dimensional coding schemes in hilbert spaces. 56 56(11):5839-584 2010.
Maurer, A. and Pontil, M. Concentration inequalities under sub-gaussian and sub-exponential conditions. In Pro- ceedings of the 35th Annual Conference Advances in Neural Information Processing Systems, pp. 7588-7597, 2021.
Minsker, S. Uniform bounds for robust mean estima- tors, 2019. URL https: org/ abs abs/181.. 1812. 03523.
Nair, J., Wierman, A., and Zwart, B. The fundamentals of heavy tails: Properties, emergence. and estimation, volume 53, Cambridge University Press, 2022.
10

---

Uniform Mean Estimation for Heavy-Tailed Distributions via Median-of-Means
A. Details of Remark 3.3
In this appendix we elaborate on Remark 3.3.
Remark A. If a function class S R and Eo is such that for any distribution D' over X' and any 0 < I Eg. F
admits e-net NG F,L1) in L1 with respect to D', i.e. for any I F there exists (ʃ) E NN' Li) such that
[1f(X) +
(11)
X-D
then for any 0 < & < Eo. M, E N, X1, E (Z"*)" F admits a (s, -diieeettttiii of size at most suppr / F),,, Furthermore, for any data generating distribution D over X, F. has D-discretization with threshold function Ko = 1, threshold Eo and size function ND(E, m) = supp | (D',F)
To the above let 0 <ESo Xo, X1, X2 E (A Now consider the following distribution D' induced by Xo, X1, X2 1x=='),
given by D'(x) Ei E Ex 3km i.c points in the sequences Xu. X1, X2 are weighted proportionally to the number of occurrences they have in Xo, X1, X2. Let now N24/1875 FD) be a 26/ 2e/1875-net for F in I, with respect to [f(x) [(())=<(((=)) E} then we have
D' and let I denote the subset of [x] such that I = E [k], {0, 1.2), Σxex:
by Equation (11) and the definition of the distribution D' that
((Xi))- - +()(E)))
28/1875 2 E [1(()) (f)(=))
Σ
X~D
3mk
2 Σ f(xi)) (f)( KEI J=
E|1
3mk
3x
which implies that [7] <
6ic =
2x and shows that F admits a (e.mm)-diccretzzale N22/1875(DD (D',F) 3) on Xo,X,, X2, and 625
1875
that it has size at most supp (N2:/1875 (D',
We notice that the above held for any << < S Eg. m,K Xo. X2 (XTT)S,, so especially also for the outcome of Xo, X1, X2 (DT) for any distribution D over X (now data generating distribution). Thus, in the case that F for any distribution D' over X' and any 0 < Eu admits E-net NV F, L1) in L1 with respect to D', then it has for any data generation distribution 'D over X DDdiscretizzatinn with thresholds function Kgg 1, (holds with probability 1 for any ), threshold Eo, and size function ND(E, m) = supp (D2)
We also remark that an -net is weaker than nets for p 2 (i.e. Equation (1I) with (Ex-D/ ([ (P) so function class F admitting net in Lp p 2 would also imply a (e, -iseereettization of F. Furthermore, we remark that for instance any function class which is bounded between [-1, and has finite fat shattering dimension FAT, every scale > 0 by (Rudelson & Vershynin, [CoooaCyryl 5.4] admits s-net Ne, F, L1) in L1 with respect to any D with size exp (O(FATo(e) In (1/e))), this can also be extended to function classes bounded between [-M, M] for M 2 1, with suitable rescaling of the net size.
B. Proof of lemmas used in the proof of Theorem 3.4
In this appendix we give the proof of Lemma 3.6, Lemma 3.7 and Lemma 3.8. We start with the proof of Lemma 3.6. To the end of showing Lemma 3.6 need the following lemma which gives concentration of the sample mean given 1 < central moments of the random variable ((X). The proof of this lemma can be found Appendix E.
Lemma B.1. Let F C x be a function class, D a distribution over X, < p 2, 0 < < and 0 < e. For F E L.,
Up = sup Ex-D (X) - Ex-D [X]] and m 2
12
then any f E F we have that:
deP
IP
(1aix - uy 8)
XwDm
With the above lemma presented, we now give the proof of Lemma 3.6

---

Uniform Mcan Estimation for Heavy-Tailed Distributions via Median-of-Means
Proof of Lemma 3.6. To shorten the notation in the following proof we now define the following random variables,
1|,xx - us >6)
(g(,,e)= = 10, - -Pyl +
(x)),)== =
K
Now notice that by the law of total probability we have
(3f F: M, (f.E) 2 1
99 199
P XXX-(Dm1)-
Mz 16' >
16'
100 200
P (3fEF: (DNxe
(2(E)) 2 2'
MM (f. 16 >
99 199
3f F: MM (f(f)) 2 2)
100 200
1
p J M> 2
(12)
Suppose that ()(f,e) 2 2 for some F. Then for such f and for any i ,,..., ks we get by m 1100-16'> op
and invoking Lemma B.1 with ā = 1/200 and & that
11 - ugl> 1611 PP [1x.. 111> 6
E DmmDm
S 200*
16
which implies that
1 -ayl S (6] 199/200
E D
(Vi 1, ,.....K)) R).
(13)
The multiplicative Chernoff inequality applied with A 2
10 (2)
yields
99
P (Dmm
M
E 16
1
EM S (f, 8
100
16'
1
1[ X) uss s -
16 1
S exp
EE
100
199
1
S exp
100
200
2
which, by (13), further implies
1
1
-
P
1
E
M
(f.
2
X (Dmje
16
100
16
E.) Mr
1
199
P
(Dmje
16
100
200
99
199
P X=(Din>
M (f.
16
100 200
Thus, by independence of X and X (12) can be lower bounded by
P (Dmje
(J
2 55 Mc(
1
99 199
(14)
100 200
1 2
> - P
2 x~
We now introduce a third sample x ~ >DDin" and for each f E F and for every 8 > 0, we define the random variables
()(8))== = * 11 - , > })
De([8)= Σ 1 11 x - - [E
K
K
12

---

Uniform Mcan Estimation for Heavy-Tailed Distributions via Median-of-Meene
We now show that
(3SEF:D> Ds
15g,
4801
ss(,,
9701
x X-
16
10000
16
10000
(JJEF: (M.E)
1
99
199
P x (Dm)
M
M
(15)
2
16
100
200
To this end, we again use the law of total probability to get that
15e
4801
2E
9701
P (DDya
F :
D& (S.
16
10000'
16
10000
15e,
4801
28
9701
P XXX)x
E F: (f.
D&
16
10000
16
10000
99
SfEF:M,(fr
M
(f,
2
16
100
P (Dmje
3f 3feF:
1 M (f, 16
99
2
100
and show that the conditional probability term is at least 2- T F where
1 Now consider a realization X, X of X, X such that there exists
1 M, (f.e)) 2' Mg 16
99 199
(16)
100 200
Now repeating that above argument for X but now with X conclude that with probability at least 1/2 over X, we have that
1 pull S )
99 199
100 200
Thus we conclude that with probability at least 1/2 over X we have that ,,,x, is close to μ4 expect for 1 fraction of = 1,...,K K so by the triangle inequality we get
99 199
100
M, (y(e,) 1 flrxx. - u1 > o)
1 111xx
, >
15c
99 199
+1
K
K
100 200
(x
and
Ms(ee) = Σ
K
1( -1yl < 16
x
11p -,
25
99 199
100 200
De(f
which by Equation (16) implies that
15 16c
99
199
4801
2
1/2
(1
(17)
100
200
10000
and
2
99 199
99
199
9701
D& (J,
(1
(18)
165
100 200
100
200
10000
13

---

Uniform Mcan Estimation for Heavy-Tailed Distributions via Median-of-Meant
which proves (15). Notice that, far, we have proved that
P
F: (f,e)
(19)
2
15c
4801
23
9701
4
P x X X-XiX-
FF
2
(5
16
10000
16
10000
We now make short digression. i E [k], let X (X i....... (),m) ~ D Xi = (X)
X
Dm, and
b; ~ {0, 1} with Pb, b; = 0) = Pb, [b, = 1] = 1/2. Notice that for A E (? it holds
(o,1).)). Xi--D" ((X xi-b,) A)
P
(20)
1
P
((X), Xi) E A)
IP
(Xx) X:) E A)
2
2 B3
P (Xx) Xi) E AA)
(by i..d assumption)
Xj-D" Xi ~m
thus (X), Xi-b. has the same distribution as (X). Xi).
Now let b- (bI...., by). X ((X), X/)..... (X X()). X/X1 = (X....., ,x, and X/X; = (X.....,X,,
Using this notation and Equation (24), the following holds
(3EEF: :
15s
4801
23
9701
P (DD))
(f. 16
Ds(f:
2
(21)
10000'
16
10000
(1 - 1
15r
(1axx 158
15c
4801
E
FfEF:
16
XnDm XXX,,
XI
X
K
10000
2m
11 - -,,8, 1 1-
25
16
25 H1p 11 S
16
) 10000
9701
+
R
i=2
F F; A1pyxx -
15c
16
11lg,x -,
15c
}
4801
E
D
x x mm (0,1
10000
X
(Dmge
2=
1 11 bb , -
2r 16
K
1
1
,xx
2x 16
9701 10000
K
2=2
(repeating the above argument K 1 times and renaming X X2.)
= (3f F: b-10.11 Xo,X, j²
(3f
(1 - Ms
15c 16
4801
28
9701 10000
10000
K
Now combining the above Equation (19) and Equation (21) we conclude that
P Xm(Dmiee
[3EF
Ms 2)
<4 P (3EFF:) b No. Xxx
K 1 1
Ms.x1
15c
16
4801
F S 3
9701
K
10000
K
10000
which ends the proof.
We now give the proof of Lemma 3.7
14

---

Uniform Mean Estimation for Heavy-Tailed Distributions via Median-of-Means
Proof of Lemma 3.7. We recall that ta by Equation (2), satísfies that for each F, there exists xʃ) F to and
Iy C [k]] such that [4 I 625
2x and for E [<]][y] it holds for each E {0, 2] that
- -())))=((((i)) $
(22)
77
16
Let for now F, and b be realization of b. We first observe that for any E [s]][T we have by Equation (22) that
f(X) b.. - (xx2))
14 - M5xx1
Σ
(23)
m
j=1
f(Xb,.) -((x)))) - -x0)((2))))
=()((2)))
-
m
(by triangle inequality)
[f -
1(X2)))=(((LL + +lMa())x; - -a(D).g
(by triangle inequality)
/=1
1=1
28
+ |M(().xi, - Ma().xgl.
(by E [n]] and Equation (22))
16
Similarly we conclude that for any E y we have that
f(xi b. 1(X3,))
1ng,f-o, -1,
(24)
x()(x1 - ----~()) (x)()))))
-
m
m
(by reverse triangle inequality)
|[(i - ( b
[f(x2,) - x (f)(22))
21p v -Ma(nx33
m
j=1
(by triangle inequality)
25
ZIPRC0-X - MM(()x3))
(by i [N] [4 and Equation (22))
16'
Now using Equation (23) we get that
x
11p 1fg,3l1 15c
}
(25)
Klp - -gs.xgl
>
15g
Hlp - -5xx2l >
15e
16
16
jeT,
1lrnx - 15
>
15c
Hl - -M011x2
13:
16
Σ
16
+
(by
1 <
2x
625
625
iE
1l Ma())xxal
>
13c
16
Σ
1lM - Mat).xal
13
16
2
(by Equation (23))
625
NT
13s
625
15

---

Uniform Mcan Estimation for Heavy-Tailed Distributions via Median-of-Means
Furthermore using Equation (24) get that
1 11 - 16
2=
(26)
K
1lpAx11 b - - 76
AlMAXI by - - - )
HIFAX by - - 25
KIMGONN by -PROA.L S ]
Σ
+
2
(by / -
2x 625
K
625
4s HI (-()xxl5 -
16
1AMAOONN - M
S
4
16
2
(by Equation (24))
625
sEly
H|MAO) - -oOLLxl S
4e
161
2
625
Since showed the above for any f F we notice that this implies that
Klpsx
15s
11yyx: M 2
4801
9701
F
R
10000'
K
10000
(1M(()xx; - -M(O).aa>>> >
13c
16
4769
(MATEIX - (x())x2
S
16
4
9669
>3ʃEF:
10000*
K
10000
i=1
F F TB
Σ
-11 >
12c
16
4769
Σ
- >
12c 16
331
K
10000
K
10000
Since we showed the above for any realization b of b it also holds for random b, and thus we conclude by the union bound that
((EF:)
1 111,,,, -s.xg
15c
16
4801
K
S 25
9701
K
100000
K
10000
(3f E F
11l - -ss,xg
12f
16
}
4769
HPP by
331 -
12:
16
<
P bnf0,113
mm
10000
K
10000
1=1
F=
Σ
P bo.1..
H1psxx, 15,xgl= >
12c
16
4769
Σ
1X,4 >
12c
T6
331
K
10000
K
10000
FEF 18.m
11psxx -Mrxgl
>
12c
16
4769
11p - -11x3
12c
} 16
331
F+ m
sup
P
Ie
FEF
10.11
K
10000'
P
10000
which finishes the proof.
We now give the proof of Lemma 3.8.
Proof of Lemma 3.8. Let Ç be the following fixed number
12s
12s
(=
H - -1,x3gl
+
Σ 11p -1,,yy1
}
16
16
12g
}.
16
i=
16

---

Uniform Mcan Estimation for Heavy-Tailed Distributions via Median-of-Means
We notice that for the probability in Lemma 3.8 to be greater than 0, it must be the case that <
4769k:
10000 from now
on assume this is the case. Furthermore, we notice that since Ç 2 4769k
To000 there is at least
4769k i's such that either
f or x, is 12s
16 away from , i.. 1,,,x; - M5,,y| > 12e or 1 |,,,;
12c let I C [I....,k) R3 be 16
20000
16
the set of these indexes, i.e. I = {a E [k]] |Ay,xj - 1l > 12c or | My.xg!
}. We notice that for 12s, furthermore we have that the random variable
16
i we have with probability at least 2/2 that 1 11 f.xg
16
Eier bi (,)= 125
Σ
is a sum of independent {0, }-randomm variables. We
notice that by 1| 2
4769k this random variable has expectation 20000
11 (f) - Ms.x;
12s }
4769
16
7 b 10.13*
K
2h
40000
SEI
EE!
We notice that
331
7)
331 10000
(1
10000
Y
and since
is an increasing function for x 2
331 (has derivative
0), and 17 2
4769 40000
331
we conclude
10000
2²
10000
that 1 >>> 7
533
4700
351
3445 4769'
Thus, by an application of a multiplicative Chernoff bound we get that
4700
K 1( (f) 15,x3] >
12c 16
}
331 10000
P
b-.0,11*
K
1
11m1-, b,( - 15,,g
12c
331 T0000
p
16
(1
7
)
b~10,11*
K
17
2311 TOU00.
2
S exp
7716
S exp
(3445 4769
2
77AC
(by
7- TRRWO
3445
2
2
1769
474721
S exp
K
S exp (-k/50).
4769 (by 2
40000 ,)
15260800
where the last inequality follows from
474721
50 and concludes the proof.
15200800
C. k -means
In this appendix we give the proof of the sample complexity result for the k-mean's 's objective. To this end, we first introduce some preliminaries and some results from (Bachem et al., 2017), which we will use in the following proof.
C.1. Preliminaries
We follow the notation used in (Bachem et al., 2017). For two points x., y E RRd we write d(x, y)² = || yl1² for a point x E Rdd and Q C Rdd we let d(x, Q) = mingeQ ||E -l??. We use k E N, for being the number of centers written Q E Rd whereby we mean that the columns of Q are the centers. For a distribution D over Rdd we define = EX-D [X]
and 2² Ex-D [d(X,p) [] For a Q E Bd we define the following function fo given by o2 old For E N
2)(
will use F& to denote the function class F& {fqlQ E [x
To describe the complexity of Fi in the following we will need the definition of the pseudo dimension of function class F C xx The pseudo dimension is defined as the largest number PFim(F) = d, such that there exists point set I1 .i...., Fd and thresholds T1,.... Fdd where for any b E {0, 1)"h there exist function f F such that for E [d] and and if b, 1 then f is above r; i.e. f(x;) 2 ri. We now introduce two lemmas from (Bachem et al., 2017) that we are going to need in the following the first lemma states some useful properties about fo
b, =0 0. then f is below i.e. fx;) <
Lemma C.1 (Lemma in (Bachem et al., 2017) ). Let E N, DD a distribution on Rd, with μ. = Ex-D [X] and Q)(
0² Ex-D [d(X, p) For any Q E pdd define fo(x) = [+EEx-o((X.Q07]) the the function class Fx [folQ Rd
17

---

Uniform Mcan Estimation for Heavy-Tailed Distributions via Median-of-Means
and s(x) = 20( + 8. We then have that (F) < 6k(d + In (6k)/ /n In (2) and for all x E R2 and Q E RR we have that fx) - s(x).
d²
The next lemma roughly says that when s() is bounded point set, then one can bound the size of maximal e-packing of Fk. As in (Bachem et al., 2017) we state the result for general function class F. For this we need to define what we mean by a maximal packing, to this end let 'D be a distribution on X' and F C [0, ooj?" we then say that Pg C F is a e-packing of F in L1 (D) if for any f, g E Pe where f # 9 we have that
f gXX]ll >E.
(27)
X-D
The packing Pe is maximal for F if it has the largest size possible.
Lemma C.2 (Lemma 4 in (Bachem et al., 2017)). Let F S [0, ool be a function class with d = Pdim(F) < co and for x E X define s(x) = supzex J (x). Let DD be a distribution on X, such that O < Ex-D [x(X)] < oo. It then holds for any
0 << E < Ex~D [s X) that any maximal s-packing Ps of F in (D) has size at most 8(2 EX-D [s(X)) /E)ad.
C.2. Proof of Proposition C.3
We now state our Proposition C.3 about the k-means objective introduced above.
Proposition C.3 -means). Let ls E < 8, e < 1, D be a distribution over Rd, μ = EX [X] < p 2 and Fs
{Je 1eelQ Q [ddkk] ifo²= EX-D [d(X, then for m 2
00, Fa E (D) and Up 2 SuD EX-D (X EX_D // [X((]] [P]
400-16Pm,) T and k 2 max (5/8),
10a (2) 50 In (8N(D.//1.m)) where ro( = 2 8000 In (e/0)
cx
99
1n (6k)
and (D,,,m) = 72-100-80004
we have that with probability at least 1 - 8 over X ~ (Dm)": : for all
E Fx that
MOM(J.X)
E X'DD
[(X)II S
Before we give the proof of Proposition C.3 we make the following observation. Proposition C.3 considers the functions
fQ(x)= -+4Ex~ [ For a fixed Q, the denominator fq is a fixed positive number, whereby we get that the median of the means Xie.
2)
2d(x;.0) Q)² -E +1xx+ ()=mm is just the same as scaling the median of the means ΣØ= m
d(x).2)
with 2/ (o² + EX-D [d(X,Q) Whereby we conclude that
|MMMf. - E (((')) SE
X'D
implies by multiplication 2f (o² + EXaD [d(X.Q) )) that
[d('', ()²] 2 =002 + ExInD [d(X',
MoM(d(; Q)2
E X
(28)
2
and furthermore by rearrangement that
E (XXX'Q)2 < (1-app) (MOM(d()))))))
=22 s (1++) (MoM(d(,Q))x))
EO²
EO²
X'
where the last inequality follows from + get that
x/2 < 11 + x for 0 S x S 1, and again by rearrangement of Equation (28) we
I-x/2
[(X'' .0)] 2 (1+ (MOM(C(.)) (),
Ea²
X'
2
which implies if the term (MoM(d(;<))) 2),x)) - _0² 2 that
202
E x
[d('' Q)²) 2 (1- ())M((())),xx)
2
by Tサ0/2 2 21 E, but also holds in the case that the term MoM(d(--Q)
Ea² 2
< 0 since Exx~D [d(X'QQ) is
non-negative and E S 1. We compile these observations in the following corollary
18

---

Uniform Mcan Estimation for Heavy-Tailed Distributions via Median-of-Meant
Corollary C.4 (k-means). Let k N, 0 d,8 < D be a distribution over Rd, μr ExnD [ p and F {Jq Q [Rdx]]
of EXWD [d(X, 14) 00, Fk E (D) and Up 2 SupfeT, RXnD [ EX / (X) 1d]
then for m 2
400-166P,
p-1 and & 2 max (5/8))),
10 (2) 50 (SN(D.//1.m) )) where Ki (o( = 2 8000 In (e/0)
o²
99
and (D,, s, m) =
72-10" 12-100"80000 .0000
14 (6k)
we then have with probability at least over X (Dm)* " that: for all
Q C IR4 such that IQ] =k
E02
S E [(X' S (1+ (MOM(((.).)x)3) + + EO²
(1-s) (.M
2
X'ND
2
We now give the proof of Proposition C.3
Proof of Proposition C.3. We now show that Fg admits a D-discretization with threshold functions ko(o) =
1n0kdln (Gk)
80002 In (e/5), 60 = 1 and size function N(2,e, m) = 72-100 8000
o² = EX_D [d(X, 14) < co.
Thus, for any 0 < e < we get by invoking Theorem that for up 2 supsEF, EX_D [I[(X) - Ex~D [S(X)] [)],
m 2 400-1000p
and 2 ko(8/8), 10 (2) 50 (D((De//0.
it holds with probability at least 1 - 8 over
6
X ~ (Dmy" that: For all f E FR
MOM X)=
E X
(X(')| Se
which would conclude the proof.
To the end of showing that F& admits the above claimed D D-discretization, let 0 <E< 1, < < 1, m 2 1 and
2 (0). Now for each E (1....,k) K}, let G3 be the event
2
m
G =
$ 12 . 8000
(29)
3m
Now by Markov's inequality o² < 00 and that s(x)
sd) o²
+ it follows that
P
[G]]
S
E X Ki Xx.xX
m
1
12
(30)
3m
12 8000
12:
8000
8000
which implies that Pxj, Xi X Dm [G 2 1- 8000 Now since the random variables X Xi. X3 for i E fI..... k.) are independent get that the events G; are independent, and it follows by an application of the multiplicative Chernoff bound, and k 2 ko()) 2- 8 In (e/8) that
Σ 1 (G) 8000
E
Σ Σ1 (G.)
S exp (-2 8000
K
S 5.
(31)
Xo (Dm)"
2.
Thus, we conclude that with probability at least - 5 over
X1, X2, X1,
it holds that 1- (i:ie [x]. 1 is such
that [7] 2 (1 1 E E. (G,)) 2 (1 sobo) where the last inequality follows from Equation (30). Now consider
any realization Xo, X1, X2 of Xo, X X2 such that | 2 (1 subn) 1x. Now by the definition of G, in Equation (29) have that
2 m s(X;
ΣΣΣ
12 8000.
(32)
3m|
NET 1=
Now let X denote the points set U =
/t/36 -f
E T 10,1, 31 E [m] such x: = X so with out multiplicity,
and define the distribution De on Xc. where Da(x) Σiel Σ I [=x;,==] so assigning points in XG weight
3m ||
19

---

Uniform Mean Estimation for Heavy-Tailed Distributions via Median-of-Means
after their multiplicity in X for i I. We notice that with this distribution we have that
X3 =
E X X~Da
[x(X] = Σ
s())Do(2)=
E
((x)
3m///
re
xEXo iE!
S 12000000
(33)
3ml [
ET 1=1
where the last inequality follows by Equation (32).
We now invoke Lemma C.2 to get an upper bound on the size of a maximal + to L1 (D)) of size at most 8 (6-10"eBx-
3-10" paacking of Fx(Xa) with respect with dj = Pk)m We here make a small remark about the invocation of Lemma C.2, Our s is only an upper bound on s'(x) = sup f(x) (by Lemma C.I), thus we actually invoke Lemma C.2 with s' and get that for e' = min( 3-104: Ex-Do [s' (x)]) the size of maximal e'-packing is at most 2e De |s' (x))
2d,
2dz, We notice that if E' Ex~Da [x(()), then since Ex~Da [s(X) N by Lemma C.1 and
6-110* lx)))) 2ds if a-10. the above also an upper bound since s' S s. Furthermore, the size of maximal e'-packing of Fs in (Dc) is larger than the size of a minimal e'-net of Fy in L1 (DG). Thus, the above also gives that the size of minimal 3-104 -net of F& in L, (Da) is at most
KEE < 1, it holds that 8 (2Ex-
2ds
W 8
6.10 Bx [x(]]
2dx
8
By Lemma C.I, we have that dg S 6k(dd 4) In (6k) In (2) 70kd (6h). By Equation (33) 3-10 net of Fx(X)) in terms
we have that EX [s(x)] S 12 8000. Thus, we have argued that the size of a minimal 2ds < 8 77-10" -0000
6.10'' 6x100=3xxpp
140kd (6k)
(D, Let F (XG. L1, De) denote a minimal 3-104 -net for Fx(X)) with respect to (D(D),, i.e has the following property, for f E (XG)), there 3f' E Fg such that
of L1 (Dc) is most 8
2 m f(X) - F(( ΣΣ iET 10
E lf(x) -f(x)) X-DD
(34)
3 10
3m|
and any other set with this property has a size less than or equal to |Fll the above last equality follows by similar calculations as in Equation (33) (using the definition of Dg). In what follows we will for f E Fi use rff) for the element in F' closest to f with ties broken arbitrarily.
Let now f FR. We define I to be the following subset of [x:].
(S(X))) - +()(
1
d E [<]. E (0,
Σ
(35)
m
We first notice that by Equation (34) we have that
I(X;)) - 8(XW)
3- 10
3m I
3/4
HETnI 1=1
which implies that sllll| we conclude that
1 104
14| S
6 104.
Furthermore since |/| (1 8000
1 )r, implying 1 < (1 -(1
8000 )m)n,
1
1
2
104
+1 +1 (1
7mnc )0000))p <
8000
625 k.
Thus, we have shown that for the realization Xo, X1, there exists set of functions F. defined on Xo. X1, X2 such that 2
X1,
for o E Fv there exists (f)) E F. and I, such that [T,l S 625 n. and for i E [K] and j E {0, 1,2) } we have that (see
In the case that Ex~D (6' (x) 0 we have (x) for x E X6, and we take the cover to only consist of the 0 function on NG. as s' (x) 2 f(x) 2 0 so must zero on XG, thus we assume that ex~Da > 0.
20

---

Uniform Mcan Estimation for Heavy-Tailed Distributions via Median-of-Means
Equation (35) that
- S
1n (6k)
and [e < 8
72-10 10 12-000.8000e 88006
(D,, e, m) (see the argument above Equation (34)). That is Fx admits a
e-discretization on Xo. X1, X2 of size at most |P 72. 12-100-8000- 8000c ln (64)
= =N, m, for 0 < < < = en- We showed the above for realization Xo. 11, X2 such that Xo. X2 such that |1] 2 (1
1 )x, which happens with
8000
probability at least 1 - å for 2 (o) = 2 8000 In (e/0) and o² < oc by Equation (31). Thus, we have shown that Fk admits the claimed D-discretization which concludes the proof of Proposition C.3.
D. Linear Regression
In this appendix, we consider continuous positive loss function Q E [0, 20) and the function class induced by the loss function l when doing linear regression with constraint on the norm of the regressor of W > 0, formally we consider the function class
Fw ([(((w,-1),))
[wll| s w} S [0, 00)
That is if f E Fw there exists w E Rdd with squared norm at most W such that for x RR. y R, we have [(xx v)) = E(((wc,- -1), (zr, ((w,,) - y), i.e. the loss function l taken on the residual. To describe our result we for continuous loss function & define for b > 0, the number (a, b) as the largest positive number such that for 2,yE [-a, a) and |x: yl S (a, we have that ((xx) l(v) s b. We notice that since l is continuous and [a, a) is compact interval or (a, b) is well-defined by Heine-Cantor Theorem which ensures that E is uniform continuous on [a, a]. We notice that if l is L--Lipschit then we have that (x b) = +.
In what follows we are going to need the following lemma which gives a bound on an epsilon net of the units ball in Rd in terms of 11-112--
Lemma D.1. Ler < E 1, = fz E CRI, I 1). then there exists a set B S IRd, of size at most (6/c)d being a e-net for (1) in |1-112 i.e. for any x E (1) there exists y E Be such that
||x - yll2 Se.
(36)
We postpone the proof of Lemma D.1 to the end of this appendix and present our main proposition regression for continuous loss function.
Proposition D.2 (Regression). For a continuous loss function l. 0 Dx and Dy over respectively Rd and R. W
L. p S distributions
O,
Up supjeFw EX-Dx, .DDD [f(X, Y Y) Ro(ō)
4 1250 In (e/5), and N(D,
6W where B,,, D) min( (I
w 2
37,0 asl (J,c)
||]] lilllimi ). with
(3W/2+1) 3750 (E [||]|]] + [[]]]) m we then have that for 0 E, m 2
100-16
and n. Z
2²
max (60(6/8), 10a (2) 50 BN(D.g/16.m) )) it holds with probability at least 1 8 over Z = (X. ~ ((Dx x
99
Dy) ) that: For all f e Fw
MoM(J, ()
E
[s(Z')] s.
2'~DxXDy
Before we prove Proposition D.2 we make a small remark on what Proposition D.2 means for Lipschitz losses. In the case
21

---

Uniform Mcan Estimation for Heavy-Tailed Distributions via Median-of-Means
of l being L-Lipschitz loss and that {()) we get that
sup SEFW.
(
5 L
sup WEB(W)
E [K(w, - 1), (X, T)X"]
(by {(0) and é L-Lipschitz)
L" sup wEB(W)
E [[] X) + |
(by la + b - |a| [6]
< (2L)" sup
E [max (tc,, XX| [P
(by a + b S 2 max(a, b))
wEB(W)
$ (2T))
sup WEB(W)
E [u, + [|\]')
(by max b) S + b)
Furthermore as discussed earlier we in this case have that (Je,, tion D.2 implies the following corollary.
و plugging these observations into Proposi-
Corollary D.3 (Lipschitz-loss). For a continuous loss function which is L - Lipschitz and has f(0) = 0.
0 < 8 < 1, < p I 2, distributions Dx and DD over respectively Rd and R, W > 0, 00
Up 2
6W (2L)² (SUPWEB(W) E [1w,, x + +BIIY"")) Ko(8) 4 1250 In (e/5), and N(D, e, m) (e,m,
where
B(e, m, D)- = min( W
2 2 (0000/1111x(|1--1111100 ). we have that for 0 < E, m 2 (
1400-16Ppp)
and k z
gp
max (5))) 10 (2) 50
(N(Dec/16.m) ) it holds with probability at least 1 - 8 over z = (x. Y) ~ ((Dx x
99
D" that: For all f E Fw
E MMM(f. x'~DxxDy
[f(z')]
We now give the proof of Proposition D.2
Proof of Proposition D.2. In what follows we will use Zo = (Xo, Yo). Z, = (X1, Y1), and Z2 = (X2, Y2) and let Dz = Dx x Dy, such that Zi ~ (D2)". We now show that Fw admits a D-discretization with threshold
functions (ō) 4 1250 (e/5), Eo oo and size function N(D,e,
()..D.) where B(e, m, m,
min(
W 2 3750(E[[ X B| ). with J (3W/2 + 1) 3750 (E [I] + E| m. Thus, for any 0 < 8 < 1 we get by l2))) 99
(JL.))
invoking Theorem 3.4 that for 0 < < 80 0o, m N 100-16" op
and k 2 ko(8/8),
50 (NN(Dee/16.m)
holds with probability at least 1 - over Z ~ (D2)* that: For all f E
MOM 2)
[ S 2'
E
as claimed. To the end of showing that Fw admits D-discretization described above let 0 < oc, 0 < < m 2 and (o). We now define the following events for E [x]
m (Xi,) Yia)
2
G:
S 1250 (E |||X|]]] + E BYDD
3m
1=0
j=1
Then by Markov's inequality, we have that
i Yir
1
(G
S E
Zi 23 Dm
3m
1250 (E [I] [1] + E [[]])
1250'
which implies that Pzj, z ~D [G]] 2
1250 Now since the random variables Z Zi Z; for E (1...., k} are independent we get that the events G, are independent. Thus, it follows by an application of the multiplicative Chernoff bound, that for any i 2 n0(8)
1250 In (e/8) we have
N
(1 (1
1250 )k 2. 12502
P Zo, Z1, (Dm)
Σ (G.) <
Σ
(G.)
< exp
8.
(37)
1250
22

---

Uniform Mcan Estimation for Heavy-Tailed Distributions via Median-of-Means
Thus, if we let 1 = {i E [s] : [(G,) }} then by Equation (37) it holds with probability at least 1 8 over Zo, Z1 Zg that [] (1 /250 xx, where we have used that we concluded earlier that P
Zig Zi Zi. 2ij=D= [G:] 2 1 1250 Thus, we have that the size _ = [< is at most | x |/| < K - (1 1250 K S 625 K. Thus, if for Zo. Zi, Z2, outcomes of 1250)*x )2x, we can construct a set of functions F'g (5 is a parameter depending on E, m, D as allowed to in the definition of a D-discretization defined on Zo. Z1, Zz such that for f E Fw. there exists T(f) E F3,
Zo. Z Zg where [4] 2 (1 - 1250
such that for i [s] I it holds that for each 1 {0, 2, that
f(tt)) - T (Z)))))
Σ
SE.
(38)
m
and the size of [Fal < N(,,e,
e, m) then we have shown that Fw admits D discretization, and we are done by the above.
Thus, now show that for outcomes Zo. Z1, Zz, of Zo. Zn, Z2 where | 2 (1 1250 )2k, there exists such an Fa..
To this end consider a realization Zo. Z1, Zz of Zu, Z1. Z2 such that []] 2 (1 1 ) We first notice that for any i E I, I E (0, 1, 2 we have that
1250
(Xi 1 Xi,)
I 1250
3m
which implies that for any j E [m]
[[Xi, ((xi)) S 3750 (E [|]] + [[]]])
Thus, we conclude that for any i E 1,1 E {0, 1, and j E [mm] we have that
[[xt 11 < 3750 (E [I + [[ m.
(39)
Now let B_ = ((e, m, D) = min( :: 3750(E [ Y()m) where J denote the quantity J = 33/2++1
W
a(J.s)
3750 (E [|]] [[ and let F3 denote a G-net in Il-ll--norm for B(W) = { E R2 :1ww|12 S W of mini- mal size, i.c. Vw E B(W there 3ü F3 such that ||w 2|1, S 3, and any other set satisfying this has size at least [Fa). We notice that this implies that for i E Fa we have that || S W + B, to see this let w B(W) and let vt Fg be the points closest to in the net F3, i.e. we have that ||w +6ll S B, and by the reverse triangle inequality we have that W 2 ||m||| > || - || w|l2 > ||00|| l 3 which implies that ||,ا||| S W + 3 as claimed. Now using Equation (39), that 11-112 < |1-I1, and Cauchy Schwarz it follows that for w E B(W), w the points closest to w from Faities broken arbitrarily), i E I, T {0, 1,2] and j E [m] that
(( -1,, (Xi,, Y(a)) - ((w) - 1), (xi X1,) - ((w,-) -1)
(uē - (Xi, X1))1
(40)
2 $B. (|xig (
(by Cauchy Schwarz) (by 11-|22 S 11-111)
8. |()))
MtyIl
$ 3 3750 (E [|]x]]]] +E [[]]) m
(by Equation (39))
and that for any w' E B(W) U
and j E [m] that
K(w', 1(w,,-1),(Xt,
< [ (x,x,,,,,,,1)1 112
(by Cauchy schwarz)
<
(by Va + b S Va + vb)
$ (W +
(by w' E B(W) U F9 so ||l||| S W + 3)
< (W (3++)]](XX,,
(by 11:112 < 11-111) (by Equation (39))
S +3+1) -750 (E [|]]]]++++ ([Y]) m
< (3W/2+1) 3750 (E [|| + E [[ m
(by 3 < W
Let now J= (3W/2 + 1). 3750 (E ||| [1] + [JY]) m and consider (J, z). We recall that by the definition of az E) we have that for x, E [-J, JJ. such that xx yl S (J,eee) it holds that ((x) - {(r)) S e. Thus, by Equation (40) we
23

---

Uniform Mcan Estimation for Heavy-Tailed Distributions via Median-of-Means
have that for any i E 1,1 E (0,1,2) j E [m] and w B(W) with to being the point in Fg closest to w (with ties broken arbitrarily) that
1(w,,- -1), (Xi,) 1. Y(a)) - ((w) -1), (Xi,, Yt) B 3750 (R [[ + E [M]]) m S <a(()e),
by B = min( W 2 3750[[]|| [|]] ) which implies that
a(J.s)
(()( m(a)i) - -1)
-1), k(aii) E
and furthermore for i E I and I E 10,
L ( (w. - 1), (Xi k2 (()))) - ( k(5))
Se
m
which concludes Equation (38), i.e. that Fs (formally speaking & compossed with the vectors in F3) is e-discretization of the realization Zo, Z1, Zz of Zo, Zi, Zg. Furthermore, by Lemma D.I and 3/W I 1/2 there exists a net B3/w of B11) with precision 3/W in |1-112 of size at most (6W/3)4. We now notice that for any E B(W), since ve
W E B(1)
we have that there exists w E B3/w such that ll w - u| 2 S w which implies that ||w - W W I 3,, i.e. shows that W Ba/w= = {10] vb = w' for w' E Bayw) J. is a B net for B(W) in 11-112- Thus, since F3 was chosen minimally (in terms of size) over such nets, we have that the size of FFl S
d
GW g
W where 3 = 3(e, m, D) = min( 2 3750(E[I|X] i +)+
(y(e.))
with = (3W/2 + 1) 3750 (E [II X [11] + E [I]]) m. Which concludes the claim of Fw having a D-discretization
with threshold functions Eo = o0, Ko 4. 1250 In (e/0) and size function N (D,,
6W
where
(E.m..D)
3(e, m, D) = min
W T 3750(E] a1,.))
1 with J = (3W/2 + 1)-3750 (E [|]] + [|]]] m and further concludes
the proof.
We now give the proof of Lemma D.1
Proof of Lemma D.I. In the following we are going to need that the volume of a ball in Rd of radius r is Vol(B(r)) = Tid/2+1) nd by 1iiii,,, where I is the Fuler's gamma function. It will also be convenient to introduce some notation for balls centered at a point x E Rdd of radius r, will use B (xx, r) = (vly E TRd, || vll2 S r) for such balls.
4/22
Now let Bg be a maximal e packing of B1), that is B, S B(1) and for any x,y E B,, where x * y, we have that || - vll2 2 and any other subset of B1)) with this property has size less than or equal to B,. We notice that B, must also be a e-net for B1)) since else there exists x E B(1) such that for all y E Be we have that || yll2 > E, but then x could have been added to the maximal packing Be, leading to a contradiction with the maximality assumption of Be. We now argue that the size of Bg is (6/s)², which would conclude the proof since we just argued it is a s-net in |1-112 for (()).
First since Bg is packing it must be the case that if we place a ball on each point in B, of radius e/3, then these balls must be disjoint. To see this assume it is not the case i.e. there exists x, y E B, such that x # y and the balls B B(x, Bxx,e/3) and e/3) centered and y of radius e/3 has a nonempty intersection B (2r, e/3) 0 B (y,, e/3) * 0. Now let be any point in this nonempty intersection, then by the triangle inequality have that ||x 2ll S ||x =|12 || ull2 S 25 leading
to contradiction with Bg being e-packing, i.e. all different elements being & away from each other.
Thus, we conclude that the balls centered at each point in B. of radius E/3 are disjoint, which implies that the sum of the volumes of the balls centered around each point in Be, which is ΣLEB, (0l(z,e/3) = BB Vol( (B(c/3)), are equal to the volume of the union of all these balls Vol(UzeR, B(x,ee3)) = Exen, Vol(z,e/3) = |B& Vol(B())3))
We now notice that any point in ball of radius e/3 of point in B: has norm at most + E/3. To see this let x B and y E (zx e e3) be point contained in the ball of radius e/3 around v. then have by the triangle inequality that [1vll2 < ||ا||| + lly 2:1l2 < 1 1 e/3, where we in the last inequality used that B, C BII) such that ||x]| < 1. Thus, we have that the union of the balls of radius e/3 centered at points in Be, Use B, e/3), is contained in the ball of radius 1+ U (xx,e/))) C BB1 +/3)..
Thus, we conclude that [B& (ee(3)) = VollUZEB. B(2,e/3)) < Vol(B(1 + e/3),. where we used that we earlier conclude that the union of the balls of radius e/3 centered at points Be, UsEB, Bxx,e/3) have volume |B. Vol VVo(((e/33) B(e/3)).
24

---

Uniform Mean Estimation for Heavy-Tailed Distributions via Median-of-Means
We notice that this implies combined with the formula for the volume of a ball in R& of radius being Vol(B(r))
T(d/241y" proof.
74/2 rdd that [Be] S
Vol(B(1++/3) Vol(B(e/3))
1+t/3)
E/3
S (6)
where the last inequality follows by < 1, and concludes the
E. Proofs of Lemma B.1.
Lemma E.1 (Follows from (von Bahr & Esseen, 1965) Theorem 2). Let 1 S p S 2 and X = (X,, Xm) be iid. with
distribution D. Furthermore let ft m Ei X,, EXinD [1] and Up 2 ExInD [ 111). We then have that
E 1 1) v 20p
(41)
mm-1
Using this lemma and Markovs inequality we obtain Lemma B.1.
Proof of Lemma B.I. By Lemma E.1 it holds for any f E F that
20p
E X-D
- u(f) s
(42)
mp-1"
Using the lower bound of implies that have that
20p
E,
8T18-1
thus by and Markovs inequality and Equation (42) we have that,
P( - >) ( m(f)>>
20p
88mP-1
EE [I((1 - (M())p) 6mp-1
28,
20p
which concludes the proof of Lemma B.1
25


Reviews:
[{"review_id": "fBGjillnHd", "reviewer": "Reviewer_18A3", "summary": "In this paper, the authors tackle the problem of uniform mean estimation under heavy-tailed noise. Considering a set of functions, and a random variable, they analyze the sample complexity of providing a uniformly consistent estimation of the mean of the functions evaluated in the random variable.", "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": "We thank the reviewer for taking the time to read the manuscript and provide feedback. \n\nWe also appreciate the reviewer’s suggestions for improving the organization and presentation by first giving the theorems and then the proof sketch.\n\nWe also make a brief remark on emphasizing that we are not the first to provide uniform convergence bounds under heavy-tailed noise, as described in the manuscript in the **Related Work** section. We differ from previous work due to the focus on the *sample complexity* of the problem instead that on the estimation error. Thanks to a new analysis technique, and due to the introduction of a novel complexity measure that, differently from previous work (focusing instead on the Rademacher complexity), is log of the size of the *relaxed* version of a discretization. Our main result (Theorem 3.4) enabled us to give improved sample complexity bounds in the important cases of k-means clustering and linear regression with general losses, which is instead unclear how to derive from previous work.\n\nIf the reviewer has any further comments, please let us know, and we will do our best to address them.", "claims_and_evidence": "All the claims are supported by proofs.", "methods_and_evaluation_criteria": "There is no experimental campaign.", "theoretical_claims": "I quickly went through the proofs. All of them seem correct and the results are reasonable", "experimental_designs_or_analyses": "There is no experimental campaign", "relation_to_broader_scientific_literature": "Existing literature deal with uniform mean estimation in the presence of non-heavy-tailed noise. This work advances the known results in the field in this sense.", "essential_references_not_discussed": "All the essential references have been discussed.", "other_strengths_and_weaknesses": "The paper presents the first algorithm tackling uniform mean estimation in the presence of heavy-tailed noise. The proofs seem correct and there is a nice technical work.\n\nIn some points the reading is not fluent, especially in the first sections, I would recommend stating the main results before giving an intuition of their proof. Moreover, I would suggest to \"light\" some constants to the closest one-point decimal value, at least. Just to make the text clearer.", "other_comments_or_suggestions": "See above.", "questions_for_authors": "I have no relevant questions.", "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": "vOusVNF9qR", "reviewer": "Reviewer_Libf", "summary": "The paper proposes to use the median-of-means estimator to (uniformly) estimate the mean over a whole real-valued function family, with respect to some unknown distribution with bounded $(1+p)$-th moment that we only get sample access from. The authors give an analysis of the maximum estimation error, under the assumption that the function family satisfies some approximability property with a small cover. They then applied the result to $k$-means clustering and to regression problems.", "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": "We first thank the reviewer for carefully reading the manuscript and providing constructive feedback.\n\n**Relation To Broader Scientific Literature:** We would like to comment on the reviewer's concern about the relevance of MoM in light of novel more refined estimators. We start noting that, similar to the MoM estimator, even the best-known bounds for the trimmed mean suffer from sub-optimal constants in the single mean task (see Oliveira, Ornstein, and Rico 2025, Theorem 1.1.1, for the case $p=2$). In addition, MoM is widely used as a sub-routine of other methods, including in the optimal Lee and Valiant estimator. Furthermore we notice that in the uniform convergence setting, differently from the single mean estimation case, it isn't even clear what the optimal constants are. Therefore, we believe that it still makes sense, to analyze the MoM in the more general uniform convergence setting. We thank the reviewer for eliciting such an interesting discussion.\n\n**Strengths and weaknesses:** We appreciate the reviewer’s efforts in walking us through their experience of reading the manuscript and highlighting that the current introduction of the $\\mathcal{D}$-discretization is suboptimal. Regarding point 5), we would like to provide some high-level intuition about why we chose this weak notion of a net. As the reviewer pointed out, the discretization allows consideration of realizations of the samples $X_{0},X_{1},X_{2}\\in (\\mathcal{X}^{m})^{\\kappa}$ to estimate any function $f\\in \\mathcal{F}$ except on a small fraction of the $\\kappa$ subsamples $X_{0}^{i},X_{1}^{i},X_{2}^{i},$ where the approximation of $f$ can be arbitrarily bad. Since we are considering heavy-tailed distributions, we cannot expect that all subsamples will allow us to estimate the function accurately, thus why we did not see how to show the result with out this definition of the discretization allowing for the discretization to \"fail\" on a small number of subsamples. More specifically, in the case of k-means, we can assert that most of the mean estimates on the subsamples $X_{0}^{i},X_{1}^{i},X_{2}^{i},$ are small, but we cannot make any claims about the remaining mean estimates. With knowledge that the mean estimates on most subsamples are small, we can discretize the functions on these subsamples and disregard the discretization on the remaining ones. A similar argument is used in the proof of regression. As alloted to earlier we did not see a way to prove the theorem without this weaker notion of a net. We again thank the reviewer for emphasizing the need for a more detailed explanation of the discretization, which we will improve in the next version.\n\nIf the reviewer has any additional comments, we would be happy to address them.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "I didn't check the proof details, but the high-level proof strategy does look like it should work. I have no correctness concerns.", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "The uniform mean estimation problem is well-studied in the literature, both in the finite variance case (or bounded variance case, for Catoni-style estimators) and in the finite $1+p$-th moment case. Methods have been proposed, based on median of means, trimmed mean, and Catoni's estimator. This paper uses a symmeterization argument different from prior works.\n\nA small personal gripe (though I don't actually reduce my score based on this) is the use of median-of-means. We know that the estimator is awful both theoretically and empirically, in the vanilla mean estimation problem (without any function classes). Both its finite sample performance and its (fix $\\delta$, take $n \\to \\infty$) asymptotic performance are off by constants from optimal (definitely in the $1+p = 2$ case), which show up empirically. On the other hand, trimmed mean is at least asymptotically efficient, and the recent Lee and Valiant estimator is optimal in the constants both finite-sample and asymptotically. All of these other estimators are also minimax-up-to-constants optimal in \"heavy-tailed\" settings too, so it doesn't seem very good to still talk about median-of-means still, as clean and simple an idea it is.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "While the paper clearly *explains* the proof, I don't think it does as good a job with *motivating* the analysis and assumptions.\n\nLet me walk the authors through what I was thinking when reading the paper, including an initial misunderstanding, the subsequent confusion and a partial resolution. Hopefully this can help improve the technical narrative in the paper.\n\n1. Read the main sample complexity result. The form of the sample complexity looks easy to interpret -- it looks like a covering number term inside the log, so at this point I'm expecting a covering on the function class, and then a union bound net argument + approximation guarantees in between net elements.\n\n2. I checked the assumption. The notion of D-discretization looks like what one would expect -- each $f$ gets mapped to some $\\pi f$ in the net, so that $\\pi f$ approximates $f$ well (Definition 3.1 has the sum of absolute differences over the samples being small, which is a strong condition). Then I was wondering, but why do we need the *three* sample sets? It clearly has something to do with the symmeterization argument that was foreshadowed, but why do we need that?\n\n3. In fact, at this point I was wondering, why not do the obvious thing of taking a union bound over the net elements (with the net over the function class), and then use D-discretization to fill out the rest of the function class?\n\n4. It took a while before I saw that the net in fact depends on the set of samples, which is why the simpler net argument fails. The D-discretization approximation condition is weaker in quantification than what one expects for a net argument. The key quantification difference is somewhat buried, and as a reader, it would be really helped if the difference was highlighted and emphasized.\n\n5. But this still leaves the question, why was the weak notion of D-discretization used (which then seems to necessitate the complicated symmeterization), instead of the stronger \"we have a single net that works for the entire function class (with high probability)\" quantification? Is it because the latter stronger notion is impossible to prove for the applications at hand? If so, why, and shouldn't the applications then be the main point of the paper instead of just \"median-of-means can be used for uniform mean estimation\"?\n\n=============\n\n**Post-rebuttal discussion**: Thank you, this is exactly the sort of discussion I was looking for (as someone who hasn't paid too much attention to covering-based results), that prior works haven't found sample-independent covers. I have now raised my score, under the assumption that the authors will include this technical motivation and discussion of quantifiers in the paper.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "Please clarify the technical motivation as discussed above.", "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": "nUdqVVyGUh", "reviewer": "Reviewer_giju", "summary": "The authors study the uniform convergence problem, i.e., estimating the mean of a set of functions simultaneously over inputs randomly sampled from an underlying distribution. Specifically, the authors focus on the classical median-of-means estimator that has celebrated performance on traditional distributional mean estimation, in particular in the heavy-tail regime. They show that median-of-means, under mild assumptions that the function class of interest can be \"discretized\" in some suitable sense, admits near-optimal sample complexity to achieve additive estimation error $\\epsilon$ simultaneously over all functions in the class with probability $1-\\delta$.\n\nTo prove their main theorem, the authors employ novel analytical techniques, including a novel symmetrization-discretization-permutation pipeline on the mean estimates from each bucket. They show that (1) for uniform mean estimation to fail, there must exist a function for which median-of-means has vastly different performances on a pair of symmetric inputs, (2) the function class can be discretized via a \"relaxed $\\epsilon$-net\" argument to allow union bounds, even if the class is unbounded, and (3) for any fixed function, it is highly unlikely that mean estimate performs vastly differently on the symmetrization introduced in (1). The authors supplement their general theoretical findings with applications to clustering and linear regression, and raises questions of finding lower bounds to the problem setting.", "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 the reviewer for taking the time to read the manuscript carefully and provide feedback.\n\n**Theoretical claims:** We would like to address the reviewer’s comment about the magnitude of the constants in Theorem 3.4. We agree that the constants differ from the empirical mean estimate of a single function, and we provide the following explanation. The main reason for the larger constants is that we are trying to estimate multiple functions (possibly infinitely many), unlike in the case of a single function. In achieving this goal, the symmetrization, discretization, and permutation steps each introduce additional constant factors into the final bound, which leads to the larger constant. Furthermore, we did not optimize the constants in the proof of Theorem 3.4. We believe it is a good idea to add a comment about this in the next version of the paper and thank the reviewer for suggesting it.\n\n**Experiments:** We are pleased that the reviewer does not necessarily require us to include experiments in the paper, although we agree that it would be exciting to see the results of such experiments. However, conducting such experiments is quite involved. Testing for uniform convergence  would require running MOM and the empirical mean estimate on all possible functions in the function class and then taking the maximum of the error. If the function class is infinite, this is not feasible. Thus, one would need to develop a reasonable discretization that is both computationally tractable and sufficiently fine-grained to simulate uniform convergence over the class in the heavy-tailed case.\n\n**Relation to broader scientific literature:** We also make a brief remark on emphasizing that we are not the first to provide uniform convergence bounds under heavy-tailed noise, as described in the manuscript in the **Related Work** section. We differ from previous work due to the focus on the *sample complexity* of the problem instead that on the estimation error. Thanks to a new analysis technique, and due to the introduction of a novel complexity measure that, differently from previous work (focussing instead on the Rademacher complexity), is log of the size of the *relaxed* version of a discretization. Our main result (Theorem 3.4) enabled us to give improved sample complexity bounds in the important cases of k-means clustering and linear regression with general losses, which is instead unclear how to derive from previous work.\n\n**Relation with Lee and Valiant 2022:** We thank the reviewer for pointing out the breakthrough work from Lee and Valiant on optimal mean estimation. As noted above, while we didn't attempt to optimize the constants in our bounds, moving from the task of estimating a single mean to that of estimating the means of each function in a possibly infinite class is likely to introduce additional (and potentially large) constant factors for any estimator. On top of that, often, the estimates of *size* of the particular function class of interest suffer from possibly large constant factors that may hide the benefits even of asymptotically optimal estimators. As a result, proving bounds with optimal constants (which, at the best of our knowledge, are still unknown) in uniform convergence, is likely to require alternatives to the symmetrization, discretization, and permutations, in addition to the adoption of more refined estimators (e.g., Lee and Valiant 2022). This challenging problem is an interesting research direction for future work, and we will mention it in the next version of the manuscript.\n\n**Strengths and weaknesses:** We thank the reviewer for highlighting that we could have presented some of the more technical details in the proofs more intuitively and accessibly. For instance as pointed out of the reviewer, the definitions of $\\hat{S}\\_{b}^{>}(f,\\varepsilon)$ and $\\hat{S}\\_{b}^{\\leq}(f,\\varepsilon)$ could be better explained, and we will do it in the revised version.\n\n**Other Comments or Suggestions:** We also thank the reviewer for providing several suggestions for improvement, which we will incorporate into the next version of the paper.\n\nIf the reviewer has any further comments please let us know, and we will do our best to address them.", "claims_and_evidence": "The claims are believable and reasonable with supporting evidences. Median-of-means enjoys many folklore properties even beyond standard setting and heavy-tailed mean estimation, so I do not find the authors' conclusion surprising; It is however very nice to see a formal analysis of median-of-means under this setting. \n\nWhile there are some details that can be illustrated better, the authors did also provided a relatively clear and intuitive proof to their results, and devises novel mechanisms for their analysis, which I believe should be appreciated.", "methods_and_evaluation_criteria": "The model chosen by the author, including the problem setting and the optimization over sample complexity, is standard for mean estimation and its derived problems. While the authors make assumptions on the discretizability of the input function class, they provide evidences that the assumption is mild and reasonable.", "theoretical_claims": "While I haven't examined technical content in the finest details, especially their choice of universal constants, the theoretical claims are reasonable to my best knowledge, and I do not identify any major issues with their proofs and analyses. \n\nI am somewhat concerned with the universal constants in their sample complexity (Theorem 3.4), which seems to have quite large magnitude even in the standard finite-variance setting. A short discussion about the reasonableness of these constants (perhaps in comparison to the performance of empirical mean on settings for which it is shown to be optimal) will strengthen the authors' claims and arguments.", "experimental_designs_or_analyses": "This submission is focused on the theoretical analysis of median-of-means for uniform convergence mean estimation, and does not provide any experimental analysis. \n\nI do not believe that any experimental setup is necessary, but it would be interesting to see experiments that compare the performance of empirical mean and other celebrated mean estimators to median-of-means on uniform convergence - if an appropriate experimental setup is available. For many mean-estimation related problems, especially in more general settings, the empirical mean often outperforms other sophisticated estimators that admit rigorous theoretical guarantees; I find it interesting to ask if this is the case in uniform convergence as well, or if the heavy-tailed regime calls for more sophistication than simply taking the empirical mean.", "relation_to_broader_scientific_literature": "Median-of-means is a well-celebrated and extensively studied mean estimator that enjoys many robustness properties in many extended regimes from classical finite-variance mean estimation, some of which folklore. The authors formally analyze its performance for the uniform convergence problem under heavy-tailed regimes, which to my and the authors' knowledge is the first such formal analysis. Previous works have studied other classical estimators under more limited or incomparable models, such as empirical mean under finite dimensional constraints, or trimmed mean with adversarial contaminations and fixed sample.\n\nThe authors' proposed novel techniques, including the alternative symmetrization of median-of-means and discretization of unbounded function classes, are potentially of independent interests for future work on mean estimation as well.", "essential_references_not_discussed": "To my knowledge the authors cite and discuss essential related literature comprehensively.\n\nOn a more peripheral aspect, relating to my aforementioned concern about the universal constants in Theorem 3.4: A line of work in finite-variance distributional mean estimation starting from Catoni (2012) culminates in the Lee and Valiant estimator (FOCS 2022), which achieves the optimal estimation error even up to constants. While it is unknown what the optimal constants are in heavy-tailed regimes, the Lee and Valiant estimator is believed to outperform and enjoy better constants than median-of-means as well. I wonder if there are evidences, theoretical or empirical, that rationalizes the magnitude of the universal constants the authors choose.", "other_strengths_and_weaknesses": "The paper is overall relatively well-written and clear, but due to the technicality of their proofs and analyses, I believe some of the claims and definitions can be better motivated and intuited. As an example, in the analysis in Section 3.4 on page 5, the right column contains high-level explanations of the flow of the authors' argument in proving Theorem 3.4, with Lemma 3.6, 3.7, and 3.8, which in conjunction with Figure 1 on page 3, is very nice and appreciated, and paints a good high-level picture of the overall structure of their proof; the definitions of $\\hat{\\mathbf{S}}_\\mathbf{b}^{(b)}(f, \\epsilon)$ on the left column of page 5, however, are built upon many layers of prior definitions and are technically convoluted, without an immediately clear interpretation of what they are supposed to represent. A brief explanation (such as something along the line of \"the fraction of the mean estimate with large/small deviation on different samples\") may be necessarily helpful.\n\nThere are also some minor typos which I outline below.", "other_comments_or_suggestions": "- While to my knowledge not enforced by the ICML submission style requirements, I believe it reasonable to format in-line citations such that the sentence is complete after removing the citations: for example, in Section 2, page 2, right column, instead of \"...special case of the formulation given in (Oliveira & Resende, 2023) except...\", use \"...special case of the formulation given in Oliveira & Resende (2023) except...\".\n- In Section 3.2, page 3, there are multiple references to \"Section 2\" that appears to be referencing Figure 1 instead.\n- Section 3.2, page 3, left column, line 160 1/2: Use `` instead of \" for the left double quote.\n- Section 3.4, page 5, left column, line 259 1/2: It is unclear immediately what does it mean for a random vector to be symmetric; A lot of other symmetric properties are not clearly defined in the paper as well.\n- Section 3.4, page 5, right column, line 247 1/2: Extra comma in \"...this discretization perserves, the imbalance...\"", "questions_for_authors": "N/A.", "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": "Dx2YwdLnHE", "reviewer": "Reviewer_xSiA", "summary": "The paper examines the Median of Means (MoM) estimator for estimating means in heavy-tailed distributions. The authors derive a new sample complexity bound using an innovative symmetrization technique. They also present applications of this technique to k-means clustering with unbounded inputs and to linear regression with general loss functions. Overall, the study introduces a novel symmetrization method to achieve these results.", "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 the reviewer for taking the time to read the manuscript and provide constructive feedback. \n\nIn the following, we will address the reviewer’s comments in the order they were given, except for those regarding experiments, which we will address last.\n\n**Claims and Evidence:** We first address the reviewer’s comment on the main results being quite technical and difficult to follow. We will add further explanations in the paragraph following Theorem 3.4. Specifically, we will clarify that the precision parameter $\\varepsilon$ affects both $m$ (the number of samples used in each mean estimate) and the precision of the net, with the intuition that we want both the mean estimates to be $O(\\varepsilon)$-close to the mean and the \"rounding\" in the net to have precision $O(\\varepsilon)$. Additionally, we will clarify that $\\delta$ influences only the number of mean estimates $\\kappa$, as this parameter is used to increase the probability that more than half of the $\\kappa$ mean estimates are successful - this ensures that the median of the mean estimates, which is the output of MoM, is correct. We appreciate the reviewer’s suggestion to clarify this point.\n\n**Theoretical claims:** We agree that readability would be improved by keeping the constants in Lemma 3.8 as $c=\\frac{4769}{10000}$ instead of $a=\\frac{4769}{10000}$ and $d=\\frac{331}{1000}$ instead of $b=\\frac{331}{1000}$ to mirror the constants in Lemma 3.7. We will make this correction in the next version of the paper.\n\n**Methods And Evaluation Criteria:** We thank the review for pointing out that the estimator could be better presented. We will make an pseudo-algorithm environment illustrating the procedure of the MoM.\n\n**Weaknesses:** We thank the reviewer for pointing out that some of the theoretical assumptions could be more clearly stated. For example, in Theorem 3.4, we did not explicitly state that $\\mathbf{X}=(\\mathbf{X}\\_1,\\ldots,\\mathbf{X}\\_{\\kappa})$ is drawn from $(\\mathcal{D}^{m})^{\\kappa}$, so that $\\mathbf{X}\\_i \\sim \\mathcal{D}^{m}$, making it unclear what $\\text{MoM}(f,\\mathbf{X})$ means: $\\text{median}(\\mu\\_{f,x\\_1},\\ldots,\\mu\\_{f,x\\_{\\kappa}}).$ We will correct this in the next version of the paper, along with other suggestions from the reviewer to improve clarity.\n\n**Experiments:** As also mentioned by reviewer (giju), including experiments would be interesting, but we were pleased that neither reviewer required us to do so. Conducting such experiments would be quite involved. Testing the uniform convergence property would require running the estimation method (in this case, MoM) on all possible functions in the function class and then taking the maximum error. If the function class is infinite, this is infeasible. Thus, one would need to develop a reasonable discretization that is both computationally tractable and fine-grained enough to simulate uniform convergence over the class in the heavy-tailed case.\n\nWe thank again the reviewer for their feedback and hope that we have addressed their concerns. If not, please let us know, and we will do our best to address them.", "claims_and_evidence": "Yes, the authors provided theoretical to support their claims. However, I have some comments on some problematic claims:\n\nThe expressions in the main results—Theorem 3.4, Theorem 4.1, and Theorem 4.3—are not reader-friendly and can be difficult to follow. The meanings of \\(\\epsilon\\) and \\(\\delta\\) in the final formulas are quite ambiguous, and their relationship is not directly explained. This lack of clarity makes it challenging to understand the claims and complicates evaluation and comparison with previous works.", "methods_and_evaluation_criteria": "1. No benchmark datasets are provided to demonstrate the application of the methods.\n\n2. The paper does not clearly present the proposed method; for instance, there is no algorithm table showing each step of the process. This ambiguity makes application and evaluation very difficult.", "theoretical_claims": "The notations in the theoretical proof are very ambiguous and contradictory, making it difficult to verify its correctness. For example, in Lemma 3.7 on page 5, the values are given as a = 4801/10000 and b = 9701/10000. However, in Lemma 3.8 on page 6, the values change to a = 4769/10000 and b = 331/10000. This inconsistency renders the proof problematic.", "experimental_designs_or_analyses": "This paper doesn't have experimental designs or analyses.", "relation_to_broader_scientific_literature": "The ideas in this paper can be applied to k-means clustering with unbounded inputs and to linear regression with general losses, enhancing the existing approaches.", "essential_references_not_discussed": "The literature review is extensive.", "other_strengths_and_weaknesses": "**Other Strengths:**\n\n1. The motivation of the paper is clear.\n\n**Other Weaknesses:**\n\n1. The assumptions of the theoretical analysis are not clearly stated. \n\n2. The expression MOM in Theorem 3.4 is not well-defined; a clearer expression would be more reader-friendly.", "other_comments_or_suggestions": "1. Experimental analysis is preferred for readers.\n\n\n=============================\n\nPost rebuttal updates: Thank you for your detailed response to my reviews. I appreciate that all of my concerns have been addressed. I will increase my overall ratings based on the discussions in the rebuttal section, provided that my concerns and suggestions are included in the next version.", "questions_for_authors": "1.Is it possible to include some experimental analysis on the real data?", "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: The paper studies the problem of uniform estimation of the mean for a family of real-valued functions, under an an unknown distribution with bounded moments that we can sample. The main contribution is the analysis of the classical median-of-means estimator in thic context, under some standard assumptions on the underlying function family. Applications to clustering and regression are also given. Overall, the reviewers found the question to be interesting and the proof to be novel. Modulo some suggestion on the presentation of the technical results, the reviewers agreed that this paper is above the acceptance threshold.
Decision: Accept (poster)