On the Optimality of the Median-of-Means Estimator under Adversarial Contamination
Authors: Xabier de Juan
Santiago Mazuelas
Venue: NeurIPS 2025 poster ()
Keywords: mean estimation
median of means
adversarial contamination
robust estimation
minimax bounds
minimax optimality
robustness
mom
concentration inequalities
Primary area: theory
TL;DR: We theoretically characterize MoM's optimality for different classes of distributions under adversarial contamination

Abstract: The Median-of-Means (MoM) is a robust estimator widely used in machine learning that is known to be (minimax) optimal in scenarios where samples are i.i.d. In more grave scenarios, samples are contaminated by an adversary that can inspect and modify the data. Previous work has theoretically shown the suitability of the MoM estimator in certain contaminated settings. However, the (minimax) optimality of MoM and its limitations under adversarial contamination remain unknown beyond the Gaussian case. In this paper, we present upper and lower bounds for the error of MoM under adversarial contamination for multiple classes of distributions. In particular, we show that MoM is (minimax) optimal in the class of distributions with finite variance, as well as in the class of distributions with infinite variance and finite absolute $(1+r)$-th moment. We also provide lower bounds for MoM's error that match the order of the presented upper bounds, and show that MoM is sub-optimal for light-tailed distributions.

On the Optimality of the Median-of-Means Estimator under Adversarial Contamination
Xabier de Juan' Santiago Mazuelas'
Basque Center of Applied Mathematics (BCAM)
2 IKKEBBASQUE-Baap Foundation for Science {xdejuan, smazuelas)@bcamatth org
Abstract
The Median-of-Means (MoM) is a robust estimator widely used in machine learn- ing that is known to be (minimax) optimal in scenarios where samples are i.i.d. In more grave scenarios, samples are contaminated by an adversary that can inspect and modify the data. Previous work has theoretically shown the suitability of the MoM estimator in certain contaminated settings. However, the (minimax) optimal- ity of MoM and its limitations under adversarial contamination remain unknown beyond the Gaussian case. In this paper, we present upper and lower bounds for the eтrог of MoM under adversarial contamination for multiple classes of distri- butions. In particular, we show that MoM is (minimax) optimal in the class of distributions with finite variance, as well as the class of distributions with infi- nite variance and finite absolute (1 (1+r)) moment. We also provide lower bounds for MoM's s error that match the order of the presented upper bounds, and show that MoM is sub-optimal for light-tailed distributions.
Introduction
The Mfdian-of-Means (MoM) estimator is widely used dinennnnnia estimator of the mean. First introduced in the 1980s in [1]. it has recently gained significant attention from the robust machine learning community. For example, MoM has enabled the development of robust alternatives for empirical risk minimization [2) kernel methods [5, G). and clustering techniques 77]. MoM is attractive robust univariate mean estimator in scenarios affected by heavy tails [8-1]] In
particular, MoM known to be a (minimax) optimal estimator of the mean in the i.i.d. scenario for heavy-tailed distributions [10., together with the trimmed mean [12], Catoni's M-estimator [13] and the in situations where data samples are contaminated by an adversary.
estimator [14]. Moreover, as shown in (15. [6]. MoM is also an adequate estimator
Adversarial contamination a general type of data attack in which the adversary is allowed to first inspect the clean samples, then remove proportion of them, and finally add new samples [17]. These types of attacks can be specifically designed to maximize the damage caused to a subsequent be especially harmful in fields where data integrity is crucial, such as cybersecurity (20), biometrics [21], and autonomous driving (22)- Motivated by these concerns, the robust machine learning community has shown strong interest in
learning process [18. [19]- Adversarial contamination
the problem of mean estimation under adversarial contamination 17. 23 25
The (minimax) optimal error under adversarial contamination depends both the fraction of con- taminated samples a and the class of distributions considered (24]). The optimal error exhibits two regimes: (1) for reduced enough number of samples, the optimal error matches that in the i.i.d. scenario; (2) as the number of samples increases, the optimal error plateaus at a level determined by and the class of distributions considered. The error in the second regime is known as the asymptotic bias and describes the unavoidable error due to adversarial contamination. Therefore,
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

such bias characterizes the optimal error for each class of distributions. Table [I shows the order of the asymptotic bias corresponding different classes of distributions and mean estimators.
Table 1:
Order of the asymptotic bias of the optimal estimation error for different classes of distribu- tions and mean estimators. Expressions in blue denote that the order optimal in the corresponding class, while empty cells indicate unknown results. We denote by a the fraction of contaminated samples.
MoM
Trimmed Mean
M-estimator
Finite Variance: P2
a [this paper]
24
v@ [25]
Infinite Variance: Pitr
[this paper] a 2/3 [this paper] a [this paper]
a [25]
Sub Babb-Gassiim: PsG
a log (1/a)
(24]
Symmetric: sym
Gaussian: Pg
a e.g., (26, 27]
a avlog
[24]
In the class of distributions with finite variance, the optimal order of the asymptotic bias is /o and both the trimmed mean and Catoni's 's M-estimator are known to be optimal in this class 24. 25). In the class of distributions with infinite variance and finite absolute (1 + r-)th moment, the optimal order of the asymptotic bias becomes a -î., and Catoni's M-estimator is known to be optimal in distributions, the optimal asymptotic bias improves to ay log(1 1 /a),, and the trimmed mean is known to be optimal in this class [4 The asymptotic bias
this class (25). In the class of
can be further improved to a in the class of Gaussian distributions 28 but the trimmed mean is
known to be sub-optimal in this class (24).
Previous work has theoretically shown the suitability of the MoM estimator certain contamination scenarios. In particular, the results in (15) provide upper bounds for MoM's error for finite-variance distributions, with rates matching the optimal order in the i.i.d. scenario. In addition, MoM has been shown to be (minimax) optimal for Gaussian distributions since it generalizes the sample median (see e.g., (66), (27. Cor. 1.15). However, the (minimax) optimality of MoM remains unknown beyond the Gaussian case, mentioned in [25]_ Specifically, previous work MoM considered more benign contamination model and only studied the regime with a reduced number of samples, i.e., not the asymptotic bias. Moreover, the limitations of MoM under adversarial contamination remain unknown, as no lower bounds on its error have been established.
This paper provides upper and lower error bounds for the MoM estimator for multiple classes of distributions under adversarial contamination (see Table D. In particular, the results reveal that MoM is (minimax) optimal for heavy-tailed and symmetric distributions, but sub-optimal for light- tailed distributions. Specifically, the main contributions in the paper are as follows:
We prove that MoM optimal under adversarial contamination in the class of distributions with finite variance, well as in the class of distributions with infinite variance and finite absolute (1 + r)-th moment.
We obtain upper bounds for the error of MoM in the classes of sub-exponential and sub- Gaussian distributions, which improve upon those established for the finite variance case.
We obtain lower bounds for MoM that match the order of the presented upper bounds. In particular, we prove that MoM cannot fully exploit light tails and is sub-optimal for sub- exponential distributions.
We prove that MoM is optimal under adversarial contamination in class of symmetric distributions that includes Gaussians and heavy-tailed distributions such as Student's 's t.
The rest of this paper is organized as follows. Section 2 describes the problem of mean estimation under adversarial contamination. with finite variance, and infinite variance with finite absolute (1 + r)-th moment. In Section 4 we present error bounds for MoM for light-tailed distributions, where we obtain improved orders compared to the finite variance case. In Section 5 we prove that MoM attains even better orders in a class of symmetric distributions. All proofs are deferred Appendices A and B Finally, we
Section we present the optimality results for distributions
illustrate the results in the paper with numerical experiments in Appendix

---

Notations. For real number [x] denotes the smallest integer greater than or equal to 2, and [ denotes the greatest integer less than or equal 2. For 1. P. denotes the set of all probability distributions with finite absolute s-th moment. Given set of real numbers I1; 222, ................................ Zn. we
denote by ((1); (()).......... F(n) their non-decreasing rearrangement. The notation S describes cases where there exists constant such that x S cy. In addition, the notation æ X describes cases where r S and S x.
2 Preliminaries
This section begins by formulating the problem of one-dimensional mean estimation under adversar- ial contamination. We then diseuss (minimax) optimal mean estimators and conclude by recalling the definition of the MoM estimator.
2.1 Contamination model
Let Xi. R be i.idd samples drawn from a distribution p with finite mean Pp and variance og. For some contamination fraction a, the adversary changes most of the samples, and the resulting contaminated samples are denoted as X1, X2.... X,. This situation is referred to adversarial contamination, and be mathematically modeled follows.
Definition
2.1 (Adversarial contamination). We say that X1, N1, N......... Xn, a-contaminated samples if there exist i.i.d. samples Xi, "i.X..... X and indexes < ip with I (1 a)m, so that
1 S 11 < l2
(X Xi2:-.., X. (2 X;)-
Adversarial contamination generalizes the additive contamination model (also called O PUZ Z model). In the additive case, the contaminated samples X1, X2...., X, contain (1 - a)n inliers drawn in- dependently from together with contaminated samples, for which no specific assumption is made. Adversarial contamination describes more general and harmful types of attacks than the addi- tive model. Conceptually, the distinction between the two contamination models can be understood as follows: under adversarial contamination, the adversary can selectively discard at most on of the samples after inspecting their values, whereas in the additive model, the adversary discards samples randomly. Mathematically, under adversarial contamination, the samples Xi,, X;,) in i just need to be contained in ..,..., X whereas in the additive contamination model they also have to be independent.
2.2 Minimax optimal mean estimators
The goal of mean estimation under adversarial contamination is to approximate the mean Mp using an estimator ğ f Xn) evaluated at a-contaminated samples. Given confidence parameter 8 > 0, we seek to guarantee that, with probability at least 1 1-8
ñ - Hpl S ope(n,6,0)
where E(n, 6, ax) is as small as possible while guaranteeing the bound holds uniformly over all distri- butions p P. where P is class of distributions.
Previous work on mean estimation under adversarial contamination has shown that the class Pa (distributions with finite variance), with probability - 6, the estimation error is at best proportional
Op (V log (og((//)
Va
Specifically, the results in [24] show that (2 is the (minimax) optimal error in Pz. Namely, for any estimator zi the mean, there exists distribution p E P2 and an adversarial attack such that with probability 8, the error jī Mpl is lower bounded by ( up to multiplicative constants. In addition, the expression 2 also provides an upper bound for some estimator for every p Pa and any adversarial attack.
3

---

The order of the optimal error in equation 2 exhibits two regimes depending on the sample size [24]] (I) for reduced enough number samples (when I log(2/6)/a)) the order of the bound takes the form (2og(2/8) /n, which matches the optimal order in the i.i.d. scenario; (2) as the number of samples increases (when n 2 (2(()))/a), the optimal order plateaus at va, which is known the asymptotic bias because it does not decrease with the number of samples. The error in the second regime describes the inevitable error caused by adversarial contamination.
For distributions with infinite variance, there is a similar optimality result [25]. Specifically, if Pi+r the class of distributions with finite absolute (1 + r--th moment, the optimal estimation error in Pitr is proportional to
((108(2/0) Tfr 12
+ a
(3)
where v, Ex-pl X /4p + denotes the absolute (1 r)-th central moment of p E Pi+r. As in the viriin-vrriance case, the first term of the optimal error 3 matches the optimal error in the i.i.d.
scenario for Pi+r. whereas the second term a Tir is the asymptotic bias.
The optimal asymptotic bias has different orders depending the class of distributions considered (see Table for a summary). In the class P2, both the trimmed mean and Catoni's M-estimator are known to be optimal [24. 25 In addition, in the class Pitr. Catoni's M-estimator is known to be optimal (25). If one considers more restrictive class distributions P C P2. the order of the optimal asymptotic bias can be improved. For example, in the class of sub-Gaussian distributions Psc. the optimal asymptotic bias is given by (og(a),,, and the trimmed mean is optimal in this class [24]. addition, in the class of Gaussian distributions Pg. the optimal asymptotic bias is (28). However, the trimmed mean is known to be sub-optimal in Pg [24].
2.3 Mfdian-of-Means
Let X1, Xy..... X,, a. be random samples and [1, Iz................... Ig be i random disjoint blocks of the indices (1,2. n with equal size [n/k] Then, the MoM estimator defined as the median of the means corresponding to different blocks, that
?MOM = (((422)
where
Ex,, JEL
X i= 1,1,,...,
and P([K/2T) denotes the [k/2]-th order statistic.
In the following sections, we present concentration inequalities for MoM under adversarial contam- ination for different classes of distributions.
3 Optimality of the MoM estimator for heavy-tailed distributions
In this section, we establish the optimality of the MoM estimator under adversarial contamination for general classes of distributions. We first define the quantile function which describes the behavior of averages of i.i.d. inliers.
Definition 3.1. Let Xi, XY,...., X m i.i.d. random variables with distribution p and finite mean Mp. We denote by Qm the quantile function of the random variable
XI + X3 +
X
B
Mp-
That is, Qm(g) =
ER E Bm, S x1} for q [0,
As is commonly done for the analysis of the MoM estimator, by taking the floor function we ensure that all the blocks have the same size even when & does not divide n. In practice, some blocks can have larger sizes all the samples, but this does not affect the theoretical results presented.

---

The bounds presented in the paper are consequences of the next theorem that shows how MoM's error described by the behavior of averages of i.idd inliers around their median. In contrast, the emor in other robust estimators is given by the behavior of the tails of the distribution [24].
Theorem 3.1. Let joxoM be the MoM estimator with blocks of size m = [n/k] evaluated a-contaminnted samples. If the number of blocks satisfies 20m > 2exp( 22(11/2 am)²)
n, then for all
1og(2/6) 2k
log (2/6)
a.m }}
[AMMM - Mpl S max Qm +
+ am
Qm 2
2k
(4)
holds with probability at least 6.
Sketch of proof. The full proof is given in Appendix A.1
Without loss of generality, we assume μp = Let {pi be the sample means of the different blocks before the attack of the adversary, and let {ūt J be the sample means of the different blocks after the adversary's attack. By the definition of adversarial contamination, the adversary k at most an samples, which affects at most an of the block means. Therefore, the sets {pt fi=1 and (TrM differ in at most an elements.
modify
Since MoM is the median of the block means, i.c. PMMM = P(pk/2))- we have P([k/2]-an) S JMMMM S P((k//2+tan* Then, the result in follows since the empirical quan- tiles P([4/2]-am) and P([k/2]+am) are close to the actual quantiles Qm(1/2 + am) and (1/2 am).
The result above presents a bound for the error of MoM under adversarial contamination that is valid with wide generality. In the next subsections, derive from Thcorem[..]jth optimal bounds for the different classes of distributions, adjusting the block size. This is achieved by bounding the quantile function Qm around 1/2,, uniformly over the class of distributions. A general approach to obtain a reduced bound for the right-hand side of (4) is to increase the blocks' size m. For instance, if p has finite variance, have the bound
(m(2/2+E)
(5)
mm21 c)
consequence of Chebyshev's inequality, for any [0. 1/2). Better bounds for 44 can be obtained the distribution enjoys certain symmetry. For instance, if p is a Gaussian distribution, for any E [0, 1/2),
Qm (1/2++)) Vm
(6)
and we can obtain better bounds than 5 by decreasing e towards zero
3.1
Finite variance
The next result establishes the optimality of MoM under adversarial contamination in the class Pa formed by distributions with finite variance.
Theorem 3.2. Let PMMM be the MoM estimator with number of blocks
{
log(2/8)
=
[yann]
(1/2-1/10) 1//)²
for any y (2,2.5) and > 2 -32 such that for any p E P2z and a 0.4
1/7)2n).
Then, there exists a positive constant
C(r) 1//2-1/7) 3/2
(V
log(2/0)
JiraMM Hpl S C(7)ap
+ Vo
n
holds with probability at least 1 1
5

---

Sketch of proof. The full proof is given in Appendix A.2
The key step bound the quantile function Qn appearing in Theorem 3.1 Since p has finite variance, Chebysev's 's inequality implies that, for any E [0,
Op
Qm (1/2+
/m(122-8
The same bound also holds for mm (1/2 -)).
Thus, both quantiles of interest scale as OOap/ /
For the choice of k in the theorem, namely
= 1og(2/8) + am
get
m = 2//nn/(222/)) + an).
Substituting this into the Chebyshev bound gives
V m(112 S (v (2g(2/0)
Pp
+ Va
n2
Finally, applying Theorem which relates the performance of the MoM estimator to bounds on Qm, we conclude that
PMOM - Mpl op (V 1og(2/5)
Va
(9)
with probability at least
8.
The result above shows that MoM is (minimax) optimal in the class P2. Moreover, Theorem 3.2
generalizes existing robustness results for MoM under heavy tails. Specifically, without contami- nation (i.e.. 0) the bound ( recovers the known sub-Gaussianity result for MoM in the i.i.d. scenario [10]. Theorem 3.2 also generalizes existing results for MoM in scenarios with contami- nated samples. Specifically, the results in [15] provide upper bounds for MoM's error with rates that match the optimal order in the i.i.d. scenario. However, such results are limited to scenarios with ad- ditive contamination and only characterize the first optimality regime. In particular, existing bounds apply when the number of samples satisfies S log(2/0)/a, and therefore do not characterize the asymptotic bias (see e.g., 15, Prop. 2)).
Thcorem 3 shows that the contamination tolerance of MoM is comparable to other estimators. In fact, requiring maximum tolerance for is standard for mean estimators (24. 25). For instance, existing results establish a contamination tolerance of a s 0.13 for the trimmed mean, and of 0.36 for Catoni's 's M-estimator (24. 25
The best known leading constants in the error bounds for the i.i.d. scenario are significantly smaller than the one in Theorem 3.2 (e.g., the bound for Lee-Valinat Valiant estimator in the i.i.d. scenario has leading constant of 2 [4]].. As in other works for adversarial contamination [24]) the focus of this
paper on establishing optimal rates rather than minimizing constants.
3.2 Infinite variance
The next result shows that MoM is also optimal the class Pi+r of distributions whose absolute (1 rh moment o, is finite for (0,1).
Theorem 3.3. Let fMMM be the MoM estimator with a number of blocks
{
12g(2/8)
max
[ran]]
(10)
(1/2 - 1/7)2
for any 7 E (2,2.5 and > 2 2exp(-(11)) - 1/)) Then, there exists a constant
C(r) (1/2 1 1/7) till such that for any p E Pi+r and 0.4
((1o8(2) (00g(2/0)
jiMOM Mpl C(
+a
(11)
holds with probability at least 1 1

---

Sketch of proof. The full proof is given in Appendix A.3
The argument parallels Theorem 3.2 The key step is bound the quantile function Qm in Theo-
rem 3.1 By combining Markov's 's inequality with the Bahr-Esseen inequality (29. Thm. 2}, for any E 0, 122) get
r
Up Qm (m(1/2+)) (1/21/2 E)
and the same bound also holds for -Qm - E). Hence, both quantiles of interest scale as (((,//m")) With the choice of k in the theorem, namely:
x log(2/6) + om
we have
m m m=n/(log(//0) + on).
Plugging this into the quantile bound yields
itr (
(10((2/6) -
+atf
m" (1/2 +)
71
Finally, invoking Theorem 3.1 we conclude that
((198(200))
iMMM Hpl S ur +
+ar5
with probability at least - 8.
Thcorem 3.3 presents the first analysis of MoM for distributions with infinite variance in the presence of contamination. Moreover, bound shows that the error of MoM attains the optimal order in the class Pitr shown [25]. Theorem 3.3 also generalizes existing robustness results for MoM under heavy tails. Specifically, without contamination (i.e., 0) the bound 111 recovers the optimality result of MoM for infinite variance in the i.i.d. scenario [8].
In terms of contamination tolerance, Theorem 3.2 shows that MoM presents notable improvement compared to Catoni's M-estimator, the other optimal estimator in the class Pitr- In particular, the tolerance to contamination of Catoni's M-estimator decreases with For example, for values of r 0.5 and = 0.1, Catoni's M-estimator can handle contamination levels up a 0.26 and 0.16, respectively (25]. Theorem 3.3 shows that the tolerance to contamination of MoM does not decrease with
3.3 Matching lower bounds for general distributions
In this section, we have established the optimality of MoM in P2 and Pitr for the same choice of the number of blocks k. The next theorem shows that, for this choice of k, the /a order of the asymptotic bias cannot be improved for any distribution E Pg with a finite third absolute moment
Theorem 3,4. Let PRIOM be the MoM estimator with k given as in ( and (10). There exist positive constants C, amaxo and an adversarial attack such that for any P E Pa and a amax
iiMOM Ppl 2 Copva
(12)
holds with constant probability.
We thank an anonymous reviewer for pointing out that the finiteness of the third moment is not essential for result similar to that in Theorem (.4] In particular, an asymptotic result can be derived using the central limit theorem without requiring finite third moment.

---

Sketch of proof. The full proof is given in Appendix B.1
Let Pi: Mi: ...... Pig denote the empirical means of the k blocks before contamination and B be the set of the [k/2] blocks with lowest sample means. With constant probability, the number of blocks in B that contain least one contaminated sample exceeds an/C1, for some universal constant C > 0 (Lemma B.I. Therefore, with that probability, MoM is shifted to
PMoM = (anC/I)+[an/CL))
the adversary includes samples with arbitrarily large values. In addition, for sufficiently
large n, the empirical quantile P(Tk/2]+[aaw fan/Cil) is arbitrarily close to the actual quantile Qm (1/2 om/Ci) for m |n/k]. Then, the result is obtained since m x 1/a and the Berry- Essen theorem implies Q. (1/2 am//C) 2 /m/vm 2 apva.
The result above shows one limitation MoM under adversarial contamination: choosing the num- ber of blocks & to achieve (minimax) optimal error rates over a broad class of heavy-tailed distribu- tions does not lead improved rates for specific, well-behaved distributions. Specifically, for every distribution with finite variance (e.g., Gaussian), the estimation error has the same order in the worst case. Therefore, the number of blocks must be adjusted differently depending on the class of distributions considered. A similar limitation affects Catoni's 's M-estimator, which requires selecting an appropriate function vó (a parameter that determines the estimator) depending on the distribution
considered (25).. In contrast, other robust estimators such as the trimmed mean [24] do not need to adjust parameters depending on the distribution.
In the following sections, we present eπror bounds for MoM that yield better orders for the asymp- totic bias than va considering specific subclasses & P2. line with the above discussion, this improvement necessitates a different choice for the number of blocks k.
4 Sub-optimality of the MoM estimator for light-tailed distributions
In this section, we show that the asymptotic bias can be improved for light-tailed distributions. In particular, we prove that the asymptotic bias of MoM upper bounded by 2// for sub-exponential distributions. In addition, we provide matching lower bounds showing that MoM is sub-optimal for light-tailed distributions. This result complements known limitations of MoM in the i.i.d. scenario, such as its large asymptotic variance [9]
4.1 Sub-exponential distributions
The following result presents concentration inequality for MoM which holds in the class of sub- exponential distributions denoted as PSE. Distributions E PSE are characterized by the condition that, for all s 2 2, (Ex=plX Upl 1/,1o)//s S caps (30. Prop. 2.7.1].
Theorem 4.1. Let AMOM be the MoM estimator with a number of blocks k = n Ç > and 8 > 2 1/3 //18). There exist positive constants C(E) and (max such that for any p PSE and Omax
[ for any
(1
log(2/0) (10g(2100
1 - Mpl S C(E))p
+ a 2/3
(13)
n
holds with probability at least - 6.
Proof. See Appendix A.4
The result above shows that the asymptotic bias of MoM can attain better orders than Va (as estab- lished in Theorem 3.2) when restricting to the class of sub-exponential distributions. However, the confidence parameter in Theorem must satisfy 5 2 cxp(-O(nn /3)), whereas Theorem B.2 al- lows for the broader range of values > expp (n)). Such limitations are common in estimators that do not depend on 8 (multiple-ō estimators) 31]
The asymptotic bias shown Theorem far from the optimal order the class PSE, which cannot be higher than a log(1/a) because the trimmed mean estimator achieves such an order (see

---

n for any remark in page 10 of (24)). Notably, in the next theorem, we show that for any MoM, the order of a./3 cannot be improved in the class PSE.
Theorem 4.2. There exist positive constants C, amaax a probability distribution p E PSE and an adversarial attack such that for any Qmax and for MoM estimator PMoM with any number of blocks E (1,2,...,7)
PMMM Hpl 2 Copa223
holds with constant probability
Proof. See Appendix B.2
The result above shows that MoM (minimax) sub-optimal in the class PSE. Specifically, Theo- rem 4.2 shows that for some sub-exponential distributions, the error of MoM for any choice of is lower bounded by an expression with order 2//3 that matches the upper bound in Theorem 4. and sub-optimal in PSE.
The suboptimality of MoM can be understood through the role of asymmetry in the error achieved using the median estimate the mean. While MoM's performance improves under light-tailed distributions (Theorem 4.1. MoM does not attain the optimal rate for all such distributions, since some of them are quite asymmetric. median differs substantially from the mean. Since MoM estimates the mean by taking the median (a biased estimator of the mean) of & sample means (each an unbiased estimator), the bias becomes more pronounced in asymmetric distributions.
particular, there exist light-tailed distributions where the
4.2 Sub-Gaussian distributions
The class of sub-Gaussian distributions PsG contains distributions whose tails decay least fast as those of a Gaussian. Distributions E PsG are characterized by the condition that, for all 2 2, (Ex~plX X - /p1")//> < copvs (30, Prop. 2.5.2].
The results in Theorem also provide upper bound for sub-Gaussian distributions since PsG S Psg. As we experimentally show in Appendix C the order 2/3 cannot be improved across all sub-Gaussian distributions. Nevertheless, the following we show that MoM can attain better orders than 2/3 for some classes of uub-Gaussian distributions with certain symmetry. However, these orders do not match the optimal asymptotic bias in Psg. which of the order a /log((/a)). as shown in [24]]
Definition 4.1. We define Pgg for any integer s 2 3 to be the set of absolutely continuous distribu- tions PsG such that for all
{x- 1Pp )}
E Ex<p
Ez-N(o.1) [Z]]
Op
where N(0, 1) is standard Gaussian distribution.
For any distribution in the class PšG the first s central odd moments are zero, indicating that the distribution has certain symmetry around its mean. The next result shows that MoM can attain better orders for the asymptotic bias in the subclasses Psg.
Theorem 4.3. Let MMMM be the MoM estimator with number of blocks k <> 0 and 8 > 2exp (-nn=it /18) There exist positive constants C(E) and a (E) such that for any E P&o and a < (max(()
log(2/6) + a a+1
iMMoM 1 C(E)
(14)
holds with probability at least
Proof. See Appendix A.5

---

Increasing results in an increased symmetry that leads to an asymptotic bias in (4 approaching a. In the following section, we show that MoM can attain an asymptotic bias of order a for some symmetric distributions that include the Gaussians and even distributions with heavy tails.
5 Optimality of the MoM estimator for symmetrie distributions
In this section, we show that the asymptotic bias can be further improved to a for symmetric distri- butions with quantile function that increases at most linearly around 1/2. We denote by Paym the set of symmetric distributions around mean, i.e., distributions p such that - Pp and -(X 1p)) have the same distribution, whenever X p.
Definition 5.1. We define the class of distributions Pe for Ep < 1/3 and c > 5, to be the set of E Paym n P2 such that for all & E [0, cul and m E
P Qm (m(122+)
(15)
vm
where Qm is the quantile function from Definition 3.1 corresponding to the distribution p-
The class Peo contains Gaussian distributions and heavy-tailed distributions like Student's dis- tributions. This is easy to check since both Gaussian and Student's & distributions are symmetrie, satisfy (15 for m 1, and are infinite divisible distributions [32]- In the literature, similar classes to P have been analyzed in the context of quantile regression and mean estimation with outliers. For example, P is similar to the distributions with 1 1/2-quantile of type 2 from 33 Def. 2.1] and the class of symmetric distributions defined in [34].
The technical condition (5] ensures that the quantile function not excessively sharp near the me- dian (it increases at most linearly), that it easier to distinguish the median from nearby quantiles. More precisely, the constant Eg controls the size of the neighborhood in which the quantile function increases at most linearly, whereas the constant controls the slope of the linear approximation.
The following result shows that MoM is optimal in the class Pegm under adversarial contamination.
Theorem 5.1. Let ΩMMM the MoM estimator with = [Bn] blocks for any 3 S and 5 > 2 fexp(-3=3n/A)) Then, there exists positive constant C C'(c, 3) such that for any p E Pion and a < BEo/2
log(2/6) n
iTMOM - -1pl S Cop
+
(16)
holds with probability at least -. 5.
Proof. The result follows directly from Theorem 3.1 and Definition 5.1
The result above establishes the (minimax) optimality of MoM under adversarial contamination in the class sym* for any pair Sp, Theorem 5. generalizes the well-known guarantee for the sample median (case 3 1) for the class of Gaussian distributions (see c.g., [26]. (27. Cor. 1.15J).
6 Conclusion
This paper provides upper and lower bounds on the error of the MoM estimator for multiple classes of distributions under adversarial contamination. Specifically, we prove that MoM is (minimax) op- timal in the class of distributions with finite variance, and in the class of distributions with finite absolute (1 r) moment (infinite variance). In addition, we show that the MoM estimator is particularly well-suited for symmetric distributions. These results reinforce the widely recognized strengths of MoM, such its optimality in the i.i.d. scenario. the other hand, the paper also re- veals that MoM has certain limitations under adversarial contamination. In particular, we show that MoM cannot fully leverage light-tails, and we characterize sub-optimality for sub-exponential distributions. These results complement known limitations of MoM in the i.i.d. scenario, such as its large asymptotic variance. Overall, the theoretical results presented in the paper provide compre- hensive characterization of the capabilities of the MoM estimator under ad adversarial contamination.
10

---

Acknowledgments
The authors would like to thank Prof. Gábor Lugosi for his comments and suggestions dur- ing the development of this work. Funding in direct support of this work has been provided funded by MCIN/AEL/1O. 130//////000133//1111 3039/5011 100011033 and the Eu- BCAM Severo Ochoa accreditation CEX2021-001 142-
by project HDD2022-13706NNB-22 ropean Union S/MICIN/AE//1O. 13039/501 10001 1033 funded by the Ministry of Science and Innovation (Spain), and program BERC-2022-2025 funded by the Basque Government. Xabier de Juan acknowledges predoctoral grant from the Basque Government.
References
[1] A. Nemirovsky and D. B. Yudin. Problem Complexity and Method Efficiency in Optimiza- lion. Wiley, New York, 1983.
[2] G. Lecué and M. Lerasle. Learning from MOM's principles: Le Cam's approach. Stochastic Processes and their Applications, 129(1 1): :385 4410, 2019.
[3] G. Lugosi and S. Mendelson. Risk minimization by median-of-meant tournaments. Journal of the European Mathematical Society, 22(3):925-965, 2019.
[4] G. Lecué, M. Lerasle, and T. Mathieu. Robust classification via MOM minimization. Machine Learning, 109:1635-166 2020.
[5] M. Lerasle, Z. Szabo, T. Mathieu, and G. Lecue. MONK outlier-robust mean embedding estimation by ceddian-of-means In 36th International Conference on Machine Learning, pages 3782-3793. 2019.
[6] Humbert, B. Le Bars, and L. Minvielle. Robust kernel density estimation with median-of- means principle. In 39th International Conference on Machine Learning, pages 1444-9465, 2022.
[7] C. Crunet-Saumard, E. Genetay, and A. Saumard. K-bMOM: robust Lloyd-type clustering algorithm based on bootstrap median-of-means. Computational Slutistics & Data Analysis, 167:107370, 2022.
[8] G. Lugosi and Mendelson. Mean estimation and regression under heavy-tailed distributions- survey. Foundations of Computational Mathematics, 19(5): (155:1145-1199 2019.
[9] Minsker. Distributed statistical estimation and rates of convergence in normal approximation.
Electronic Journal of Statistics, 13(2):5213-522 2019.
[10] D. Hsu and S. Sabato. Loss minimization and parameter estimation with heavy tails. Journal of Machine Learning Research, 17(18):1-40, 2016.
[11] S. Minsker. Efficient median of means estimator. 36th Conference on Learning Theory, 2023.
[12] R. Oliveira and P. Orenstein. The sub-Gaussian property of trimmed means estimator. Techni- cal report, IMPA, 2019.
[13] O. Catoni. Challenging the empirical mean and empirical variance: A deviation study, Annales de I'....P. Probabilités el statistiques, 48(4): 148-1 185, 2012.
[14] J. C. Lee and P. Valiant. Optimal sub-Gaussian mean estimation in R. In 62nd Annual Sympo- sium Foundations of Computer Science, pages 672-683, 2022.
[15] Laforgue. G. Staerman, and Clémençon. Generalization bounds the presence of outliers: a median-of-mean study. In 38th International Conference on Machine Learning, pages 5937- 5947, 2021.
[16] D. Rodriguez and M. Valdora. The breakdown point of the median of means tournament. Statistics & Probability Letters, 153:108-112, 2019.

---

[17] A. S. Dalalyan and A. Minasyan. All-in-one robust estimator of the Gaussian mean. The Annals of Statisties, 50()) 1900:1193-1100 1219, 2022.
[18] H. Xiao, B. Biggio, B. Nelson, H. Xiao, H. Eckert, and F, Roli. Support vector machines under adversarial label contamination. Neurocomputing, 160:53-62 62, 2015.
[19] P.W. Koh, J. Steinhardt, and P. Liang. Stronger data poisoning attacks break data sanitization defenses. Machine Learning, 111:1-47, 2022.
[20] O. Suciu, R. Marginean, Y. Kaya, H. Daume III, and T. Dumitras. When does machine learning fail? Generalized transferability for evasion and poisoning attacks. In 27th USENIX Security Symposium, pages 1299-1316, 2018.
[21] X. Chen, C. Liu, B. Li, K. Lu, and D. Song. Targeted backdoor attacks deep learning systems using data poisoning, 2017. arXiv:1712.05526.
[22] T. Gu, B. Dolan-Gavitt, and S. Garg. Badnets: Identifying vulnerabilities in the machine learning model supply chain, 2019. arXiv:1708..m 776336.33.
[23] I. Diakonikolas, G. Kamath, D. Kane, J. Li, A. Moitra, and A. Stewart. Robust estimators high-dimensions without the computational intractability. SIAM Journal on Computing, 48(2):742-86,, 2019.
[24] G. Lugosi and Mendelson. Robust multivariate mean estimation: The optimality of trimmed mean. The Annals of Statistics, 49(1):393-44 2021.
[25] S. Bhatt, G. Fang, P. Li, and G. Samorodnitsky. Minimax M-estimation under adversarial contamination. In 39th International Conference on Machine Learning, pages 1906-1924, 2022.
[26] A. H. Bateni. Contributions to robust estimation: minimax optimality vs. computational tractability, PhD thesis, Institut Polytechnique de Paris, 2022.
[27] I. Diakonikolas and D. M. Kane. Algorithmic High- -igeenimnai Robust Statistics. Cambridge University Press, Cambridge, 2023.
[28] M. Chen, C. Gao, and Z. Ren. Robust covariance and scatter matrix estimation under Huber's contamination model. The Annals of Statistics, 46(5):1932 1960, 2018.
[29] B. von Bahr and C. G. Esseen. Inequalities for the rth absolute moment of a sum of random variables, 1 S r S 2. The Annals of Mathematical Statistics, 36(1):299-303, 1965.
[30] R. Vershynin. High-Dimensional Probability: An Introduction with Applications Data Sci- ence. Cambridge University Press, Cambridge, 2018.
[31] L. Devroye, M. Lerasle, G. Lugosi, and R. Oliveira. Sub-Gaussian mean estimators. The Annals of Statisties, (4(6))2695-2733 2016.
[32] S. Ken-lti. Lévy Processes and Infinitely Divisible Distributions. Cambridge University Press. Cambridge, 1999.
[33] I. Steinwart and A. Christmann. Estimating conditional quantiles with the help of the pinball loss. Bernoulli, 17(1):211 1-225, 2011.
[34] A. Prasad, S. Balakrishnan, and P. Ravikumar. A robust univariate mean estimator is all you need. In 23rd International Conference on Artificial Intelligence and Statistics, pages 4034 4044, 2020.
[35] V. Vovk. Conditional validity of inductive conformal predictors. In 4th Asian Conference on Machine Learning, pages 475-490, 2012.
[36] U. V. Prokhorov and V. Statulevicius. Limit Theorems of Probability Theory. Springer, Berlin, 2000.
12

---

[37] S. G. G. Johnston. A fast Berry-Esseen theorem under minimal density assumptions, 2023. arXiv:2305.18138
[38] A. Panconesi and A. Srinivasan. Randomized distributed edge coloring via an extension the Chernoff-Hoeffdiin bounds. SIAM Journal on Computing, 26(2):350-368, 1997.
[39] S. Greenberg and M. Mohri. Tight lower bound the probability of binomial exceeding its expectation. Statistics & Probability Letters, 86:91-98, 2014.
[40] Shao. Mathematical Statistics. Springer, New York, 2003.
[41] C. Berg and H. L. Pedersen. The Chen-Rubin conjecture in a continuous setting, Methods and Applications of Analysis, 13(1):63-88 88, 2006.
13

---

A Proofs for Upper Bounds
The following result is an adaptation of Proposition 2a from (355 that is used to prove Theorem 3.1 For clarity, we assume that p an absolutely continuous distribution. This assumption allows the cumulative distribution function to have inverse, which corresponds to the quantile function. This assumption is not restrictive and the proofs can be adapted to include any distribution with finite variance (see [35, Prop. 2a] for similar arguments in the context of conformal prediction). An alternative solution for the statistician to add a small amount independent Gaussian noise to the samples, ensuring that the distribution has a density without compromising statistical performance.
Lemma A.I. Let p be a distribution with quantile function Q, and let X1 X2,..., be n i.i.d. samples drawn from For r E 21,2..... nJ and & = r/n, the following holds:
If + Vlo((1/0)/2) e (0, 1), then
log (1/6)
(() SQ 8+
(17)
2n
with probability least 6.
If 8 Vlog(1/6//2) E (0, 1), then
(() 2 1 ( (-
()))
(18)
2n
with probability at least - 8.
Proof. Let F be the CDF of and let t E (0, be real number be chosen later. Since the X1, Ni,.,,..,, are independent
a
P[X > Q(t)=
Sr P(Bin(n, F(Q(t) S 1]
where, for any m E N, g E [0. 1]. Bin(m, q) denotes random variable drawn from a binomial distribution m trials with a probability of success q. Taking = Vlog(1/8)((2n), we apply
Hoeffding's ss inequality (as e 1. < 0) and obtain
(nnin(n, t) < 1| $ P[Bin(n, t) S En]
< P[Bin(n, -)nn-t//nnnn t E -e2t-))) =
that leads to (17 since we have shown P(X > (()) < 6.
Now prove 18 in similar way 17
Analogously the previous case, have
P[X Q(1) IP Σ 1xx < Q()) 2 ([Qi((n,FQQU)) 2 r]
so that taking = (log((/)))/2n)) and applying Hoeffding's 's inequality (since 1 0) we
get
(BBin(n, 1) F[Bin(n, 1) 2 en]
P(Bin(n, f)/n - t E -e 2(e--)) =
that leads to 18
14

---

A.1 Proof of Theorem 3.1
Proof of Theorem 3.1 Without loss of generality, we assume Mp = Let I1, 12, ..... ., Ix be k ran- dom disjoint blocks of the indices {1, 21.2....m) n)
of equal size m = [n/k]. Let
Σ Xj, i 1=1,2,.... JEL,
(19)
be the sample means corresponding different blocks before the adversary contaminates the sample and let
Σ X i 1,
(20)
JEL
be the sample means corresponding different blocks after the adversary contaminates the sample.
The attack of the adversary can modify at most the values of on blocks, so MMMM = (((2/2)) is between P1(14/2 and [((k/2)++om)> which are well defined since k 2on.
Since (log am 1/2 by hypothesis, applying Lemma A.1
l2g(2/6)
P(ak/2]+an) S Qm
+
+ am
=:
2
2k
holds with probability at least - 8/2, and also
1
log(2/8)
Qm
am S ((1k/21+mm)
2
2k
holds with probability at least - 6/2. Moreover, by the union bound
min(4, uu S l AMMMM S u S max(u, (u, -13
holds with probability at least 1 - 6. Since min(/, -u} = max mnax(u,-1) -1}
{
@m
log(2/8)
1
log(2/8)
MMMM S max
Qm
+ am Qm
am
2k
2
2k
holds with probability at least 5.
A.2
Proof of Theorem
3.2
Proof of Theorem
3.2
Without loss of generality, we assume Up
-0. By Theorem 3.1
(2g(2/8)
1
log 1og(2/6)
PMoM|
max Qm
am
Qm
am
2k
2
2k
holds with probability 5 whenever
log
am 1/2.
(21)
2k
Some basic computations verify that the choice of & in the hypothesis satisfies 2am < k S n and that (11h holds for the range of specified the hypothesis.
For every & E [0, 1/2), Q = Qm. + E), by Markov's inequality we have
of
1/2 c P(B,, 2 Q = P[B2 2 Q²1 S
(22)
mQ²
and in particular,
(1/2+
Tn
1
Vm 1/2
15

---

Moreover, we also have
Op
(1/2 - -E) Vm v1/2- -
where Q-m is the quantile function of -Bm- Let 11/2-1/7)3 be positive constant. If ò (2c on .. cTam), ) the number blocks given by [log(2/6)/c). particular, 1/ m S v 2k/n S 2 (21l((2/))/(cn) since [a]] 2 x/2 and [x] s 2x for any 2 1. Therefore, if E = v (2g)(/6)/
since Qm =) = 2).
+ am.
0p Vm 1122-
S <dop (2/(2/0)
where
1/c
d s 2
1/2 (Vc/2+1/1)
If 8 2 2om the number of blocks equals h: = [yan] and in particular, 1/Vm 5 Hence, E = (log(2/0)((2k) + am,
Op 1 Vm 1/2 - S Scoova
where
& S
7
1/2 (Ve/2 1/7)
Therefore, we have shown that for all > e on and 7 S 2.5 = 1/0.4 S 1/a, k max[[yam], (2g(2))))
1og(2/6)
Immoaal S Cop
+ Va
holds with probability at least 6, where
C= C 2 2 2= v2
1
V7
(23)
(1/2 - 1/738/2
(1/2 1//)2/2
A.3 Proof of Theorem 3.3
Proof. Without loss of generality, we assume /4p = 0. By Theorem 3.1
l2g(2/8)
1
log(2/0)
AMMM S max
Qm
+ am -Qm
am
2k:
2
2k
holds with probability 8, whenever
log (2/5)
am < 1/2.
(24)
Some basic computations verify that the choice of k in the hypothesis satisfies 2om < k and that (44 holds for the range of specified in the hypothesis.
For all E [0, 1/2), by Markov's inequality (following similar reasoning in 22
[8| Bm 1++ +
(m
1/2
16

---

Moreover, by the BahreEsseen inequality Bl |+ I I 2m E,. Therefore, we have
29 Thm. 2], moments of i..d. averages satisfy
U7
Qm { s
mi+r (1/2 - E)
Furthermore, we get
Uf 1
Qm/2 - 2 m
(1/2-E) E)
since
(1/2-mm11/+22 2). where Q-m denotes the quantile function of -Bm-
The rest of the proof proceeds analogously to the one for Theorem 3.2 in Appendix A.2 Let c
(1/2 1/7)² be a positive constant. 5 (2e-en, 2e 20ym)) the number of blocks is given by = [20g(2/6)/c). and if (1og(2/0)((2k)) aam,
S Go 1og((/8) Ifr
1 m (1/2 -) =)
T
(25)
where of depends only on and r.
If 8 2 7on the number of blocks equals k [yam], , and if (log(2/8)((2k) am,
2 m (1/2 1 S cf atr
(26)
where ef depends only on y and r. Combining both (25 and 26 we get the desired result.
A.4 Proof of Theorem
Minsker introduced 9 a technique to study the error of MoM in terms the rates of convergence normal approximations. We extend this approach to the scenario of adversarial contamination. In particular, the definition bellow describes the difference between averages of i.i.d. inliers and the standard Gaussian distribution.
Definition A.1. For every E N we define g(m) 2 0 as
Opt /m
g(m) = sup tER
Fm
((()
where Fm is the cumulative density function from Definition function of a standard Gaussian distribution N(0,
3.1
and & is the cumulative density
the following lemma, we combine Theorem with the ideas in Section from to obtaín bounds for the error of MoM under adversarial contamination in terms of g(m).
Lemma A.2. Let PMaMs be the MoM estimator with blocks of size m = |[nkk] evaluated at n a-contaminated samples. If the number of blocks satisfies 2om k S n, there exists universal constant C such that for all > 2exp(-22 22k(1/3 am 2
[1og(2/0) av + g(m)
jMMM Ppl S Cop
7
vm
holds with probability at least - 5.
Proof. We first prove that for e 1/ - g(mi)
(m -) Op Φ (1/2 = g(m)),
(27)
Vm
(1/2++)
Up Φ (1/2 = +mmm)).
(28)
vm
17

---

We only prove 28 since 27 is obtained in the symmetric way. Note that ( - Fm (apt/ g(m) for all E R. In particular, if -1- + g(m))
Opt
8 (b( - g(m) - Pm
mm
Therefore, we get
Qm(1/2+8)
Op Vm
pp Φ (1/2 + + Vm
Since vlog(2/0)/2k + am + g(m) < 1/3 by hypothesis, by Theorem
log log(2/6)
AMoM - Mpl S
Tp Φ --1
2 +
2k om + g(m)
v
holds with probability at least 6, after applying both (27 and 28) Moreover, is well known
that Φ 01//2 22/22+ + 2) I 32 for all < 1/3 19. Lemma 4]. Therefore, there exists universal constant
C > 0 such that
10g(2/0) av m
g(m) Vm
iMMoM Ppl S Cop
holds with probability at least 6, as desired.
Proof of Theorem Let O'max min (6(5-) + 2(avE)) be the tolerance to contamination, where C3 is a constant specified later. easy to check that 2an < S n is satisfied for all & > 0, since < 0maxx
By the Berry-Esseen theorem [36, Sec. 1.2], the value of g(m) in Definition A.I satisfies g(m) s Cipp/(a /m) for some constant Ō₁ > and where Pp Ex X Upl 3. Moreover, since is sub-exponential Pp Č202 for some universal constant C₂ > 0. Therefore, there is a constant O3 > 0 such that g(m) I C3/vm Hence, > 2 e 221(22k(1/ am 03/ (m/m by Lemma
1og(2/0) n
jMoM Mpl Ciap
av +aym m
holds with probability at least - 6, for positive constant C₁.
By hypothesis n/3 and since m = |n/k]]
jMMM Mpl S C20p (V 1og(2/0) + 2/3
holds with probability at least 1 - 8, for constant C2 = =C2(E) whenever 2exp(-2k(1))
am Cs/ ). Without loss generality, we assume a 2 1/n. Therefore the result also holds for all > cxp( (exxpp(Enn// //3 /18) since a E [1/n, (6(g- +(3 -3) implies 2 cxp(- 1/3 //8) >
2 texp(-2k(1) 1 am - C2/ )m))).
A.5 Proof of Theorem
Proof of Theorem Since the proof is almost identical to that of Theorem 4.1
Appendix A.4
we omit the computations and provide only a sketch of the proof. Instead of using Berry-Essen theorem, now use Theorem 1.1. from 37 to upper bound g(m). Therefore, since SG by
37. Thm 1.1.]
Ex-p X 1p g(m) S Ō1
1
0p m
18

---

for some constant Õ1 > 0. In particular, as is uub-Gaussian, there exists constant C2 > 0 such that Ex~pIX 1p 1 v C2 Thus, there is constant C3 0 such that g(m) - Cs/m + Therefore, for 5 > 2 2exp(- 1aap(-2k(]) / am - Ca/mm=1mm) by Lemma A.2
(2g()/6)
iMMO - Mol Clop
+ aaymm m mn/2
n
holds with probability at least - 6, for constant C1 O.
By hypothesis, &s [ga n]], and since Ln/k],
(Vl0822/3) 1ogg(/0))
iMMOM Hpl C20p
holds with probability at least 1-ô, for a constant C2 > 0. Proceeding as in the proof of Theorem in Appendix A.44] get the desired lower bound for 8.
B Proofs for Lower Bounds
The following two auxiliary lemmas are used to prove the lower bounds in theorems 3.4 and 4.2
Lemma B.1. Let C₁ > 3 and Za be the number of blocks with at least one contaminated sample among the [k/2] blocks with lowest sample means P1 ..y....: 1o before contamination. Then there exists un adversarial allack and C2 >> O such that for all a 2 1/n
.......
Pizo > an/C.] > Cz.
(29)
Proof. Note that Z. = |[//2] Y, where the random variable Y, E (0, 1} is defined Y; 1 the i-th block, ranked by the smallest sample means before contamination, contains at least one contaminated sample, and Y,
[k/2]
otherwise.
We consider contamination in which the adversary randomly chooses an samples, and makes them arbitrarily large. Hence, all the Y; are identically distributed.
Note that for all * j. Y; and Y, are negatively correlated, i.e., Cov Yj) S 0. To see this, since all Y1, 2,.... Y2 have the same mean, we get Cov(Y; Y2) E[Y,Y, (EEY) Let C, denote the event such that Y; = ]. J. Since C, - F[C.] and the Y; are identically distributed
E[ IP, n Cj] = ICC s [PC,)I[(C.] = (EY))
whence we get Cov (Y,, Y,) - 0. Therefore, we can apply to Za the Chernoff bound for negatively correlated random variables [38] That for all 0 E (0, 1)
P (1-a) 2 exp 8
(30)
We can lower bound the r.h.s. of (30 if we find lower bound for EZ.. claim EZ,, > 1-e 1-1-112 1/2 and prove it in the following lines. Let (a) be the probability that all the samples in block are not contaminated. Then it easy to see that for all i E {1, 2, .... ......k, k). EY, = f(xx) where
f(a)
K
m
Moreover, ((a) S am since
m-
n1 an j
n an
m
f(a)
<
-11 (1 Se -a
(31)
11
n
0=
19

---

Finally,
[n/m]
EZa 2
(1 e
am
2 2am
(1 e
amm)
> C e1/2
(32)
where in the first inequality we have applied (31 in the second one n 2 1/a and in the last one m 1/(2).. Therefore, applying EZaa
1/2 in (30) we get
B
8
1/2)
exp
>
exp
C2.
2
2
We can upper bound the l.h.s. of (30) as follows,
1 an/C C// 2 P (1 0).),
where - ( -113)) - (1- - 0). To see this, note that the following chain of inequalities hold
C am 0) -
1
an (1 - 20m
(1 e cmm)
S (1 2)
where in the second inequality we have used
1/(2x) and in the last one
EZ, 2 n11 - e --mm (2m). as in 32
Lemma B.2. Les C1 be constant, let MMoM be the MoM estimator with blocks of size m, and let Fm be the c.d.f. of Bm in Definition 3.7 There exists an adversarial attack such that for any distribution p with finite mean, and any such that F.. < 1/2 + cmm/Ci.
iiMOM - Ppl 2 t
(33)
holds with constant probability.
Proof. Without loss of generality we assume Up = 0. Let Ci > 3 and C2 be the constant from Lemma B.I By the law of total probability
Pl[iMoM| > t] 2 PllPMoM| > 1 > an/Ci]Plza > am/Ci).
We consider contamination in which the adversary randomly chooses an samples, and makes them arbitrarily large, as considered in Lemma [.]] Thus, by that lemma we have a lower bound for the second term PiZa. an/Ci] >> C22 Thus, it remains to lower bound the first term PlipMoal > t Za. an/Cin First note that
Pl|AMoM| Z > an/Ci] 2 (1P((11/2
> t]
(34)
since there are at least Jan/Ci CC] contaminated blocks not above the median before the attack.
We can further lower bound 334 with binomial tail
F1[A((1/21+(mm//11 f] 2 PT (1k/222) > t]
an
IP
Hmm
st
+
2
Ci
[
am
IP
Bin(k, (t)) <
+
2
G
am
IP Bin(k, Fm. < k
(35)
C
Since the binomial tails are monotonically decreasing in the success parameter equation (35) can be further lower bounded
35
Lemma 1].
P Bin(k, Fm (f)) <
am
)
2PP
Bin
k. 2 + am
< k
1 am
+
]
C2
C1
2
C₁
since F., (t) < 1/2+ am/C, by hypothesis.
Write y 1/2 + am/Ci C for simplicity. is easy to check that g < 1 - 1 kk, since Ci can be taken
as large as needed. Therefore, by Corollary from (39) we have IP Bin (k, 9) S kg) 2 1/4, which
translates to the desired lower bound P[[AMoM| > t Za an/Ci] 2 1/4.
D
20

---

B.1 Proof of Theorem 3.4
Proof of Theorem 3.4 Let Fm be the c.d.f. of Bm in Definition 3.1
Since p P3. by the Berry-
Essen theorem 36, Sec. 1.2], there exists C >> 0 such that
C Vm
Opt
sup ER
Fm
((1)
S
and in particular, for any E IR.
ppt m
C vm
F
I ((1)
(36)
Let C1 3, O'max (32C) //3 be the contamination tolerance, and C = 1/(8C1 0. 1/2 + am/Cr for all S Qmax so that by Lemma B.2
In the following we prove Fm (Cop such bound is sufficient to prove the statement of Theorem 3.4
Note that there exists range for 5 such that k [yam], so that 4/(7a) S m S 1/(7a). For all Omuax
CpC mm
Fm (CopVa) & Fm
Fm
(m S 11((7))
(Apply (36)
m
1
C
2 +
(2 2 0 D(2) S 1/2 + z)
vi
mm
1 +
C
< 2
+ 1E /
(m 2 4/(7a) and S Ommxx).
Vi
Finally, since C = 1/(8011((11) (7), Omax (320, 03332) and m 2 4/(7a),
2 + + //
2
1
4yC1
1
S +
2
am
Ci
so that Fm (Copyo) S 1/2
om/ C1, as desired.
B.2 Proof of Theorem 4.2
Proof of Theorem The proof is divided in two parts depending on whether m > 1/a2/3 or m S 1//2/3
If m > 1/a2/3, we show that there exists an adversarial attack and C > such that for any distribution p E PsE
MTMOM - -Apl 2 Copay/
(37)
holds with constant probability. By Lemma B.2 establishing the lower bound in (37 reduces to
proving Fm (Co,ay// I 1/2 + am/C1, where C1 > 3. Note that since m > 1/02/3, bound in 37 can be further lower bounded to an order of 2/3.
2/3 the lower
Since p E PSE, as consequence of the Berry-Essen theorem 36 Sec. 1.2], there exists Č such that for any e R,
opt
Fm
<
((t) +
(38)
mm
Let r E 12/3,1) be such that m 1/a" and let O'max (2C(C) 3//2-1 be the contamination tolerance, what follows, we will prove F. P S 112 + am/Cr for all a S Ommxx with C' = 1/(2Cr).
21

---

We have
Fm (Copavm) Fm J.Com
Vm
Č
+ (Cam) +
(Apply 38
Vm
1
Cam C
(2
( 1/2 2).
2
vm
Finally, since Omax C= = 1/(2C1) and > 2/3, it is straightforward to check
1 + Cam +
Ö
+ Ca 1- Ca' + Ca S 2 C1 2 C1
1 +
al-r 1 am
+
2
Vm
so that Fm (C.CCopaa 1/2 am/C1, desired.
If mm < 1/a2/3 we show that if p is negative exponential distribution then there exists an adversarial attack and > 0 such that
MMMMM - Upl 2 Cop m
(39)
holds with constant probability. By Lemma B establishing the lower bound in (39) reduces to proving Fm (Cop/m) & 1/2 - cm/Co /i, where C1 > 3. Note that since m S 1//2/3 the lower bound in (39 can be further lower bounded to an order of 2//3,
We consider distribution p corresponding to negative exponential with parameter 1, i.e. X if straightforward show that there exists C such that Cop/m S -Mp Jm The average of m i.i.d. exponential distributions follows Gamma distribution [(m, 1/m) 44. p. 82], and the median of such Gamma is upper bounded by sm [41. Prop. 3.6). Let F denote the cumulative density function of a ['m, 1/m). Since - (Bm + μp) follows I'mm 1/m).
X Exp(1).
1 s F 2
(Bm + 1p) S smm
=
Upp - am & Bm = - Fm (114 14p - e --amm sm
Therefore,
Fm 11p Fm FCoppmmm < 1/2 + am/ /1, as desired.
sm
1/2, and since Cop/m 5 U4p 3m,
get
C Numerical Experiments
In this appendix, illustrate the theoretical results in previous sections with numerical simulations. In particular, the experiments show that MoM performs particularly well for symmetric distributions but does not fully leverage light-tails in accordance with the theoretical results.
In all the results in this section, for fixed estimator ğ and distribution p, we repeated the following procedure Rrep times:
1. Draw n i..dd samples from p.
2. Contaminate the i.idd. sample, where a is the fraction of contaminated samples.
3. Compute the estimation error 1/ /ppl-
Finally, we plot the 5 quantile of the Rrep computed errors J - /4pl as function a. The empirical data is shown using dashed lines, while solid lines represent the graphs of the asymptotic bias when an upper bound is known. All plots are shown in log-log scale clearly display the order of the asymptotic bias.
22

---

In table 2 section. In addition, we relate each figure to the corresponding theorem it illustrates.
we summarize the parameter of the various experimental results presented in the present
The trimmed mean and Catoni's M-estimator have been implemented following the definitions and results in 24. 25]. For the MoM estimator, in figs. T(a) and 1(b) we have used number of blocks
k [3am| (corresponding to y = 3 in Theorems 3.2 and 3.3), whereas in fig. [(c] we set k [n/5] (corresponding to 3 1/5 in Theorem 5.
all the experimental results, we consider the following adversarial attack: given an uncontami- nated sample XG ...... X; the adversary removes the largest values and replaces them with an new samples, all set to min; X; Since the empirical error follows the same order as the upper bounds established in theoretical results, other attack can cause greater damage (in terms of order). However, it is true that some attacks may lead to larger absolute errors, although this would not change the error order.
The experimental results in the paper can be carried out in regular desktop machine in few hours.
04
012
100
Oaytmnn MAM
10
MAM
T
Mestizane
Contomination fraction
Contaminaaiinn frnction
Contemination fraction
(a) Finite variance case, Pa
(b) Infinite variance case, Pitr (c) Symmetric distribution, sym
Figure 1: Empirical errors align with the theoretical bounds presented over multiple classes of dis- tributions.
In fig. we show that the empirical error of MoM aligns with the orders of the results from sections to 5 We also provide the empirical errors of the trimmed mean and Catoni's M-estimator. The experiments in fig. can be seen an illustration of the first, second and fifth rows of Table
0.03
Eatimation crne
067
2/5 012
3/3-00
0.01
= 2/5 0.16
2/3
Contamination Erection
Figure 2: For any A: [4a'n]], the error is at least ((22/3) for sub-Gaussian distribution p Psa.
23

---

Table 2: Parameter values of the numerical experiments.
Figure Theorem Class
Distribution
5 Dreep
T(a)
3.2
P2 Pareto(0.45; 1; 10 0.05 100
I(b)
Pi+r Parcto(0.77) 1;
10 0.05 100
[(c)
5.1
Say
to
102 0.05 100
2
4.2
Psg Half-normal
10 0.05 100
Finite Variance Distributions. Figure ((a) illustrate Theorem 3.2 by considering Pareto distribution with finite variance. The figure shows that the empirical error of MoM aligns with the order of the upper bound from Theorem 3.2
using Pareto distribu- tion with infinite variance. Again, the figure shows that the empirical error of MoM aligns with the order the upper bound from Theorem 3.3
Infinite Variance Distributions. Figure [(b) we exemplify Theorem 3.3
Symmetric Distributions. In Figure [(c) we depict Theorem 5.1 using Student's / distribution. The figure shows that MoM continues to align with the corresponding theoretical upper bound in Theorem 5.1 Interestingly, the trimmed mean does not seem to exploit symmetry (in order) as effectively as MoM does. Although its error has not been characterized, the empirical results suggest that the trimmed mean estimator may be sub-optimal in these cases.
Sub-Gaussian Distributions. In Figure 2 we show that the order 22/3 cannot be improved for half-normal distributions for any choice for the number of blocks k. Specifically, we plot the error of MoM with different choices for the size of the blocks h: = [4a'nn] The dashed line with the steepest
slope corresponds to = 2/3 and the asymptotic bias a 2/3 in accordance with Theorem 4. above.
24

---

NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
We mention results that are presented later in the paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals motivation as long it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: In the discussion following each theorem we have explained the limitations of each result.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are discussed in the paper.
The authors are encouraged to create separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The au- thors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, c.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the ap- proach. For example, facial recognition algorithm may perform poorly when image resolution is low images taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to ad- dress problems of privacy and fairnsss.
While the authors might fear that complete honesty about limitations might used by reviewers grounds for rejection, worse outcome might be that reviewers discover limitations that aren't i acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
25

---

Justification: Complete proofs for each theoretical result are provided in Appendix A and B Assumptions are explicitly stated in the statement of each theorem in the main paper.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theo- rems.
The proofs can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be comple- mented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclu- sions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: Yes, see in Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken make their results reproducible verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of model checkpoint, other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all sub- missions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g.. a large language model), then there should either be way to access this model for reproducing the results or way to re- produce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case au- thors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
26

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [No]
Justification: The numerical experiments are simple and can be easily coded. Moreover, numerical experiments are not part of the contribution of this paper.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.. cc/
public/guides ooniadd//ooooeuuubsisiiooooo Policy) for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https://nips httts::/tiips.cc/pbbiii/////// wwt.ccccpppccccceee
for more details. The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
http://ppididdss/////ppp httpdde//ooeeuuuiisseeeeeeeeeeee SondeSubmissiioPool11
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Yes, see in Appendix C
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined other appropri- ate information about the statistical significance of the experiments?
Answer: [Yes]
Justification:
We plot the quantile the computed errors.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
27

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report I-sigma error bars, but one should state it. The authors should prefer- ably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative rates).
show in tables or
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory. time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Yes, see Appendix C
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't it make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer:
[Yes]
Justification:
No relevant issues in our work.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- cration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: The paper presents foundational research that is not tied particular applica- tions.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
28

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g,, deployment of technologies that could make decisions that unfairly impact spe- cific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitiga- tion strategies (e.g.. gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper presents foundational research that is not tied particular applica- tions/datasets.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards allow for controlled use of the model, for example by re- quiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
29

---

If assets are released, the license, copyright information, and terms of use in the pack- age should be provided. For popular datasets, hwtpssspppppsososoooooooo com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the li- cense of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documenta- tion provided alongside the assets?
Answer: [NA]
Justification:
[NA]
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the pa- per include the full text of instructions given to participants and screenshots, if applicable, well as details about compensation (if any)?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but the main contri- bution of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, cura- tion, or other labor should be paid at least the minimum wage the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper deseribe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equiva- lent) may be required for any human subjects research. you obtained IRB approval, you should clearly state this in the paper.
30

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the method development in this rescarch does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy /ttp/errri..cccoooteeeere/////// for what should or should be described.
31


Reviews:
[{"review_id": "ibqn6ceoQL", "reviewer": "Reviewer_fw73", "summary": "This paper studies the asymptotic bias of the Median-of-Means (MoM) estimator for one-dimensional distributions under adversarial contamination, where a small fraction of the input samples can be arbitrarily corrupted. The authors present tight upper and lower bounds for the MoM estimator for several families of distributions.", "questions": "The authors are encouraged but not required to answer the questions mentioned in “Strengths & Weaknesses” above.", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n+ The paper studies the problem of robust estimation under strong contamination models, which is of high relevance to the NeurIPS community.\n+ The paper establishes several **tight** upper and lower bounds for the MoM estimator under adversarial contamination for different distribution families.\n+ The paper is well written, and the presentation is clear.\n\nWeaknesses\n- The paper could be strengthened by highlighting its main technical contributions. For example, what are the paper's key ideas that are missing from prior work? Are there any known previous bounds for MoM estimators for the first four rows of Table 1?\n- When defining the adversarial contamination model, one could further emphasize that the adversary can inspect the estimator/algorithm as well as the true mean. Related to this, on Line 114, the paper states: \"there exists a distribution and an attack such that for any estimator...\". The reviewer is a bit confused about the order of the quantifiers here -- why not \"for any estimator, there exists a distribution and an attack...\"?\n- It could be helpful to clarify early in the paper that the authors focus on the one-dimensional case. The title can seem a bit of an overstatement as MoM is not optimal for all distributions. Perhaps \"On the Optimality of...\" or \"When Is MoM Optimal under Adversarial Contamination?\"\n- The authors could consider citing [1].\n[1] S. Minsker. Efficient Median of Means Estimator. COLT 2023.\n\nTypos\n- Line 121: should there be a comma after \"as the number of samples increases (...)\"?\n- Lines 187 and 330: \"there exist a positive constant\"\n- Line 205: \"the bounds ... has\".\n- Line 318: \"Gaussians distributions\"\n- Line 320: \"infinite divisible\"\n- Line 342: \"is specially well-suited\"\n- Line 438: \"Propostion\"", "was_revised": true, "final_justification": "Most (if not all) of my comments are constructive suggestions. The authors responded that they would revise the paper accordingly. A few short and clear points that justify my rating were provided under \"Strengths and Weaknesses.\"", "rebuttal": "We would like to thank the Reviewer for the constructive feedback provided and we are delighted that the Reviewer finds value in our work. The following provides detailed answers and clarifications for the Reviewer’s questions. We are confident that the comments and questions raised are fully addressed below, and we would be happy to answer any further questions the Reviewer may have during the authors/reviewers discussion period.\n\n**Main technical contribution**: In the final version of the paper we will be more clear explaining the main technical contribution of the paper. In particular, there are no known bounds for the first four rows of Table 1 prior to our work, as the asymptotic bias had not been characterized for these distribution classes. \nThe error of estimators can be divided into two regimes: (1) for a reduced enough number of samples, the optimal error matches that in the i.i.d. scenario; (2) as the number of samples increases, the optimal error plateaus at a level determined by $\\alpha$. The error in the second regime is known as the asymptotic bias and characterizes the optimality of estimators. While previous work on MoM [14] provides error bounds, there are four key aspects that are missing in their work that we solve in the paper:\n\n1)  do not characterize the asymptotic bias.\n\n2) results are restricted to the class of distributions with finite variance, and to the additive contamination model.\n\n3) only provide upper bounds and not lower bounds.  \n\n4) guarantees hold only for reduced enough number of samples.  \n\nIn contrast, the results in our paper characterize the asymptotic bias of MoM for different classes of distributions. Moreover, we also provide lower bounds for the error.   \n\n\n**Title**: We will revise the title to \"On the Optimality of the Median-of-Means Estimator Under Adversarial Contamination\" since it improves the paper as it accurately reflecets the paper’s contribution. \n\n**Reference and clarifications**: We appreciate the reference and we will include it in the final version.  We will also incorporate new comments that will improve clarification 1) on the order of the quantifiers on line 114 and 2) on the fact that our work focuses on the one-dimensional case. We are also thankful for the identified typos which will be fixed in the final version."}, {"review_id": "16IvcZpp57", "reviewer": "Reviewer_SDfx", "summary": "This paper studies the theoretical performance of the one-dimensional median of means estimator under adversarial contamination.\n\nOver the class of distributions of finite $1+r$ absolute moment, for $r \\in (0, 1]$, the paper proves new upper bounds on the $1-\\delta$ quantile of the error of the median of means estimator (Theorem 3.2 and 3.3). These upper bounds, when combined with an exisiting minimax lower bound on this quantile, show that the median of means estimator is minimax optimal (up to a constant) over these classes of distributions. Previously, only the trimmed mean estimator was known to be minimax optimal in this sense. \n\nThe paper then considers light-tailed classes of distributions. Theorem 4.1 and 4.2 show that the performance of any median of means estimator, regardless of the choice of the number of blocks, deteriorates over the class of sub-exponential distributions and is no longer minimax optimal, with its error growing as $\\alpha^{2/3}$ where $\\alpha$ is the contamination level.\n\nFinally, over certain special classes of symmetric distributions, the paper shows that the median of means estimator with a particular choice of number of blocks is minimax optimal.", "questions": "+ The theorems holds for a particular choice of number of blocks which depends on a unspecified constant $\\gamma$ (and $\\xi$ in Theorem 4.1). What is it?\n\n+ In lines 275-276, it is claimed that the optimal error is of order $\\alpha \\log(1/\\alpha)$ over sub-exponential classes. Can the authors provide a reference for this statement?\n\n+ In Theorem 3.4: is the third moment assumption necessary? As far as I can tell, the statement is asymptotic (for sufficiently large n, no explicit estimate on n is given), and thus holds by the central limit theorem, so the second moment assumption should be enough.\n\n+ In section 4.2, the class $P_{SG}^{s}$ is presented as subclass of subgaussian distributions. This class however is more closely related to gaussian distributions than subgaussian ones (equality of moments is required, rather than just a bound). I suggest modifying the notation and the language to make this clear.", "limitations": "A main limitation of this work is the fact that it only deals with one dimensional mean estimation. This should be more prominently highlighted in the paper.", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n+ The paper is well written and the results are properly contextualized.\n+ The question of whether the median of means estimator is minimax optimal under adversarial contamination is interesting. The trimmed mean estimator is known to be robust to such contamination, but the situation, at least rigorously, is not as well understood for the median of means estimator.\n\nWeaknesses:\n+ The results are restricted to one dimensional mean estimation.\n+ Though it is nice to have rigorous statements, the results are somewhat expected and may have limited impact on the research area.", "was_revised": true, "final_justification": "My main concern with the paper was that the results are limited to one dimensional mean estimation. The authors promised to discuss this limitation in the writing which is a positive. Nevertheless, the comparable paper [1] - which studies the minimax optimality of the trimmed mean estimator under adversarial contamination - treats of the multivariate case, and on a technical level this is where most of the work is done. \n\nThe results of the current paper can still be of some interest, but I still think this is a borderline paper.\n\n[1]: Lugosi, Gabor, and Shahar Mendelson. \"Robust multivariate mean estimation: the optimality of trimmed mean.\" (2021): 393-410.", "rebuttal": "We would like to thank the Reviewer for the constructive feedback provided. The following provides detailed answers and clarifications for the Reviewer’s questions. We are confident that the comments and questions raised are fully addressed below, and we would be happy to answer any further questions the Reviewer may have during the authors/reviewers discussion period.\n\n**Dimensionality**: In this paper we have focused on the one-dimensional case since it is natural to study the MoM estimator only in this case. In higher dimensions, there is not a canonical extension of MoM since there is not a canonical (and efficient to compute) extension for the median. This is the reason related work for MoM has focused on the one-dimensional case [2-7].  Moreover, we  would like to emphasize that one-dimensional mean estimation is of high relevance, e.g., loss functions are univariate. One-dimensional focus is common in the robust mean estimation  literature beyond MoM estimator (e.g., [13, 24]). That said, we will describe this aspect of the paper more explicitly in the final version. Specifically, we will refer to MoM as a univariate mean estimator both in the abstract and in the introduction. Also, in Section 2.1 we will also emphasize that we are considering the one-dimensional mean estimation problem.  \n\n**Impact of the results**: To the best of our knowledge the results presented in the paper have not been proved and stated in the existing literature. In fact, [24] explicitly states that \"the asymptotic bias [of MoM] is not characterized and it is unclear whether the proposed estimator [MoM] achieves the minimax error bound.\" Theorem 3.2 in the submitted paper shows that MoM is minimax optimal under adversarial contamination for distributions with finite variance, while Theorem 3.3 extends the result to distributions with finite absolute $(1+r)$-th moment.\n\nFurthermore, as far as we know, Theorems 3.4 and 4.2 are the first lower bounds for the error of MoM under adversarial contamination. These lower bounds expose limitations of MoM that are new and unexpected based on existing results in the literature.\n\nTheorem 4.2 shows that MoM is suboptimal in the class of sub-exponential distributions. Notably, Theorem 4.1 together with Theorem 4.2 show upper and lower bounds with a matching order of $\\alpha^{2/3}$ for the asymptotic bias of MoM in the class of sub-exponential distributions. Such suboptimal order for MoM was unknown and unexpected.\n\n**Meaning of the constant $\\gamma$**: In Theorem 3.1, the constant $\\gamma\\in(2,2.5]$ can be thought as a dummy variable that describes the range of possible values for the number of blocks. More precisely, we have that the range of values for $k$ satisfying the result in Theorem 3.1 is\n$$k = \\max \\{ \\lceil \\frac{ \\log(2/\\delta)}{(1/2-1/\\gamma)^2} \\rceil, \\lceil \\gamma\\alpha n \\rceil \\} $$\nfor $\\gamma\\in(2,2.5]$.\n\nThe above discussion also shows that  the optimality of MoM in Theorem 3.1  is valid not for just one particular $k$ but for all the range of possible values for $k$. This is desirable since it can give more flexibility in the choice of $k$ in practical scenarios. The same comment applies to the rest of the theorems as all upper bounds hold for ranges of values of $k$ described by a numeric constant.  \n\n**Optimal error for sub-exponential distributions**: In lines 275-276 the paper mentions  that the optimal error is at most $\\alpha\\log(1/\\alpha)$. This is because the error of the trimmed mean is at most $\\alpha\\log(1/\\alpha)$ (to see this: apply the remark in page 10 from [23] to sub-exponential distributions). \n\n**Third moment assumption in Theorem 3.4**: As the reviewer points out, it is possible to have an asymptotic result by only requiring two finite moments. However, Theorem 3.4 is non-asymptotic, and that is why we need three finite absolute moments. Specifically, the result hinted by the reviewer holds by the CLT, which is asymptotic, whereas our result holds by Berry-Essen’s theorem, which is non-asymptotic. We appreciate the reviewer’s remark and in the final version of the paper we will comment that it is possible to have an asymptotic result under a second moment assumption. \nFurthermore, we will make Theorem 3.4’s statement more precise as follows:\n\n> Let $\\widehat\\mu$ be the MoM estimator with $k$ given as in (9) and (11). There exist positive constants $C,\\alpha_\\max,n_0$ and an adversarial attack such that for any $p\\in\\mathcal{P}_3,\\alpha<\\alpha_\\max,n>n_0$,\n$$\n| \\widehat\\mu-\\mu_p| \\geq C \\sigma_p \\alpha^{2/3}\n$$\n holds with probability at least $1-\\delta$.\n\n**Naming of the class $\\mathcal{P}^s_{\\text{SG}}$**: We agree with the Reviewer that the class $\\mathcal{P}^s_{\\text{SG}}$ is closely related to Gaussian distributions. However, this class is contained in the class of sub-Gaussian distributions but not in the class of Gaussians. Therefore, we have chosen such notation and language because it fits better with the common thread of the paper (start analyzing the optimality or suboptimality of MoM in a class of distributions. Then, analize MoM’s optimality in a subclass.)"}, {"review_id": "mXzQyBIE2e", "reviewer": "Reviewer_3535", "summary": "This paper studies the optimality of the Median-of-Means (MoM) estimator under adversarial contamination. It establishes error bounds for various distribution classes and shows that MoM is minimax optimal in settings with finite variance, certain heavy-tailed distributions, and symmetric distributions, while being sub-optimal for light-tailed cases. The theoretical results are supported by numerical experiments presented in the appendix.", "questions": "As aforementioned, could the authors provide further insights into why MoM underperforms in light-tailed settings, possibly suggesting modifications to address this gap?", "limitations": "See 'Weakness' part.", "rating": 2, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths\n- The paper rigorously provides upper and lower bounds for the MoM estimator under adversarial contamination across various distribution classes.\n- The paper not only proves MoM’s strengths but also highlights its sub-optimality for light-tailed distributions, offering a realistic assessment.\n\nWeaknesses\n- As the paper also illustrates, the number of blocks $k$ must be carefully tuned depending on the underlying data distribution to achieve optimal performance. However, the authors do not provide any practical guidance or theoretical insights on how to choose $k$ in practice. A more detailed analysis of how the block size affects the robustness and accuracy of the estimator would strengthen the work and make the results more actionable.\n- The constant $C$ in the proposed error bounds is not tightly controlled or minimized. By providing a more detailed description of how to minimize this constant, or non-asymptotic results, could show the way to improve the practical applicability of the estimator.\n- The paper identifies that MoM is sub-optimal for light-tailed distributions, but it doesn’t provide sufficient insight into why it struggles in these cases or potential strategies to improve performance under such conditions.\n- While the paper presents theoretical results and bounds through solid mathematical proof, there is a lack of empirical validation or numerical experiments that demonstrate the practical effectiveness of the proposed bounds and estimators in real-world settings.\n- The results are focused on specific classes of distributions (e.g., finite variance, heavy-tailed, symmetric), but they do not consider more complex distributions or non-i.i.d. settings. The assumptions about the underlying distribution may limit the applicability of the MoM estimator in diverse real-world data scenarios.", "was_revised": true, "final_justification": "I prefer to maintain my original score.", "rebuttal": "We would like to thank the Reviewer for the feedback provided. However, we find some of the Reviewer’s comments unclear. The following provides detailed answers and clarifications for the Reviewer’s questions. We would be happy to answer any further questions the Reviewer may have during the authors/reviewers discussion period.\n\n**Underperformance of MoM for light-tails**: we appreciate this interesting comment by the Reviewer. As we point out in the paper, MoM’s performance improves when the distribution is light-tailed (Theorem 4.1). However, MoM does not achieve the optimal order since there exist light-tailed distributions whose median is significantly different from their mean. Therefore, as MoM underperforms for asymmetric distributions, it consequently also underperforms for some light-tailed distributions. This is because MoM estimates the mean as the median (biased estimator of the mean) of $k$ sample means (unbiased estimator). Therefore the bias of the median makes MoM underperform in distributions with asymmetry (median significantly different to the mean). That is, the error of MoM decreases slower for asymmetric distributions. \n\nProviding modifications for MoM to address this gap is beyond the scope of the paper, which is to analyze the optimality/suboptimality of MoM. One possible solution could be to use instead the Lee-Valiant estimator which is a modification of MoM that aims to correct the bias introduced by the median. However, the asymptotic bias of the Lee-Valiant estimator  has not been characterized for light-tailed distributions. It could be interesting to know whether Lee-Valiant’s estimator outperforms MoM or not. \n\nIn the final version we will include this discussion after Theorem 4.2.\n\n**Generality of the considered distributions and non-i.i.d setting**: \nWe do not really understand these comments from the Reviewer. The classes of distributions we consider are completely general and complex since we consider distributions with finite variance and even infinite variance. Moreover, the classes of distributions we consider are common in related work [23, 24].\n\nThe setting considered in the paper of adversarial contamination is a general non-i.i.d. setting where an adversary replaces a fraction of the samples  with arbitrary values, and possibly creating dependences among the samples. Adversarial contamination generalizes many real-word situations such as additive contamination and Huber’s contamination model, among others.   \n\n**Numerical experiments for a proposed estimator**: \nWe do not really understand this comment from the Reviewer. We would like to stress that the paper does not propose an estimator.  \nThe goal of the paper is to theoretically analyze the optimality and suboptimality of the well-known MoM estimator for different classes of distributions. Therefore, practical applications are beyond the scope of this work. In fact, it is common in robust mean estimation papers to not include numerical experiments of real-world settings (e.g., [23, 8]).\n\n**Tuning of the number of blocks $k$**:  as we point out in lines 248-250, it is common for estimators to require a parameter (in the case of MoM, the number of blocks $k$) to be adjusted based on the underlying distribution. For instance, Catoni’s M-estimator requires selecting an appropriate function [24]. That said, the goal of the paper is to analyze the optimality/suboptimality of the MoM estimator for different classes of distributions. Therefore, finding a way to tune $k$ is beyond the scope of the paper.\n\n**Constant $C$ in the bounds**: As described above, the goal of the paper is to analyze the optimality/suboptimality of the MoM estimator for different classes of distributions. Therefore, the results in the paper aim to clarify the optimality of MoM and the constant used in the bound does not change the optimality of the estimator (see also lines 204-207 in the paper). This is the reason we did not minimized the constant, similarly as other works in the topic as [23].\nIn Theorems 3.2 and 3.3 we include an asymptotic expression for the leading constant to give an intuitive idea of its value. In the proofs of Theorem 3.2 we give the exact value of the constant, which is\n$$\n  C = 2\\sqrt{2+\\sqrt{2}} \\left( \\frac{1}{(1/2-1/\\gamma)^{3/2}} + \\frac{\\sqrt{\\gamma}}{(1/2-1/\\gamma)^{1/2}}   \\right).\n   $$"}, {"review_id": "YH2dEJNVBO", "reviewer": "Reviewer_QWU9", "summary": "In this paper, the authors present upper and lower bounds for the error of MoM under adversarial contamination for multiple classes of distributions. In particular, the authors show that MoM is (minimax) optimal in the class of distributions with finite variance, as well as in the class of distributions with infinite variance and finite absolute (1+r)-th moment. The authors also provide lower bounds for MoM’s error that match the order of the presented upper bounds, and show that MoM is sub-optimal for light-tailed distributions.", "questions": "Please check the points mentioned in \"Strengths And Weaknesses.\".", "limitations": "Yes.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\nThe paper correctly defines the problem. It explains the model, restrictions, related assumptions, and the main problem by addressing all related issues.\n\nWeaknesses: The paper has some shortcomings, and I will mention them here:\n1. In Definition 3.1, why do you use Q_m(q) to quantify the upper bound of estimation error? What is the insight behind the math?\n\n2. In Theorem 3.1, could you please show more analyses for Theorem 3.1, since I cannot get more insights into this upper bound. For example, the performance with special cases could be discussed.\n\n3. As for line 171, the authors say \"Indeed, we assume only that the mean of the inliers is finite.\" I recommend that this assumption is given in an individual environment.\n\n4. In Theorem 3.1, we can see that $\\alpha<1/2$. In Theorem 3.2 and Theorem 3.3, why $\\alpha\\leq 0.4$ and $\\gamma \\in(2, 2.5]$? The assumption seems to be stronger. \n\n5. In Lemma A.1, in line 453, the authors assume that the random variable follows binomial distribution, but I cannot see the variable q in the results.\n\n6. In line 469, Why $\\sqrt{}+\\alpha m<1/2$ holds true? $m$ is the size of the block, for example, if $m=1000$, $\\alpha=1/10$, $\\alpha m=100$, which is not less than $1/2$.\n\nIn this upper bound, if we use Lemma A.1, why there exists $1/2+\\alpha m$?", "was_revised": true, "final_justification": "The authors have addressed my questions and comments. Given the discussions and rebuttal, I keep my score for acceptance.", "rebuttal": "We would like to thank the Reviewer for the constructive feedback provided. The following provides detailed answers and clarifications for the Reviewer’s questions. We are confident that the comments and questions raised are fully addressed below, and we would be happy to answer any further questions the Reviewer may have during the authors/reviewers discussion period.\n\n**Insights and intuition behind Theorem 3.1 and the usage of function $Q_m$**: \nThe function $Q_m$ describes the quantile function of differences between averages of m i.i.d. samples and the actual mean. Since MoM carries out a median of averages corresponding to the samples in each block, its value is between two quantiles of averages of i.i.d samples (those corresponding to blocks without contaminated samples). The specific quantiles upper and lower bounding the value of MoM depend on the number of blocks without contaminated samples, which depend on the fraction of contaminated samples and on the number of blocks used, as described in the statement of Theorem 3.1. \n\n\n**Finite mean assumption for Theorem 3.1**: In the final version of the paper we will revise the sentence, in order to improve clarity, as follows:\n“In fact, no additional assumptions on the distribution of the inliers is required.”\nWe emphasize that the mean has to be finite in order to be possible to estimate it.  \n\n**Contamination tolerance in Theorems 3.2 and 3.3**: The contamination tolerance in Theorems 3.2 and 3.3 is lower than $1/2$ because of technical constraints in the proofs. This is a common phenomenon in robust mean estimation as many estimators have a contamination tolerance significantly lower than $1/2$. In fact, the results in the paper show that MoM tolerates more contamination than other estimators. Specifically, the results in the paper hold for all $\\alpha\\leq0.4$, whereas as described on lines 200-203, existing results establish a contamination tolerance of $\\alpha\\leq0.13$ for the trimmed mean, and of $\\alpha\\leq0.36$ for Catoni's M-estimator.\n\n\n**Binomial distribution in the proof of Lemma A.1**: There is not a variable $q$ in the results, $q$ is used as a dummy variable to explain the notation. In the final version, we will improve the clarity of the sentence in line 453 as follows:\nWhere, for any $m\\in \\mathbb{N},q\\in[0,1]$,  $\\text{Bin}(m,q)$ denotes a random variable drawn from a binomial distribution of $m$ trials with a probability of success $q$.\n\n**Inequality in the proof of Theorem 3.1 (line 469)**: The inequality in line 469 is valid since $k>2\\alpha n$. Specifically, since, $m=[n/k]$, the assumption $k>2\\alpha n$ becomes  $ m < 1/(2\\alpha)$. For instance, in the example mentioned by the Reviewer we have that $\\alpha=1/10$ implies $m < 5$.\n\nIn the proof of Theorem 3.1, $1/2+\\alpha m < 1$ holds because for the choice of $k$ in the statement of the theorem (see equation (9)) we have that $k>2\\alpha n$ so that $ \\alpha m < 1/2$ since $m=[n/k]$."}]

Author rebuttal:

Meta-review: This work studies the performance of the classical Median-of-Means (MoM) estimator for univariate distributions, including finite variance distributions, in the presence of a small constant fraction of arbitrarily corrupted datapoints. The main contribution is a collection of essentially tight upper and lower bounds on its performance for each of these families. With the exception of a highly problematic review, the reviewers overall appreciated the contribution. While the paper may be viewed as borderline by some (given the extensive amount of work in this area recently), I believe that the contribution is valuable and the submission is slightly above the acceptance threshold.
Decision: Accept (poster)