All-Purpose Mean Estimation over R: Optimal Sub-Gaussianity with Outlier Robustness and Low Moments Performance
Authors: Jasper C.H. Lee
Walter McKelvie
Maoyuan Song
Paul Valiant
Venue: ICML 2025 oral (2025)
Keywords: mean estimation
instance optimality
robust statistics
Primary area: theory->learning_theory

Abstract: We consider the basic statistical challenge of designing an "all-purpose" mean estimation algorithm that is recommendable across a variety of settings and models.
Recent work by [Lee and Valiant 2022] introduced the first 1-d mean estimator whose error in the standard finite-variance+i.i.d. setting is optimal even in its constant factors; experimental demonstration of its good performance was shown by [Gobet et al. 2022].
Yet, unlike for classic (but not necessarily practical) estimators such as median-of-means and trimmed mean, this new algorithm lacked proven robustness guarantees in other settings, including the settings of adversarial data corruption and heavy-tailed distributions with infinite variance.
Such robustness is important for practical use cases.
This raises a research question: is it possible to have a mean estimator that is robust, *without* sacrificing provably optimal performance in the standard i.i.d. setting?
In this work, we show that Lee and Valiant's estimator is in fact an "all-purpose" mean estimator by proving:

(A) It is robust to an $\eta$-fraction of data corruption, even in the strong contamination model; it has optimal estimation error $O(\sigma\sqrt{\eta})$ for distributions with variance $\sigma^2$.

(B) For distributions with finite $z^\text{th}$ moment, for $z \in (1,2)$, it has optimal estimation error, matching the lower bounds of [Devroye et al. 2016] up to constants.

We further show (C) that outlier robustness for 1-d mean estimators in fact implies neighborhood optimality, a notion of beyond worst-case and distribution-dependent optimality recently introduced by [Dang et al. 2023].
Previously, such an optimality guarantee was only known for median-of-means, but now it holds also for all estimators that are simultaneously *robust* and *sub-Gaussian*, including Lee and Valiant's, resolving a question raised by Dang et al.
Lastly, we show (D) the asymptotic normality and efficiency of Lee and Valiant's estimator, as further evidence for its performance across many settings.

All-Purpose Mean Estimation over R: Optimal Sub-Gausiannty with Outlier Robustness and Low Moments Performance
Jasper C.H. Lee! Walter McKelvie
Maoyuan Song² Paul Valiant
Abstract
optimality guarantee was only known for median- of-means, but now it holds also for all estimators that are simultaneously robust and sub- Gaussian, including Lee and Valiant's s, resolving question raised by Dang et al. Lastly, we show (D) the asymptotic normality and efficiency of Lee and Valiant's estimator, as further evidence for its per- formance across many settings.
We consider the basic statistical challenge of designing an "all-purpose" mean estimation al- gorithm that is recommendable across vari- ety of settings and models. Recent work by Lee & Valiant (2022) introduced the first 1-d mean estimator whose eтror in the standard finite- variance+i...dd setting is optimal even in its con- stant factors; experimental demonstration of its good performance was shown by Gobet et (2022). Yet, unlike for classic (but not necessar- ily practical) estimators such median-of-means and trimmed mean, this new algorithm lacked proven robustness guarantees in other settings, in- cluding the settings of adversarial data corruption and heavy-tailed distributions with infinite vari- ance. Such robustness is important for practical use cases. This raises research question: is possible to have mean estimator that is robust, without sacrificing provably optimal performance in the standard i.i.d. setting? In this work, we show that Lee and Valiant's 's estimator is in fact an "all- "all-purpone purpose" mean estimator by proving:
1. Introduction
The past decade has seen reinvigorated interest in under- standing fundamental statistical problems, and in particular, the foundational problem of mean estimation: given n sam- ples from an unknown distribution, and an allowed failure probability 8, what is the most accurate estimate of the dis- tribution mean? The sample mean the traditional estimate, yet, its sensitivity extreme values makes it an unreliable estimator in practice. Other classic estimators, for exam- ple the knoln median tetiian-offmane -if---off--ssss-- estimator (Alon et al., 1999; Nemirovsky & Yudin, 1983; Jerrum et al., 1986), also suffer from poor empirical performance.
Recent work by Lee Valiant (2022), sitting in a line re- search initiated by the seminal paper of Catoni (2012), gave the first 1-dimensional mean estimator whose estimation er- ror is optimal (i.e. sub-Gaussial error) and tight even in the leading constant. Gobet et al. (2022) further demonstrated its good empirical performance against other competing estimators.
(A) It robust to an r--frcction of data corrup- tion, in the strong contamination model; it has optimal estimation error ((a for distributions with variance o².
For distributions with finite 2h moment, for 21, it has optimal estimation error, matching the lower bounds of Devroye et al. (2016) up to constants.
Fact 1.1 (Lee & Valiant 2022). Given any distribution D with mean I and variance o² (both unknown),, parameters nu, 8 > O, let X be a set of independent samples from D. Then, with probability at least 1 over the sampling pro- input ô and X will oulput an estimate i with error most
We further show (C) that outlier robustness for 1-d mean estimators in fact implies neighborhood optimality, a notion of beyond worst-case and distribution-dependeed optimality recently intro- duced by Dang et al. (2023). Previously, such an
cess, Estimator
log 1 Ip - 1 uIso. (
University of California, Davis *Purdue University "Columbia University "Harvard University. Correspondence to: Jasper C.H. Lee <jasperlee Saapeenlo@duddavs.ccc..uu
Proceedings of the ndnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
log .) + (0, 0) and,
Here, the o(1) term tends to 0 as crucially, is independent of D.

---

All- All-Purpose Mean Estimation over R
Estimator 1 Mean Estimator of Lee and Valiant Inputs: i..dd samples (z,) ): Confidence parameter 8.
Is it possible for mean estimator satisfy the important robustness guarantees of classic estimators, without losing the strong and optimal-constane performance that the Lee and Valiant estimator enjoys in the standard setting?
1. Compute an initial estimate x using any sub-Gaussian, scale-and-translatee -iauiaaaiooneiivaiaann and robust mean esti- mator (cf. Facts A.18 and A.23). One possible choice is the median-of-meam estimate: evenly partition the data into log 1 set of means of the groups;
In this paper, we show 4 strong positive results demonstrat- ing the robustness and performance of Estimator
& groups and let i be the median of the
(A) In the presence of 17-fraction of arbitrary adversarial cor- ruption, the error of Estimator 1 degrades by only O(a from the sub-Gaussian error guaranteed in Fact 1.1. This extra error term is optimal under the assumption that the distribution has (finite) variance o².
2. Find the solution a the monotonic, piecewise-linear equation
(B) When samples are drawn from a distribution with fi- nite 20 moment, for (1, Estimator achieves error matching the lower bound of Devroye et al. (2016) up to constants.
E, min(a(;; - -x)?, llg 3/
3. Output:
(C) Estimator I enjoys a fine-grained beyond beyond-worst-case no- tion of optimality called neighhorhood optimality, recently introduced by Dang et al. (2023). Previously, only median- of-means was known be neighborhood optimal, and our result answers the question raised by Dang et al. on whether more modern estimators are also neighborhood optimal. (D) Under the standard finite variance and i.i.d. setting, Lee and Valiant's estimator is asymptotically normal and effi- cient.
k + x) min(a(2; - -x)², 1))
The constant "V2" in Fact 1.1 is optimal, with matching lower bounds. Essentially, Estimator uses Step I to find a preliminary estimate (c.g. using median-of-means. but it can be other choices as well), which is then refined in Steps 2 and 3 into better eshim accuracy is optimal even in the leading multiplicative constant. Even though the form of the estimator is somewhat complicated-includiit function inversion in Step 2-the estimator can in fact be computed easily in quasilinear time via a sorting opera- tion, or even in linear time using a more subtle algorithm. See (Lee& & Valiant, 2022) for more discussion of the design and analysis of Estimator 1.
We emphasize that these new results hold without any changes at all either the structure or the parameters of Estimator 1. That is, the estimator does not need to know that it is being expected to perform in these challenging settings. The guarantees we show also smoothly revert to Fact 1. as the amount of corruption decreases to 0, or as the 2h moment assumption tends to 2 2
These results, in aggregate, demonstrate that Lee and Valiant's estimator is in fact "all-purpose", enjoying the same breadth of guarantees as either median-of-means or trimmed mean, while also having what is essentially the smallest possible estimation error (even in the leading con- stant) in the standard setting. Thus, Lee and Valiant's 's esti- mator should be used in practice over existing estimators.
While Fact 1.1 is strong recommendation for Estimator 1, getting optimal performance in this regime is not the only practical desideratum for an estimator. Practitioners have long observed that some real-world distributions are very heavy-tailed, with variances that are gigantic (thus render- ing guarantees like Fact 1.1 effectively useless), but whose lower moments-berweed the first and second moments- might be much more bounded. Further, real-world data can be subject to random or even adversarial corruption. Per- formance guarantees in these more demanding settings are therefore critical for practice. However, while there are rela- tively straightforward folklore analyses of classic algorithms in these settings-including notably, median-of -ofiiann---- and trimmed mean-Lee and Valiant's estimator has not been studied in these contexts. The breadth of guarantees shown for these classic estimators might therefore lead researchers and practitioners to choose either of them over Lee and Valiant's is estimator, despite the latter being more accurate estimator in standard finite variance i.i.d. sample settings.
2. Our Results at a Glance
We now formally state our technical contributions.
2.1. Outlier robustness
Lee and Valiant's estimator is robust against data corruption from the strong contamination model, the most adversarial data corruption model in the literature.
Definition 2.1 (Strong Contamination Model). Given cor- ruption parameter 17 and a distribution D on the uncorrupted data, an algorithm gets a set of n 1-corrupted samples from D as follows. The algorithm specifies n and nature draws
The natural and pressing research question, then, is
2

---

All-Purpose Mean Estimation over R.
i.i.d. samples from D. Then, an arbitrarily powerful ad- versary can inspect the samples from D, and arbitrarily replace [m]] of them before giving the (new) set of samples to the algorithm, with no indication of which samples were corrupted.
Suppose both log. and 5 are bounded by some small uni- versal constant, and suppose 1) I 9m.
1 log 1 8. Let 6' be so that 1 log 3 = 3 log & + 3mn. Then, with probability at least 8' over the sampling process, Estimator I on input ö and X will output estimate with error most
3
In the setting of 17-coruuptio, when we only assume that D has a finite variance o², it is well-known (Diakonikolas & Kane, 2023) that the minimum estimation error is (1)))) even if there are infinitely many samples. Our analysis of Lee and Valiant's estimator shows that it achieves this estimation error bound, as long as the amount of corruption is (log / /n)-wh ó, the desired failure probability, is a parameter under the user's control. Put differently, the parameter for Estimator can be viewed as "dual use", parameterizing not just the allowed failure probability of the estimator, but also its desired robustness, expressing the maximum tolerated level of corruption.
(IVE+ O(DNN
log Φ + +133 + (o)))
So. As-M I - 1l
We emphasize again that, similar to Theorem 2.2, Theo- rem 2.3 says that Estimator 1 adapts the value of v) with- out knowing what it is precisely. Namely, Theorem 2.3 simultaneously holds for all values of 8' even though the algorithm is only given a fixed 8.
We sketch the proof of the above two theorems in Section and give full details in Appendix A. While the v2 con- stant in the sub- Gaussian terms tight, we expect that the constants in the robust error terms (222 and 135) might be significantly improved with a different proof strategy.
We emphasize that in the following theorem, Estimator does not need to know the precise value of n, the frac- tion of corruption. It only makes the assumption that 7 I (log //n), or in other words, Estimator adapts to the level of corruption.
In Appendix B, we also show that Estimator is robust in the Huber and Total Variation Contamination Models, in addition to the Strong Contamination Model above.
Theorem 2.2. Given any distribution D with mean I and variance a², parameters n, 6, 0, let X be a set of n n-corrupted samples from D.
Median-of of-innnss also has guarantees analogous to the above, but they are folklore. See the proofs of Theorem 2.2 and Theorem 2.3 in Appendix A.4 and Appendix A.3 respec- tively for the formal statements and proofs of these folklore guarantees. Trimmed mean also gives analogous robustness guarantees, but current analysis (see Oliveira et al. (2025)) requires precise knowledge of r) in order to match the op- timal rate. In contrast, although Estimator does require an upper bound on 1) (from the necessary assumption that n 1 log }), the accuracy will gracefully improve if the actual corruption rate is less than the pessimistic upper bound.
Suppose both 1 and ō are bounded by some small uni- versal constant, and suppose 17 S 24n lo. }. Then, with probability at least 1 1-6 8 over the sampling process, Estima- tor 1 on input 5 and X will output an estimate ja with error at most
j - ulso. (V2+
log
1 & + 22
In the above theorem, Estimator 1 gets as its input param- eter, and fails with probability 8. Accordingly, the estimator error is the sum of the sub-Gaussian error term from Fact 1.1, and new "robustness" term of O( vT). On the other hand, the standard robustness analysis and guarantee of trimmed mean takes& different form (see Oliveira et al. (2025))-ig if the desired failure probability is 5' and the corruption pa- rameter is 77. then the number of trimmed samples chosen as log 1 Ollo & + 1p)). We give an analogous theo- rem for Estimator I, where again we preserve the optimal error term. Comparing
We further stress that, while median of-nn and trimmed mean both have relatively straightforward and folklore proofs of robustness, the analysis required for the Lee and Valiant estimator much more intricate- this is due the fact that Lee and Valiant's 's estimator is (a lot) more compli- cated, in order to yield optimal constants in the i.i.d. setting.
2.2. Low moment performance
constant of 2 in the Theorem 2.2 with Theorem 2.3, the latter asks for fail- ure probability 8' >6 8, but correspondingly has a smaller sub-Gaussian error term (since log 1 < log 3)- 8'
Next, study the performance of Lee and Valiant's estima- tor when given data drawn from a distribution that only has finite low moments, specifically, moments between and 2.
Theorem 2.4. Given any distribution D with mean a and th moment M, for some 2 E (1,2), let X be a set of n i..d samples from D. Then, with probability at least 1 - 8 over the randomness of X, Estimator I on imput 8 and X
Theorem 2.3. Given any distribution D with mean and
variance o², parameters n, 5, r7 > 0, let X be a set of n n-corrupted samples from D.
3

---

All- All-Purpose Mean Estimation over R.
will oulpul an estimate ii with error most
equals 1; then, return the distribution D conditioned on lying in 11+ - 14 +).
log 1
1-
ji - 11 (M,, (1 + +(1))
Given and 8, define the trimmed distribution D to be the 0.40
x log 1-trimmed version of D. When ó is implicit, we may denote this D-- Now define the error function
where C2. = 2(5.6)== -1 Here, the o(1) term tends to 0 10s.2.0 6) - (0,0) in a manner independent of D and independent of
Cn.a (D) = la P + o.V 1o where je, and o are the mean and standard deviation of D respectively.
as
Dang et al. show that median-of- achieves error ((Gn,((D), and raises the question of whether more mod- ern estimators such as Lee and Valiant's (Estimator 1) also achieve this error bound and are hence neighborhood op- timal. We show a more general result: in fact, every sub- Gaussian and robust estimator (satisfying a slight variant of Theorem 2.2) achieves this error bound.
The above result matches the lower bounds shown by De- vroye et al. (2016) up to constants. As - 2, the guar- antee converges to Fact 1.1. Analogous results (up to con- stants) were shown for median-of- means in Bubeck et al. (2012), but the multiplicative constant we achieve for Es- timator 1, (2(5.6) - is better than that of median-of- means (12) - 1) across all values of E (1,2).
Proposition 2.6. Let ja be an arbitrary estimator that, when given 8 > 0 and set of n c-corrupted samples from any distribution D with mean and variance o², outputs mean estimate satisfying
2.3. Neighborhood optimality
Going beyond the worst-case analysis of Estimator 1, we give a finer-grained analysis of its performance. We provide maite- error bounds that optimally adapt to the under- lying distribution is far stronger than just having optimal dependence the variance.
+ vii ))
log n
l - 11 SO
instance-by-intaaee basis, which
with probability at least 1 over the randomness of the (uncorrupted) samples.
Recent work by Dang et al. (2023) gave a first study of the fine-grained optimality of 1-dimensional mean estima- tors, providing upper and lower bounds that match up to constants. At high level, they showed that error bounds are essentially all one can hope for, for any distribution with finite mean. More specifically, they de- fine an error rate function (D) over distributions D, and prove that i) median-of-meant means attains this error bound: and ii) for any distribution D, there exists a "reasonable" counterpart distribution D' such that no algorithm can dis- tinguish between the distributions, and thus no estimator can simultancously get error < cn,5 (D) using samples from D, while also getting error < 6n,5 (D') using samples from D'. We define 6,,6 (D) below. The combination of lower and
Then, the same estimator j., on input n i.i.d. samples drawn from a distribution D with finite mean, will output an esti- mate with error upper bounded by ((n,,(D) (as defined in Definition 2.5) with probability at least 1 1-6.
We formally prove Proposition 2.6 in Appendix C. The precondition of Proposition 2.6 is implied by mild variant of Theorem 2.2 (decreasing the failure probability from to 8/2), which holds also for Estimator 1. As a consequence:
Corollary 2.7 (Informal). Estimator is neighborhood optimal, in the sense of Dang al. (2023).
In Section 5, we state the formal definition of neighborhood optimality and discuss the intuition on Proposition 2.6.
upper bounds of i) and ii) is extended into new optimality notion called neighborhood optimality by Dang et al.
2.4. Asymptotic normality and efficiency
Intuitively, these are bounds that are optimal in an instance- by-instance basis, because property (ii) shows that no al- gorithm can get error better than 6n,a (D) on samples from distribution D-even algorithm customized specifically for distribution DD-withou getting unacceptably bad error on a designated nearby distribution D'.
Lastly, we show that Lee and Valiant's 's estimator is asymptot- ically normal and efficient, under the standard finite variance and i.i.d. sample assumption. In particular, we show that, if the parameter in Estimator 1 is fixed, and the number of samples n - oc, then Estimator converges in prob- ability the sample mean at the appropriate scale. The Central Limit Theorem for the sample mean then implies the asymptotic optimality of Lee and Valiant's estimator as corollary.
For concreteness, we define (D) below.
Definition 2.5 (Dang et al. 2023). Given a (continuous) distribution D with mean μl and a real number t E [0, 1]. define the t-trimming operation on as follows: select a radius r such that the probability mass in Ju r. +
Theorem 2.8. Let D be a distribution with mean and variance a².
4

---

All- All-Purpose Mean Estimation over R
Let is denote Estimator 1 on input parameter ô and n L..d. samples from D. Also let X denote the sample mean. Then, fixing ô and D and laking + Jc, we have
showing that median-of- achieve such rates. Our work shows that in fact all estimators that simultaneously achieve (big-O) optimal sub-Gaussian and robust estimation error must also achieve the distribution-speciie rates (Proposition 2.6). In addition to the standard i.i.d. set- ting, a different line of work has also studied distribution- specific mean estimation error rates for various differential privacy settings (Asi & Duchi, 2020a;b; Huang et al., 2021).
optimal error
Vup E VnXn
that is. IVnn- vnlul S 0, that vnp converges to VnXn in probability.
As a corollary, by the Central Limit Theorem, we have
Robust mean estimation. Robust statistics, the setting where part of the input data can be corrupted by an adversary, has been an active area of research the statistics commu- nity since the 1960s (Huber, 1992; Tukey, 1960). However, it was only in the past decade that polynomial-time algo- rithms for these statistical problems were found. See the textbook of Diakonikolas & Kane (2023) for a detailed in- troduction to these recent advances. Most directly relevant to our present work are results that give simultaneously sub-Gaussian and robust mean estimators, even arbitrary high dimensions (Diakonikolas et al., 2020; Depersin & Lecué, 2022; Hopkins al., 2020). Median-of-means is also known to be such a robust and uub-Gaussian estimator in I I-dimension this is a folklore result, but see Laforgue et al. (2021) for more details on the analysis in the robust setting. Similarly, trimmed mean also has a folklore analysis for its robustness, and see Oliveira et al. (2025) for more re- sults on the robustness and additional properties of trimmed mean.
Vnlp p) 1 N (0.
That is, ji is asympiotically normal and efficient.
The above theorem contrasts with the asymptotic behavior of median-of-means, whose error-scaled by vn conveoess to (0, (T/2) (2) (Minsker, 2023); median-of-means thus has asymptotic variance a v/2 #/2-factor larger than desired.
3. Related Work
Mean estimation in 1 dimension. Mean estimation, even in I-dimension, has been studied algorithmically since the 1980s. The classic cadiian-of-means. estimator was the first big-O optimal sub-Gaussian mean estimator proposed in the literature, independently invented by different groups of authors (Alon et al., 1999; Nemirovsky & Yudin, 1983; Jer- rum et al., 1986). Catoni's influential work (2012) gave the first sub-Gaussian mean estimator that yields the tight multi- plicative constant in its error, but under strong assumptions that either the variance is known (to extremely high accu- racy) or the distribution kurtosis (normalized 4th moment) is bounded. Followup work by Devroye et al. (2016) studied "multiple-5" estimators, also with sharp error constants, in the same setting. More recently. Lee & Valiant (2022) con- structed a sub-Gaussian mean estimator with tight constants, under the bare minimum assumption that the variance exists, and absent any extra knowledge or moment assumptions- this estimator is the subject of study in the current work.
4. Outlier Robustness
In this section, we outline the proof of Theorem 2.2 (re- stated below for the reader's convenience), which says that Estimator 1 is robust against adversarial data contamination from the strong contamination model of Definition 2.1. The proof of Theorem 2.3 has analogous structure.
Theorem 2.2. Given any distribution with mean p and variance o², parameters n, 5, >> 0, let X be set of n-corrupledd samples from D.
See the survey of Lugosi& & Mendelson (2021) on mean estimation results prior to 2019.
Suppose both log and 5 are bounded by some small uni- versal constant, and suppose nj S 1 log 3. Then, with probability at least - over the sampling process, Estima- tor on input 8 and X will output an estimate pa with error at most
In low moment settings where the underlying distribution might have infinite variance, Bubeck et al. (2012) studied the performance of median-of-means. Devroye et al. (2016) then showed lower bounds that match up to constants. Our work shows that Lee and Valiant's estimator achieves anal- ogous results as median-of-men of-mm in these regimes (Theo- rem 2.4), with sharper dependence on the 2th moment, for every: E 21,
24m
In 1-1550 (V2+0(1)))
log + +2222
"Beyond worst-case analysis" of 1-d mean estimators is a new research topic of recent interest in the community. In the standard i.i.d. setting, Dang et al. (2023) characterized the optimal distribution-sseciff error rates up to constants,
The proof strategy is to bound the difference between the estimates returned by Estimator on (corrupted) samples X versus its behavior on uncorrupted samples X, fixing the confidence parameter
5

---

All-Purpose Mean Estimation over R
Changing the input from uncorrupted samples cornupted samples has two effects on the resulting estimate:
Lemma 4.3. In the setting of Lemma 4.2, suppose both log i and are bounded by some small universal constant, and suppose 1i S Zi
log J. With probubility at least 1 - 46/11 over the sampling of n. samples X from a distribution D with variance 0², we have à 2 0.0008496n.
1. The a "influence parameter" (as computed in Step 2 of Estimator 1) may change. However, we show that in a certain sense, when the fraction of corruption 1j is small compared to log //n, this corruption will not change the computed a value by much (Lemma 4.2). We further show that artificially changing the a value by a small amount will not change the mean estimate of Step 3 by much, with high probability, when given uncorrupted samples.
These lemmas let us bound & even when given corrupted data, and relate it to the uncorrupted a; these bounds are the crucial tools needed to bound the mean estimation er- ror in both Theorem 2.2 and Theorem 2.3. Lemma 4.3 is used in the proof of Theorem 2.2. and shown inside Propo- sition A.2 in Appendix A.4. The proof of Theorem 2.3 has an analogous lemma with slightly different parameters.
2. For a fixed influence parameter a, corrupting the samples from X to X changes the returned mean estimate. However, we show (high probability) lower bound on the value a computed by the algorithm on input X (Lemma 4.3); and this lower bound on a gives us natural upper bound on how much any corrupted input value can affect the final mean estimate.
The full analysis of the outlier robustness of Estimator 1 is given in Appendix A.
5. Neighborhood Optimality
We state here the two key structural lemmas (and a corre- sponding prerequisite definition) for the a value computed from corrupted samples X.
Neighborhood optimality is a new notion of fine-grained distribution-dependdee optimality recently proposed by Dang et al. (2023). While sub-Gaussian bounds are worst- case optimal for the class of finite variance distributions, neighborhood optimality captures the extent which esti- mators can beneficially adapt to the non non- non-Gaussianity of the underlying distribution and outperform the sub-Gaussian bound.
Definition 4.1. Let X = {x.} be a set of clean samples, and let X = } be the corresponding set of n-corrupted samples. Denote by ap the "influence parameter" computed from the clean samples so as to satisfy version of Step 2 but with modified right hand side (5log 8 + pm instead of y loo }
Before we formally state the definition of neighborhood optimality, let us give some preliminary definitions.
Σ min(a,a7, 1) log + pm
Let Pi be the entire set of all distributions with finite first moment over R. We say that N is neighborhood function (defined over PI) if N maps a distribution D E PI to a set of distributions (D) S P1. Intuitively. the neighbor- hood (D) of D is a set of distributions that we expect an estimator to perform similarly well on (and we typically consider neighborhoods where D E N(D)) ). Similarly, an error function e maps distributions to non-negative numbers, like the function introduced in Definition 2.5. In the later definitions, we use the notations N,,5 and en,5 to indicate their dependence on the sample complexity n and failure probability 6.
and denote by ap the corresponding "influence parameter" computed instead from the corrupted samples:
Σ miin 1) = 3 8
1og + pm
Lemma 4.2. Consider an arbitrary set of samples X and new sample set X n-corrupted from X. Consider also an arbitrary imput parameter 8. Using â denote the influence parameter of Estimator I on inputs (8, X), i.e. ön in Definition 4.1, we have
Given these two notions, we can now define the notion of a neighborhood Pareto bound, as a property that an error func- tion satisfies. Essentially, the definition imposes admissibil- ity/Pareto efficiency structure within the local neighborhood Nu.a (T,,(D)) (D) of every distribution D E Pi.
Q-27 S à 5 5229 022
Considering the right hand side of the condition in Step 2 of Estimator as expressing the level of "desired robustness": Lemma 4.2 states that the modified influence parameter from y-corruption is always sandwiched between the uncor- rupted influence parameters, but at slightly different levels of desired robustness. We point out that Lemma 4.2 is a deterministic lemma, that always holds, regardless of the sampling over X.
Definition 5.1 (Neighborhood Pareto Bounds (Dang et al., 2023)). Let be the number of samples and 8 be the failure probability. Given neighborhood function N,.8 : Pi + 2P, we say that the error function (D)) P1 + R is a neighborhood Pareto bound for P, with respect to N,.5 if for all distributions D E P1, no estimator á taking n i.i.d. samples can simultaneously achieve the following two
6

---

All-Purpose Mean Estimation over R
conditions:
and optimally robust corruption must achieve the error rate from Definition 2.5 (stated formally Proposition 2.6), and are thus neighborhood optimal as a corollary.
For all D' E (D), with probability 1 5 over the n i.idd. samples from D', we have j p S en,
Proposition 2.6. Let j be an arbitrary estimator that, when given 8 > 0 and a set of n n-corrupted samples from any distribution D with mean and variance o², outputs a mean estimate satisfying
With probability 1 8 over the n i.i.d. samples from D, j uD! (D).
Neighborhood Pareto ounds essentially play the role of "lower bounds" in an optimality definition, and the strength of the result depends crucially on the choice of the neigh- borhood function N under consideration. As a basic ob- servation, the strength of this definition is monotonic in the size of the neighborhoods returned by N: if an error function e is a neighborhood Pareto bound for neighbor- hood function N, then for any neighborhood function N' such that N(D) C (DD for every D E Pi. is also a neighborhood Pareto bound for N'. Thus, the smaller each neighborhood is, the stronger the neighborhood Pareto bound is.
log n
11
S
with probability at least over the randomness of the (uncorrupted) samples.
Then, the same estimator is, input n ii.d. samples drawn from distribution D with finite mean, will output an esti- mate with error upper bounded by (()),(DD) (as defined in Definition 2.5) with probubility at least 1 - ô.
The precondition of Proposition 2.6 is satisfied by a variant of Theorem 2.2-with slightly smaller failure probability- which holds for Estimator 1. Thus the neighborhood op- timality of Estimator follows corollary of Proposi- tion 2.6.
Finally, we define neighborhood optimality.
Definition 5.2 ((K, Neighbbboodd Optimal Estima- tors (Dang et al., 2023)). Let k > 1 be a multiplicative loss factor in estimation error, and 7 > 1 be a multiplicative loss factor in sample complexity.
To see the intuition behind Proposition 2.6, recall the defini- tion of the error rate function e,,s from Definition 2.5. The definition constructs a distribution D from D, by removing the tails of D with probability mass Ollog p/n),
Given the parameters K, > 1. sample complexity n, fail- ure probability 5 and neighborhood function N,,6, mean estimator á is (xs, -eighhbooodd optimal with respect to Nn,5 if there exists error function 6,,6 (D) such that min(<n/r.s( D), c,, (D)) is neighborhood Pareto bound!, and f gives estimation error at most K (D) with proba- bility at least 1 - 5 when taking n i.i.d. samples from any distribution D E P1.
and the error function 6.,8 (., = o log 1 + IH4 Pal is the sub-Gaussian error for distribution D plus the mean difference between D and D Thus, when given samples from D, one could view them as corrupted samples from D where roughly O[log //n)) fraction of the samples are corrupted. A sub- Gaussian and robust estimator would thus achieve good error with respect to the mean of D and by triangle inequality, also with respect to the mean of D.
Dang et al. (2023) showed that the error function Ga, from Definition 2.5 yields a neighborhood Pareto bound 6n,5 cn, (D)) for an appropriate choice of neighborhood function, for some constants K, > 1. Their choice of neighborhood function Nn.5 is technical; we state it in Appendix C, and refer the reader to their paper for the justification. Based on this result, they also showed that median-of -e-ns indeed achieves error ((G,,s) from Definition 2.5 and hence is neighborhood optimal by Defi- nition 5.2. Dang et al. (2023) further raised the immediate question of whether other more-modern estimators, such as Lee and Valiant's 's Estimator 1, can also achieve such estimation error.
min(en/=,5
We present proofs of the above statements in Appendix C. For completeness, we also provide a summary of Dang et al. (2023)'s results. We again refer the reader to their paper for more in-depth discussion on the intricacies of the neighborhood optimality notion.
6. Infinite Variance Distributions
In this section, we extend Lee and Valiant's analysis of Estimator to more heavy-tailed distributions. Instead of Fact 1.1, where the performance of the estimator is charac- terized in terms of the variance of the distribution D, we instead ask if we can characterize the performance of the estimator on distributions that may not have a finite variance but instead only have finite 2h moment for some < < <= 2.
We show a general affirmative answer, that in fact, all estima- tors that are (up to constants) simultaneously uub-Guussian
While it is intuitive to expect that an error function decreases in n. it might not be true in general. Indeed, the function used by Dang et al. (2023) (Definition 2.5) is not necessarily monotonic. This is the reason for the "min" in the neighborhood Pareto bound requirement.
We restate our main theorem for this section, which matches
7

---

All- All-Purpose Mean Estimation over R
the lower bound of Devroye al. (2016) up to constants. Theorem 2.4. Given any distribution D with mean and n moment Ms for some E 2), let X be a set of nt i..d samples from D. Then, with probability at least 1 --0 over the randonness of X, Estimator on input ó and X will output an estimate ji with error most
follows:
n
(, Σ
(p x; min( 1)))
Va (x, (), =
min( log
3n 5
log 1
1-
j - 1l (M,) 10...-1165 (1+ ((1)
3. Output: á from the previous step.
This reformulation has the advantage that, for any fixed pair (ft â). any linear combination of the 1 and ta functions is of independent terms. The concentration of Estima- tor I is then reduced to proving Chernoff bounds for these linear combinations.
where C₂ = =-( Here, the o(1) term tends to as 1og + (0, 0), a manner independent of D and independent of
At a high level, our analysis is a generalization of Lee and Valiant's analysis to the low-moment setting, which allows us to prove guarantee that gracefully reduces to their main result (Fact 1.1, with the sharp constant of /2) - 2. Furthermore, our value of cz is smaller than the corresponding multiplicative constant in the analysis of median of-mians means by Bubeck et al. (2012), across all values of = E (1,2).
This reformulation and reduction is independent the finite variance assumption, and therefore also applicable to the low moment setting that our work analyzes.
6.2. Proving Chernoff bounds over large distribution classes
Even in the finite variance setting. proving a Chernoff bound that applies for all distributions D with mean 0 and variance is daunting, given how large the distribution class is com- pared to standard concentration bounds. Lee and Valiant showed that the worst-case Chernoff bound (for linear com- binations of the d-equations from Definition 6. can in fact be viewed as a max-min linear programming game.
Here we give an overview of our analysis.
Without loss of generality, from the shift-and-seale equivari- ance of Estimator 1, we assume the underlying distribution has mean 0 and =th moment M, 1. The goal is prove tailored Chernoff bounds for this estimator to show its con- centration. Lee and Valiant's 's analysis in the finite variance setting provides two useful techniques to address obstacles described in the following subsections.
For simplicity, let us illustrate this by sketching the analysis of the Chernoff bound of hypothetical linear estimator that is sum of independent terms: f({x1, ... ....),...,,,,)
1 Σ, f(x;;, for some fixed function ʃ RR - lR. Proving Chernoff bound is equivalent to upper bounding the mo- ment generating function of the estimator f. and choosing the "Chernoff parameter" t accordingly. Thus, it suffices to upper bound the objective of the following max-min game, where the max player chooses any mean-O variance-1 dis- tribution D-represented by variables (Px) denoting the probability mass at (ignoring probability formalism is- sues with non-discrete distributions) and the min player chooses the Chernoff parameter t. Using the moment gener- ating function as the objective function, we have
6.1. Estimator is a sum of dependent terms
Estimator is a sum of dependent terms, due to the in- fluence parameter a computed in Step 2 involving the samples. This makes proving Chernoff bounds tricky, given that moment generating functions multiply only for sums of independent terms. Lee and Valiant's approach is reduce (via a Lipschitz argument) to analyzing the case where the preliminary estimate from Step is taken to be exactly equal to the true mean = 0, and crucially reformulate Estimator as "2-parameter v--estimator".
Definition 6.1 (Lee & Valiant 2022). Consider Estimator but with Step replaced with "x 0". The estimator can be equivalently expressed as follows:
min; Σx ((())
max
such that
Σ nn Ps
x = 0
(1)
Σ Ps x²
1. Input: Failure probability 8, independent samples X 21....,2.
where
Ps 2 0
By using minimax duality and linear programming duality, the game can then be rewritten into a pure minimization program with the same optimum, where the dual variables
2. Solve for the (unique) pair (ft, à) satisfying uh = and Vha = O. where the functions wha vha are defined
8

---

All-Purpose Mean Estimation over R
U, M, V correspond to the 3 respective constraints in the program in (1).
symmetrically the minimum sample), multiplied by factor of y since that is the scale that the Central Limit Theo- rem holds at. Under the finite variance assumption, we can use a (slightly refined) Chebyshev's s inequality and a stan- dard Chernoff bound to upper bound the magnitude of the maximum sample with high probability. See the complete calculations in Appendix E.
min;
MVY U +
such that
for all x E IR, Vx + Mx U 2 el)(()
(2)
thus suffices to choose dual variables U, M, V and an appropriate Chernoff parameter to certify an upper bound on the optimum.
A Acknowledgments
We modify this approach from Lee & Valiant (2022) by relying on a 2n moment bound instead of a variance bound. The key observation is that the 2hhh moment bound may be expressed as a linear constraint in the above program, replacing Σx p2 = 1 with Σ, Pz | = 1. The technical challenge from here is to provide a feasible dual solution and choose Chernoff parameter bounds, including that the guarantees converge to Fact 1.1 as + 2. We show our complete proof in Appendix D.
The work of Jasper C.H. Lee was done in part while he was at UW Madison, supported by NSF Medium Award CCF- 2107079. He also thanks Stanislav Minsker for discussions on the asymptotic normality result.
The work of Walter McKelvie was partly supported by the National Science Foundation Graduate Research Fellowship Program under Grant No. 2140743.
to satisfy the desired
Maoyuan Song and Paul Valiant are partially supported by NSF award CCF-2127806 and by Office of Naval Research award N000142412695.
7. Asymptotic Normality
In this section, we show that under the standard finite vari- ance assumption, the estimator of Lee and Valiant asymp- totically normal and efficient. Specifically, we prove that if we fix the input parameter ó and take the number of samples + 0C, the estimator converges to the sample mean in probability, which by the Central Limit Theorem implies asymptotic normality and efficiency.
Maoyuan Song is partially supported by NSF award CCF. 2228814.
Impact Statement
This work studies a fundamental statistical problem that is broadly applicable to a wide variety of domains, As such, does not directly raise any societal or ethical concerns that warrant special consideration.
This result contrasts with mffian-of-means, means, which, under the slightly stronger 2 moment assumption for any 0, is asymptotically normal yet inefficient (Minsker, 2023)- the asymptotic distribution of /Tii/MM is N(u, (T/2))²² instead of the desired N N(, o²).
References
Alon, N., Matias, Y., and Szegedy, M. The space complex- ity of approximating the frequency moments. J. Com- put. Syst. Sci, 58(1):37-1147, 1999.
Theorem 2.8. Let D be a distribution with mean p. and variance o².
Let js denote Estimator 1 on input parameter and n i. samples from D. Also let Xn denote the sample mean. Then, fixing ō and D and taking > DC, we have
Asi, H. and Duchi, J. C. Near instance-optimaaliyy in differ- ential privacy. arXiv preprint arXiv:2005.106300 2020a.
Asi, H. and Duchi, J. C. Instance-optimality in differential privacy via approximate inverse sensitivity mechanisms. Advances in neural information processing systems, 33: 14106-14117, 2020b.
Vnp Bs VnX,
that is, lyni- Siij--Vx,, /x ml 2. 0, that vnj converges to VnX, in probability.
As a corollary, by the Central Limit Theorem, we have
Bubeck, S., Cesa-Bianchi, N., and Lugosi, G. Bandits with heavy tail. arXiv preprint 2tt.: 2012.
v) 1)) $ N - (0. That is, ji is asymptotically normal and efficient.
Catoni, O. Challenging the empirical mean and empirical variance: deviation study. Ann. I. H. Poincaré -PR, 48 (4): (4):1148-1185 2012.
The proof is relatively straightforward. The key idea is that Estimator 1 differs from the sample mean by removing Olog }) weighted samples, so we might as well bound the difference by O(log })) times the maximum sample (and
Dang, T., Lee, J. C. H., Song, M., and Valiant, P. Optimality in mean estimation: Beyond worst-case, beyond sub- gaussian, and beyond + a moments. In shirty-seventh

---

All-Purpose Mean Estimation over R
Conference on Neural Information Processing Systems, 2023.
Nemirovsky, A. and Yudin, D. Problem Complexity and Method Efficiency in Optimization. Wiley, 1983.
Depersin, J. and Lecué, G. Robust sub- -abb-gausiinn estimation of mean vector in nearly linear time. The Annals of Statistics, 50(1):511-555)) 2022.
Oliveira, R. L., Orenstein, P., and Rico, Z. Finite- sample properties of the trimmed mean, arXiv preprint #rXiv:250103364 2025.
Devroye, I.., Lerasle, M., Lugosi, G., and Oliveira, R. I. Sub- Gaussian mean estimators. Ann, Stat, 44(6))2695-2725, 2016.
Tukey, J. W. A survey of sampling from contaminated distributions. Contributions to probability and statistics, pp. 448-485, 1960.
Diakonikolas, and Kane, M. Algorithmic high- dimensional robust statistics. Cambridge university press, 2023.
Diakonikolas, I,, Kane, D. M., and Pensia, A. Outlier bust mean estimation with subgaussian rates via stability. Advances in Neural Information Processing Systems, 33: 1830-1840, 2020.
Gobet, E., Lerasle, M., and Métivier, D. Mean estimation for randomized quasi monte carlo method. Hal preprint hal-03631879v2, 2022.
Hopkins, S., Li, J., and Zhang, F. Robust and heavy-tailed mean estimation made simple, via regret minimization. Advances in Neural Information Processing Systems, 33: 11902-11912, 2020.
Huang, Z., Liang, Y., and Yi, K. Instance-optimal mean estimation under differential privacy. Advances in Neural Information Processing Systems, 34:25993-26004, 2021.
Huber, P. J. Robust estimation location parameter. Breakthroughs in statistics: Methodology and distribu- fion, pp. 492-518. Springer, 1992.
Jerrum, M. R., Valiant, I.. G., and Vazirani, V. V. Random generation of combinatorial structures from uniform distribution. Theor. Comput. Sci, 43:169-1888 1986.
Laforgue. P., Staerman, G., and Clémençon, S. General- ization bounds in the presence of outliers: median-of- means study, 2021.
Lee, J. C. and Valiant, P. Optimal sub-Gaussian mean estimation in E. In 2021 IEEE 62nd Annual Symposium Foundations of Computer Science (FOCS), pp. 672- 683. IEEE, 2022.
Lugosi, G. and Mendelson, S. Robust multivariate mean estimation: The optimality of trimmed mean. The Annals of Statistics, 49(1):393 410, 2021.
Minsker, S. U-statistics of growing order and sub- gaussian mean estimators with sharp constants. arXiv preprint arXiv:2202. 1842, 2023.
10

---

All- All-Purpose Mean Estimation over R
A. Remaining Proofs of Section 4
In Section 4, we discussed the intuition behind our main results, Theorem 2.2 and 2.3, At a high level, our proof strategy for both main theorems uses the triangle inequality bound estimation error introduced by adversarial corruption as the sum of two parts, one from changing the influence parameter from a, and one from the adversary arbitrarily corrupting the samples. We provide formal proofs for relevant lemmas and propositions in this section, and restate the main theorems for completeness:
Theorem 2.2. Given any distribution D with mean μ and variance a², parameters n, n, > O, let X be set of n-corrupted samples from D.
Suppose both log, 3. and 8 are bounded by some small universal constant, and suppose 5 24n log 3. Then, with probability at least å over the sampling process, Estimator 1 on input 6 and X will output an estimate ji with error at most
10 10 ((V2+ log n + 222
Theorem 2.3. Given any distribution D with mean and variance o², parameters n, 0, > 0, let X be a set of n y-corrupted samples from D.
Suppose both log 2 and ō are bounded by some small universal constant, and suppose v log log 3 = 3 log 8 + 3rm. Then, with probability at least 8' over the sampling process, Estimator on input and X will outpul an estimate j with error at most
log 3.- Let 8' be so that
log l/ - --lls0 (v22+((1))
+ (135 o(1)))
n
Throughout the proofs, we will compare and make use of different values of "a", computed from either corrupted or uncorrupted data, and computed from different choices of parameters in the equation defining a. Here, we give a more general definition of notation (generalizing Definition 4.1) that will be using.
Definition A.1. Let X {a;} be a of clean samples, and let X {ä,} } be the corresponding set n-corrupted samples. Denote by 0g the "influence parameter" solved from the corresponding condition involving the clean samples, so satisfy version of Step 2 of Estimator but with modified right hand side (glog pn instead of log }):
Σ min 1) log pn
and denote by as the "influence parameter" solved instead from the corresponding condition involving the corrupted samples:
Σ min log + pn
Theorem 2.3 refers to failure probability 8', so parts of the analysis will involve the notations as and c for example.
We start with showing the crucial preliminary Lemma A.2, which bounds the value of å allowing us approximate it using different influence parameters the clean data, with assumption of the corrupted data:
Lemma A.2 (Restatement of Lemma 4.2 under the notation of Definition A.1), Consider an arbitrary set of samples and new sample set X corruppeed from X. Consider also an arbitrary input parameter 6. Using à to denote the influence parameter of Estimator inputs (5, X), i.e. 08go in Definition A.I, we have
088, 2n S ā S 018,2n
Proof. Let the clean samples be X {xx) and the corrupted samples be X (7.).

---

All-Purpose Mean Estimation over R
To prove the first inequality, suppose for the sake of contradiction that â 266 Then,
Σ min(a 1)
Σ min min(da
(da; 1)
Σ
min(ā.7.
f: cormupted
log 6
2nm +
Σ
min(ā 1)
(since < (68
a: corrupted
1
log 0
ryn
(since the sum has ynn elements, each at most
1
log 8
which is a contradiction.
The second inequality follows similarly. Suppose for the sake of contradiction that â 018,21 Then,
Σ min(āā?
Σ min min(āx..1) 1)
minn(a., 1) min(āa?. 1)
a: corrupted
log
+ +2m
Σ
mmin(a.?. 1) min(āx? 1)1
(since (6622)
comrppee
M
log
+ Tyn
(since the sum has rnn elements, each at most
log
which is a contradiction.
We fact generalize the above lemma slightly for use in the proof of Theorem 2.3, which can be proven from Lemma A.2 by reparameterizing 8.
Corollary A.3. For any set of clean samples X and the corresponding n-corrupted samples X, and for any constant 2, we have ('s(ce2)) & Ü'8,.n S (.,(c-2)m
The proof structure of Theorem 2.2 and 2.3 are essentially identical. We present the proof of Theorem 2.3 first.
For the rest of the appendix, we will assume that the uncorrupted data distribution has mean 0 and variance without loss of generality, due the shift-and-scale equivariance Estimator 1.
A.1. Bounding the Error due to Changing the Influence Parameter
We present the following proposition upper bounding the error incurred on Estimator by using influence parameter = 0gg.,, instead of a == atg on the clean samples. That is, we compute à on the corrupted samples, but analyze its effect on the clean samples.
For the following section, recall assumption that the underlying distribution has mean 0 and variance 1.
Proposition A.4. Suppose both 3 and 8' are bounded by some small universal constant. Let be the influence parameter computed from the clean samples with robustness level Elog 4. namely == parameter computed from the corrupted samples with robustness level ţlog gr + 3mm, namely, â == ög 3ay- Then with probability at least &8, the mean estimate using a on the clean samples differs from the mean estimate using ā on the clean samples by at most 125.5 //1 i.e.
Let ā be the influence
Σ min 1) - Σ min(aa;, 1) < 125.5nn/7
(3)
12

---

All-Purpose Mean Estimation over R
To provide some intuition towards our proof strategy for Proposition A.4, first notice that bound the left hand side via Cauchy-Schwand
Σ x
(min(āx?, 1) min(aaf; 1))²
This turns out to be insufficient; instead bound (3) by defining the set S of indices where min(āx;. 1) * min(ax,, 1), and restrict the range of both sums in (3) to the range i E S, since doing only discards zero terms and does not change the bound
sum. Thus we instead have the
Σ VES
Σ FES
(min(āx;, 1) min(ax3, 1))²
The bound on the second parenthetical makes crucial use of the comparison and a provided by Corollary A.3. The first parenthetical is an empirical variance, but the restriction i S means that |zy| cannot be large; we thus use Bernstein's inequality bound this S-truncated empirical second moment, in terms of a lower bound a, which prove next.
To show our lower bound on o, we first calculate the following straightforward relations between the empirical and population quantiles.
Throughout this section, we denote by (D) the q (true) quantile of D, i... P(D < Q₂( =
Lemma A.5. Suppose both log and 8' are bounded by some small universal constant. Denote eı 0.277 4. and a log 3.). ). Let constant 0o = 102.907. Then the empirical quantile of x; is at most 01/k//2 (D) with probability least 8'.
Proof. For the 1 empirical quantile of z; to be greater than Q Q1 (D), there has to be more than kn samples greater than Q1-x/ea (D). Thus, it suffices prove that Ki E [n] 2 Q1-x/ca (D) with probability at most 5
Denote Z; ;= 2=:2Q:-m/=a.0 (D)) Then Z = Hi E [m] 2 Qi-n/ea (D) = Σ.= Z₁ We denote by p = the probability that individual is in this set; and thus E []] pn. Since each Z; is coin flip of probability p, we further have that Var = p(1 p).
By multiplicative Chernoff,
cc--1 pn
Z 2 capm] S
6g
exp (C2 02 log 02 pm)
C1(02 02 log C2)
exp
log
S exp
(-1.01)log 8'
by choice of e₁ and 02
A exp
log
since 1.01log 2 log &
for suff. small
8' 8
as desired.
By symmetry, we have the following corollary as well:
Corollary A.6. The empirical quantile of x; is at least Qn/eog (D) with probability at least 1 36. Lemma A.7. Let Dirimmmed denote "trimmed" version of D: namely, D conditioned on lying [Qw/ez (D), Q1)
Then E D?
Rrimmeal < [02 2x)3
13

---

All-Purpose Mean Estimation over R
Proof. Denote by 1 unttrimmed (a) the indicator that returns if xr [Qx/ez Q1-x/ez (D)) and otherwise. Then
observe that D Drrimmmed 02 2n untrimmedd) Thus
21 )
E B
E
(D.
1 (nntrimmed)
C2
2k
untrimmedd
02
2x)²
2
EEDA
C2
2x)²
o
(c2 - 2x)²
as desired.
Lemma A.8. Suppose both 2 and 8' are bounded by some small universal constant. Let (Irrimmed)) denote the sample Iy after trimming, namely: let (Terimmed); = 24 if E. Q1x/// (D)], and (Itrsmmed)s = 0 otherwise. Let
constant 251.099. Then (3trimmed) <
(cs+1)e [cz 22)22 n with probubility at least 1 38.
Proof. First notice that if we replace any trimmed z; with random sample according to Derimmeds then the sum (Ztrimmed) can only increase. Thus, prove the claim, it suffices to bound the sum of i.i.d. samples from Dtrimmed: With an abuse of notation, we let {Ftrimmedd) Jiga denote set of such samples.
Also notice that by our choice of C3, we have, crucially, (6 20020
301
2 1.01.
We start by bounding Qu/ez (D) and Q1-x/cz (D). Since assume D) has mean 0 and variance 1, by Chebyshev's T
inequality, |aD] 2 x. which implies that Qx/ez 2 - and Q1-x/ea S v 2 k for all i.
a result, (Itrimmed) S 02
Then,
Var((Ztrimmedd))
< [ ((trrmmeed)
02 [T
K o
by Lemma A.7
k(02 2x)²
Thus, by Bernstein's 's inequality,
(Cs + 1)c2n
P
( (Itrsmmed))
(c2 2x)²
C3
P
((trimmed)))
n
(02 - 2x))
(c2 2x)²
1
c32
< P
n (Fttrimmed)) E - (Dtrimmedd))
(02 2
2xJ
< 2xxp
Varl (atrimmed))
20g 3x0 - 2c3
of
(0g 2x)
< exxp
2r3 klez
20ar
2x)²
3n 3n 2N)
14

---

8 All- All-Purpose Mean Estimation over R
3czerm
2xxp
(6 + 2c3 (c2 2x)2
3e3nx
$ exp
(6 203)
3c1 c
2exp(
log
by definition of
(6 20z 02
s 2 2eepp--1.011 -1.01log
by choice of C3
8
8
s 2xxp( log 8
since 1.01log 5 8
log for suff. small 6'
8
as desired.
Combining Lemma A.5, Corollary A.6, and Lemma A.8, we have the following corollary:
Corollary A.9. Suppose there is sufficiently small constant that upper bounds 8'. Let Sen denote the set of indices i s.t.
x² is not the top x (empirical) quantile. Then Eissen x?
(cs+1)e with probability least - -8'.
(o2 2x0
We are now ready to present lower bound on a C.sr.0, before proving Proposition A.4.
Lemma A.10. Suppose both log + and 8' are bounded by some small universal constant. Then a 0,g00 0.000214 & with probability at least 8
Proof. Recall that by definition of a.
log
Σ min(ax?, 1)
3
Σ
min
Σ
min(ax},
(:ss not top quantile
t:? top quantile
Σ
0.e +
2
(:2 in top quantile
iu? top quantile
Σ
0x + Kn
ésr not top quantile
Σ
az + cılog g
Gor not in the top quantile
Rearranging, this is equivalent to
1
log
1
<
Σ
02
3
8
d:f in the quantile
By Corollary A.9, with probability at least
48'
(ca + 1)c²
(C3 + 1)c2 (c2 2)2
Σ
(c2 2x)²
f not in the top a quantile
Which implies that 2 -x)
(c- (0--2)² Loog $ >
0.000214 1 with probability at least - 88.
(cs+1)e
15

---

All-Purpose Mean Estimation over R
Proof of Proposition A.4. First, notice that for all such that |x:|
the corresponding term in the sum in the
the left hand side in left hand side becomes Thus, using the notation Σ denote summing over elements | S v
the guarantee of Proposition A.4 is equal to
Σ 2, min(āa; 1) Σ 24 min(aaf, 1)
Then, rearranging the sums, we have
Ty min((azi 1)
Σ min(axf 1)
ay (min(áxz 1) min(ax;, 1))
Σ x
(min(āx7;1) 1) - min(ax?,1))
by Cauchy-Sehwarr Schwarz
for which bound the two terms separately.
To bound the first term, since we sum over only those terms where |2r]| S V for all i, and by Lemma A.10 2 0.0002141gg log z with probability 1 o we have that ur S 4672n for all i. Since X has mean 0 and variance 1, we know Thus, by Bernstein's 's inequality,
Tox
that E|,;]| E[X²] and Var [x Bla
4672n
IE [x S
4672n log 37
log
P
Σ of 2 S
3150n
=
1 12 3149
11
<
< P
1
Σ
1
-[
2 3149
n1
S
3149ºn
S 2 2exp
9344
n
+ 9344 3149
n /3
log f
log x
< 2exp
1.011og 8
8 (-log log 8'
8
< 2exp
since 1.01log 8 > log 8
for suff. small 5'
8'
In other words, conditioning Lemma A. holding, with probability at least 1 - 28, Σ 1 < 3150n.
To bound the second term, note that
Σ (min(āx), 1) min(a27, 1))
(min(āx;, 1) min(aa 1))² < (min( (āa 1) min(aa;, 1))
since == āg ,3 2 as a = ag.o o by Corollary A.3, and "a" is monotonic in the n argument, and thus 5 min min(ā.? 1) min 1) < 1 for all i.
To further upper bound the last quantity, we have
Σ (min(āz?11 1) min(oz;, 1)) Σ min(áa 1)-) Σ min(2 1)
16

---

All-Purpose Mean Estimation over R
min "n 1)
Σ
min(as 002;:
by Corollary A.3 and by definition of
1
1
log
5mm
log
8'
3
5mm
Finally, summarizing, we have that with probability at least g
Σ S
x
Σ (min(ōxf, 1) - min(a2,, 1))2
v 3150m 5xm
ny 115550m
125.5mv/1
as desired.
A.2. Bounding the Error due to Corrupting the Samples
We now present the following proposition upper bounding the error incurred on Estimator 1 by the arbitrary corruption of the adversary on the clean samples, while fixing ā := c .4 as the influence parameter.
We again assume that the uncorrupted distribution has mean and variance 1.
Proposition A.11. Suppose both log 3 and 8' are bounded by some small universal constant. Let â be the influence parameter computed from the corrupted samples with robustness level Elog 5 + 3mm, namely, ā == 0g 3n Then with probability least 8 the mean estimate using à on the clean samples differs from the mean estimate using à on the corrupted samples by most 8.586 RT i.e.,
Σ a, - min(aa,, 1)) - Exi(1
min(ān?, =ii(t=in( 1)) 8.586n.77
xe
To provide some intuition towards our proof strategy for Proposition A. consider the adversary's 's arbitrary corruption, which can be interpreted piece-wise wise as moving each clean sample that the adversary wishes corrupt to a new location. Since the influence parameter controls the contribution of each sample to the mean estimate, based on how far from the mean it is, moving sample too far from the mean moving the sample too close to the mean will both incur very little error. The question then, is, what is the maximum estimation error the adversary can incur by corrupting single sample?
Fixing the value of à as in the statement of Proposition A.11, we can upper bound the maximum magnitude of the expression 1 E; (1 - min(ázz) 1)) by calculus, which is O(1 ((/vV). We will show a lower bound o, specifically that à 2 R(1), and then conclude that the maximum total error possible by corrupting yp samples is at most mm ((1/ = O as desired.
We similar strategy in the proof of Proposition A.4, using quantile statistics well Corollary A.3 obtain desired lower bound on a, before proving Proposition A.11 in Appendix A.
Lemma A.12. Suppose both log 1. and 8' are bounded by some small universal constant. Denote ci 3. and
(1 log $). Let 02 : 55.252. Then the 1 - empirical quantile of x; is at most Q1-e/ca (D) with probability at least
1 8
Proof. For the empirical quantile of xz be greater than Q1 (D), there has be more than an samples greater than Q1-x/ea (D). Thus, it suffices to prove that [i E [n] x; 2 Q1 (D)) 2 en with probability at most 1/ 8'.
[D) = Σズ Z,. Obviously E[Z] kn/e2. Denote Denote Z; 1,:2Q -n/ (D)- Then Z : Ki [m] æ. Q Q1_x/02
p: = E = s/c2. Then Var [Z,] = p(1 p).
17

---

All-Purpose Mean Estimation over R
By multiplicative Chernoff,
e pa
P 2 62pm) S
22
2
=exp
((02 - 02 log C2 pm)
(1 (1
C2 log 02)
exp
(log
C2
(-1.01)(10g ))
S exp
by choice of C1, C2
32
1 5'
32 for suff. small 8'
$ cxp
llog
8/
=
32
since 1.01log
8r 2 log 8
as desired.
By symmetry, we have the following corollary as well: x; is at least Qujer (D) with probability at least 32 Lemma A.14. Let Derimmed denote the trimmed version of D conditioned on lying in [Qn/egg (D), Q1 Q1 (D). Then
Corollary A.13. The & empirical quantile of;;
[rimmedd [eg (Tx-2xx)T
Proof. Denote by 1 (uxtrimmed(() the indicator measure that maps z 1 (D)sx501-=///)())) the indicator of whether x is untrimmed. Then observe that Dirimmed
02 2kc (D
untrimmed). Thus
27
E trimmeed
E
(D.
Lnntrimmed)
C2
2k
c
D
untrimmedd
C2 2x)²
2
02 2x)²
c2
C2 - 2x)
desired.
Lemma A.15. Suppose both log dh sample 2i after trimming, such (Fersmmed)s = F4 if x; [Qxje, (D), Q1-n/e, (D)), and (Ferimmed); = otherwise. n
and are bounded by some small universal constant. Let (Itrimmeed) denote the
Denote C3 = 114.532. Then (3trimmed)
< 1ee (02 2xy n with probability at least 28.
Proof. First notice that if we replace any trimmed n; with random sample according to Dtrimmeds then the sum E, (Ztrimeed)) can only increase. Thus, to prove the claim, it suffices to bound the sum of n i.i.d. samples from Derimmed: With an abuse of notation, we let (Ierimmead) Jisa denote a set of such samples.
Also notice that by our choice of c3, we have, crucially, (6-2ca)es
3c50:
2 1.01.
We start by bounding Qn/ez (D) and Q 1 (D). Since we assume D has mean 0 and variance 1, by Chebyshev's inequality, P [|D] 2 v 22 x which implies Qu/oz 2 - and Q1-x/ea I v As result, (Dtrimmed)} for all
o2
Then.
Var Varl(Xerimmed) S E ( ((Terimmed)) 2)
C2 E[(
18

---

All- All-Purpose Mean Estimation over R
c2
by Lemma A.14
R(C2- 2x)²
Thus, by Bernstein's 's inequality,
(C3 + 1)22n
IP
(Itrimmed)i))
(02 2x)²
C2
C3O2
IP
(Etrimmeed)))
(02 2x)²
(c2 22))
C3
< IP
(Etrimmed)))
Bl( E[((Atrimmed))))
(02 - 2x)}
of (22 2n)
< exp
2 Varl (arr(aTrring (trimmed) ))
200
3x(r2 - 2x)
$ expp
[0g
2x²
2n M(
2
+
2x)2
3nle2 2n)2
3c3 3eJeznk
exp
(6 2c3)
(c2 -2x)²
303nK
< 2exp
(6 20g)02
3c3a1
2exp(
(log x)
by definition of
(6 + 203)02
1
< 2exp( -1.01 ()
by choice of C3
32 for suff. small 8
< 22exp(-(1og
since 1.01log 8' 2 log 8'
8
2
8¹
32
as desired.
Combining Lemma A. 12 Corollary A.13, and Lemma A.15, we have the following corollary:
Corollary A.16. Suppose both log and 8' are bounded by some small universal constant. Let Scn denote the set of indices i s.t. xt is not in the top k. (empirical) quantile. Then Eieser
[es+1)e (02 2x)2
n with probability at least 88.
Proof of Proposition A.II. We start by consider a single sample ã; which is corrupted such that x; A 5,. Fixing all other samples, we solve for the maximum (signed) error, or equivalently mean shift, that the adversary can incur by arbitrarily corrupting this sample v; only.
Recall that the estimator (fixing influence parameter :- .8,3)) defined as E, x1 min 1)). Taking the derivative with respect 2,, restricted to the region in which min( (āz², 1) āx,, have
i 0r,
1
p 1 3 =
Since 2 0, a local maximum occurs at x = /35 The corresponding maximum contribution of this single term is 2 is easy to verify that this local maximum is in fact the global maximum based on taking the minimization between a.? and 1. Symmetrically, the minimal contribution of single term 3/38
3/35'
19

---

All-Purpose Mean Estimation over R
Thus, the maximum error the adversary can incur by corrupting single term is 3/36 The maximum error the adversary
incur by corrupting yyn terms is
4nm
3/36
To upper bound
4nm need to lower bound ä. Towards this, notice that á az',g .n by Corollary A.3, which by definition
3v3a'
satisfies:
mM log
ass .n 1)
min(ãar
by Corollary A.3
Σ
min(áx,, 1) +
Σ
min(āx,, 1)
d:n] not top quantile
din in the top quantile
Σ
dx +
Σ
im?? not in the top quantile
i:x? in the top quantile
Σ
dia + Km
i:r? not in the top quantile
1
Σ
oa? + 1+,gl0
log
i:a not top quantile
Rearranging, this equivalent
mp S
Σ
a
i not in top quantile
By Corollary A.16, with probability at least 1 8"
Σ
iun? top quantile
(c3 + 1)cg
(02 2x)²
(C3 + 1)c²
(C2 - 2)2 n
Thus,
(cs + 1)03
mM S
Σ
O. <
(cy 2) nā
tur the quantile
which is equivalent
(c2 2)
17 0.00804m
(03 + 1)c²"
Thus, we have
Σ (1 min(2 1))
Σ 21 min 1))
5
4pm
4mn
8.5866 /1
3v3ā
3v0.02412g
desired.
A.3. Proof of Theorem 2.3
Equipped with Propositions A.4 and A.1,, we are ready formally prove Theorem 2.3.
20

---

All-Purpose Mean Estimation over R
Proof of Theorem 2.3. We will start by assuming that the underlying distribution has mean 0 and variance (by the shift- and-scale equivariance of Estimator 1); and furthermore, that the initial estimate computed in Step is exactly the true mean of O. At the end of this proof, we will show that the assumption introduces only negligible amount of mean estimation eπrоr.
Fixing the initial estimate x = 0, then, Estimator on input the clean samples X and confidence parameter computes the influence parameter a := 01gr00- and returns an estimate Metean.a == # 2. z min(cx7 1)). As part of their analysis, Lee Valiant (2022) showed that
log 8 |aciean,al S (V2 +V2++ (
71
with probability least 1 - 8'. We note that the above guarantee can in fact be slightly strengthened, so that the failure probability becomes 8'/ /1, at the expense of slightly increased o(1) by more than constant multiplicative factor.
Now we consider changing the "a" value from to á computed from the corrupted samples, but applying these a influence parameters on the same clean sample set, and bound the difference in the resulting mean estimates. Specifically, consider 3q. which is the influence parameter computed with robustness level glog Φ² + 3rm from the corrupted samples. Let the mean estimate of using ā on the clean samples be Patean, E, 2; min māx, 1)). Then, by Proposition A.4, with probability at least o' have
:= ,.g.
jedeaan,
Pelean,
Σ 2; min(āx3, 1)
Σ min(ax? 1) 125.5.77
Next we consider the effect of replacing the effect of corruption, but after fixing the influence parameter to be a. Specifically, define Acorrupt.d to be the mean estimate of the corrupted samples using a, namely 1 E, #.( min(ā.? 1)). Then, by Proposition A.11, with probability at least 1 - 1 8', we have
8
Meorruppt 5 ieltean. al
1
Σ
54(1 min(
E
5.((1 miinmmmn(af 1)) < 8.586
By union bound and triangle inequality, summing over all three error terms, we have that with prohability at least Peorrupt,a satisfies
15
16
log 134.086 S (V2 o(1))
log + 135
|eooruptta S (V2 + o(1))
Finally, observe that on meea---variannee distribution, and with 77-ooruption, the only difference between Acorrupt, and the output ji Estimator (on input as stated the theorem statement) lies in Pcorrapt,a assuming that the initial mean estimate x was the true mean of O. On the other hand, á (Estimator I) uses an estimator (for example, median-of-means) compute
We use the following fact shown in Lee & Valiant (2022) about the structural properties of Estimator 1, to analyze the effect of the assumption:
Fact A.17 (Lee & Valiant 2022). Let X be fixed set of samples of size and let 8 > 0 be confidence parameter. Let f ((X,6) 6) denote the output of Estimator of LV22. Then Estimator is affine invariant, i.e.:
plax + b,8) af(X,6) +
Additionally, let (X, 8) denote the output of Estimator I but where Step I is omitted, and the initial estimate instead considered input. Then:
0 (X,8)
log 1
O
0x
21

---

All-Purpose Mean Estimation over R
We also the following fact/assumption the robustness of the initial estimate against adversarial corruption: it is folklore result that median-of-ment satisfies this. proof of Fact A.18 is given in Appendix F for completeness, since are unaware of literature explicitly writing down this proof. As discussed in Estimator I, are free to use other estimators to compute as long as Fact A. 1.18 holds analogously.
Fact A.18 (Folktore). For any distribution D with mean μ and standard deviation o, let X be a set of n-corrupted samples from D. The cordian-of-means estimate K. from grouping samples into Ollog 5 + mm) buckets, on input X, satisfies
log + 17
1k - 14 2 O
o
- d
n
16
log ø +1)
By Fact A.18, with probability at least 06 |x] 5 0 bound the (absolute) difference between j and Aeorrupt, by
and by the Lipschitz. bound of Fact A.17, we can
log 3 n
5o ((V
(v(
log 87
log 8 + 1j
log 1 x n
j0 Acorrupt, & SO
|sly
S o
=((v))
n
n
Thus, on mean-O-variancee 1 distribution, with probability at least 1 - 8' over the clean samples (and with an arbitrary n-corrpption), Estimator outputs
log M S o(1))
+ (135 + v(1))
n2
Combined with the affine invariance of Estimator 1 as stated in Fact A.17, if the underlying distribution instead had mean and variance o², we have the mean estimation guarantee
l - u1. a. (1V2tOCIny log 1 + (135 +135+
n
as desired.
We note that the o(1) / term in the estimation error is solely incurred by the estimation error from the initial estimate K.
A.4. Proof of Theorem 2.2
In this section, we present the proof of Theorem 2.2. While the high level idea of our proof similar to that of Theorem 2.3, there some important distinctions, most importantly in what require the failure probability of our component lemmas to be.
Recall that in Theorem 2.3, while we gave the parameter 5 to Estimator 1, we relaxed the failure probability of the estimator to 8' 2 8. On the other hand, Theorem 2.2 actually analyzes Estimator at failure probability which in turn requires the prerequisite lemmas to have failure probability < 6.
Towards that end, notice that given the desired failure probability 5, we let 8' be such that glog 1 = |/ log 1 + 8qm, then ò 8'e 24mm Thus, the goal of this section is to devise analogs of Proposition A.4 and A.11 with failure probability instead. We stress that this reparameterization is purely for analytical purposes; Neither the estimator the user know anything about the corruption parameter 7) or the analytical assumption we use to define 8'. Our choice of the constant 8 in front of the ryn term is different from the previous section, and stems from somewhat arbitrary numerical choice to prevent constants in the theorem from blowing up, while also implicitly posing constraints on
-'e-24mp 24 as
We present the counterpart of Proposition A.4 first, bounding the error coming from the change in a value on uncorrupted samples, with smaller failure probability.
22

---

All-Purpose Mean Estimation over R
Proposition A.19, Suppose both log and are bounded by some small universal constant. Let o be the influence parameter computed from the clean samples with robustness level glog & + 81n, namely, a= 028' SSy- Let å be the 3
influence parumeter computed from the corrupted samples with robustness level 3log & + 81mn, namely, == 0&8 So Then with probability least 10 8' 24mm, the mean estimate using a on the clean samples differs the mean estimate using â on the clean samples by at most 195.065 /n,, L.e,
Σ Ty miin(áz)
Σ x, min(ax) 1) I 195.065m
We begin proving Proposition A.19 by stating alternative version of Lemma A.10:
Lemma A.20. Suppose both log 2 and ö are bounded by some small universal constant. Then 0181
n 0.000214 (log 8 24mm) with probability at least 1 4 e 24mn.
The proof identical to that of Lemma A.10, with the appropriate log 1 and 5 terms replaced with log &. + 24mn and 8' -24mm instead.
Now that we have lower bounded (with high probability), analogously to the proof of Proposition A.4, we wish to also lower bound à. The proof of this lower bound will deviate from that in Proposition A.4-in Proposition A.4 we were analyzing and comparing ā := ā5 3n and a == 0s8,ot here in Proposition A.19, we are comparing ā := ā. ,8 against = 0'8 8t-
For Proposition A.4, the "r-suubscripts" between the two "a" values differ by 3n, so we could apply Corollary A.3 and the monotonicity of a&' in the "q-subscript" to yield ā == .8' 3n 0..n 2 a ag , Here, we need a new argument to lower bound à = (rpt,8p shown in the following lemma.
Lemma A.21. Suppose both log and d are bounded by some small universal constant. 0.0000354| (1005544((ogg (log & 24mn) with probability at least A 22mm
Then == Öeg' ,8)
2
Proof. Notice that ā = 28 .on 2 ..866n Bon by Corollary A.3. Letting x == C1 A (log + 24mn) for some constant < 4. we have
(24m + log ):) = 6rm + - log 1 8'
1
1
< Grm +
log 8'
Σ min aas (1
S Σ
mān;
by Corollary A.3 as above
Σ
min (āzz 1)
Σ
min(áx7. 1)
S:re not in the top quantile
i:x?? in the top quantile
<
Σ
ax +
Σ
1
the top quantile
d top quantile
Σ
āx + AM
sir? the quantile
an, + c24mm + log 1
Σ
8r)
iir? not in the quantile
This implies that
Σ
ax, 2 Ci (log z
+ 24m)
daa? the top quantile
23

---

All-Purpose Mean Estimation over R
With a slightly modified version of Corollary A. A.16, bounding Eis? not in the up quantile 2, by (e2-2) with probability at
(cx+1)cc
least A - -2mm we can choose e 0.202, e2 = 399.443, cg 1328.46, and obtain 0.0000354(1og & + 24mm) as desired.
Proof of Proposition A.19. First, notice that for all i such that [xy]] 2 max m
min(a,a). the corresponding
term in the left hand side becomes O. Thus, using the notation
Σ> denote summing over elements |
V mmn(o,aa. the
left hand side in the guarantee of Proposition A.19 is equal to
Σ min(āaf, 1) Σ min(aaf 1)
Then, rearranging the sums, we have
Ty min( 1)
Σ vi min(aa2 1)
De (min(áz)) 1) min(ax;, 1))
Σ x
(min( 1)mnn 1))²
by Cauchy-Sehwarz Schwarz
for which we can bound the two terms separately.
To bound the first term, since we sum over only those terms where [x:]] S min(as mi, for all i, and by Lemma A.20
and A,21, min(as Sny 887 a)) 0.0000354 (log 37 + 24mm) with probability nr 8' -21m we have that of S n
28249n
for
log +24m
all Since X has mean O and variance 1, we know that [xxx]] S [ = 1, and Var[a?] & R[xx)] S 3 +224gp
28249m
[x
TEl
S
28249n
Thus, by Bernstein's 's inequality,
log z +24mp
Σ 2 z
19025n
SP
P
2 12
19024
< P
2 -[
2 19024
n
19024
< 2 2exp
56498
+ 56498 19024
12
/3
log J 24mm
log Φ +2mm
< 2 eexp
-100 8 + 24mm)
11 (-(log zr 24m))
< 2 2exp
for suff. small 8
2 _ e 247
11
In other words, conditioning on Lemma A.20 and A.21 both holding, with probability at least 1 3.8 8' . 24mm Eg 27 19025n.
24

---

All-Purpose Mean Estimation over R
To bound the second term, note that depending the order between == a''' 8y and à äg 88y either min(oaf, 1) min( 1) 2 0 for all i, min(dar; 1) min(ax?: 1) ā a, and that min(aaf, 1) min(axr 1) 2 0 for all i.
for all holds. Without loss of generality, assume that
Then, we have
(min((az) 1) min(a2, 11)² (min(āaff 1) min(aaf 1))² 2 Σ (min(āx; 1) min(axf. 1))
since ā 2 a, and that m 1) min(axz) 1) 2 for all i.
To further upper bound the last quantity, we have
Σ (min(āz). 1) min(ax}, 1))
Σ min(āx..1) Σ min(ax;, 1)
$
Σ min(as' .00 1) min 11
by Corollary A.3 and by the definition of a
1 10mn
1
log 8'
log 8'
8pm
2mm
Finally, summarizing, we have that with high probability least 1 11 8' 24mm;
Σ x
Σ (min(āxf, 1) min(ax;, 1))²
I 19025n 2mp
= n /38050 S 195.065n
as desired.
We now present the counterpart Proposition A.11, bounding the error due the adversarial corruption with tighter fallure probability.
Proposition A.22. Suppose both log and 5 are bounded by some small universal constant. Let be the influence parameter computed from the corrupted samples with robustness level glog + Sim, namely, â = 0&8' Sn Then with probubility at least TI 8'e - -24m the mean estimate using on the clean samples differ from the mean estimate using on the corrupted samples by most 26.411 VT. i.e.
Σ 5:(1 min( 1)) Σ x1(11 min 1)) < 26.411n/7
Proof. With arguments identical to that in the proof of Proposition 1. the maximum error the adversary incur by corrupting yn terms is 4xy To arrive at a similar lower bound of ă in terms of 17, notice that by Lemma A.21, we have that with probability at least 1
3v/3
5'
e 2-24m
11
ā > 0.0000354- 1
log 8r + 24mm 0.0000354- (20003)4-(2Am)) 2 0. 0.00084967
Thus, we have that
Σ (4(1 - m1n21, 1))
Σ (1 m 1))
5
4nn
<
4my
S 26.411nn
3/
3/33 0.00084967
25

---

All-Purpose Mean Estimation over R
Equipped with Propositions A.19 and A.22, are ready to formally prove Theorem 2.2.
Proof of Theorem 2.2. We will start by assuming that the underlying distribution has mean 0 and variance (by the shift- and-scale equivariance of Estimator 1), and furthermore, that the initial estimate computed in Step 1 is exactly the true mean of 0. At the end of this proof, we will show that the 0 assumption introduces only negligible amount of mean estimation eтror.
Fixing the initial estimate ε = 0, then, Estimator on input the clean samples X and confidence parameter á computes the influence parameter a == 0,6,0, and returns an estimate Petean.a := #. E, zz(11 - min(az? 1)). Note that as,0 = 0t'' ,8 since glog 2 log & + Syn by definition of 8'.
As part of their analysis, Lee & Valiant (2022) showed that
log Medeana S (V2 (V2+)01) (())
n
with probability least 1 6. We note that the above guarantee can in fact be slightly strengthened, so that the failure probability becomes 6/22, at the expense of slightly increased (1) by more than constant multiplicative factor.
Now we consider changing the "a" value from to â computed from the corrupted samples, but applying these a influence parameters on the same clean sample set, and bound the difference in the resulting mean estimates. Specifically, consider := 0 which is the influence parameter computed with robustness level Glog & + 8yn from the corrupted samples. Let the mean estimate of using à on the clean samples be Patean, : :/ E, 1mminnx2?.... 1)). Then, by Proposition A.19, with probability at least 11
8 -2in 1 10 we have
11
Peleon,& Melean,a
1 Σ vs min(
-) x4 min(ax] 1) < 199..655
Next we consider the effect of replacing the effect of corruption, but after fixing the influence parameter to be a. Specifically, define Pcorrupt. & to be the mean estimate of the corrupted samples using ā, namely 1 E, H (1 min(ā.? 1)). Then, by Proposition A.22, with probability 1 conditioned on Proposition A. and thus Lemma A.21 holding, we have
Proorrupt, Peteann al =
Σ 5.(1 min(as)) 1)) Σ m1(1 min(āu?, 1)) < 26.411
21 5, By union bound and triangle inequality, summing over all three error terms, have that with probability at least
22
Peorrupt, & satisfies
log 1 221.476 (V2 (/2++(1)) o(I))
log x 222
Ppoorrapt. S (V2 (V2+ ((1)) oV)))
n
n
Finally, observe that mean-O-variance-- the output of Estimator 1 (on input as stated in the theorem statement) lies in Pcorrupt. & assuming that the initial mean estimate K was the true mean of 0. On the other hand, (Estimator 1) computes x. from data.
distribution, and with n-corruption, the only difference between Meorrupt, á and
We use Fact A.17 as well as the following fact/assumption about the robustness of the initial estimate л against adversarial corruption to analyze the effect of the x assumption. Fact A.23 is known to hold true for median-offmean as folklore result, which we show in Appendix F for completeness. As mentioned Estimator 1, we can choose to use other estimators to compute the initial estimate x as long as the estimator satisfies Fact A.23.
Fact A.23 (Folklore). For any distribution D with mean μ and standard deviation let X be set of n-corrupted samples from D. Assuming that 1) S 2An log 3, the meeiann-of-meade estimate &s from grouping samples into O(log 1/) buckets, on
input X, satisfies
1 log <
1 22
P
I
pal 00
26

---

All- All-Purpose Mean Estimation over R
(vor,
log
By Fact A.23, with probability at least 1 the (absolute) difference between f and Pcorrupt, by
22 6. |K| S
and by the Lipschitz bound of Fact A.17, we can bound
log 5O
log (V(le))
))
log
l Pcorrupt. SO
[kly
50
n
m
Thus, on mean-O-variance I distribution, with probability at least 7-cormuption), Estimator outputs
ô over the clean samples (and with an arbitrary
log A S (v2+
n + 222
Combined with the affine invariance of Estimator as stated in Fact A.17, the underlying distribution instead had mean j and variance o², we have the mean estimation guarantee
1á 0 (WZ+ log + 222
n
as desired.
B. Robustness of Estimator 1 in Weaker Models
As corollaries to our main results, stating that Estimator robust against adversarially corrupted data, we also show that Estimator is robust against two (slightly weaker) contamination models, namely Huber contamination and TV contamination. For simplicity, we present and prove direct corollaries of Theorem 2.2 only. Corollaries of Theorem 2.3 follow similarly.
Definition B.1 (Huber contamination (Huber, 1992)). Given corruption parameter v and a distribution D the uncorrupted data, say that set of n samples is j-Huubrrcontaminate sample from D if it is drawn i.i.d. from some distribution (1 D E for arbitrary distribution E.
The Huber contamination model (Huber, 1992) be regarded being weaker than the strong contamination model, because the corruption is always drawn randomly and obliviously from fixed distribution E chosen by the adversary; on the other hand, the adversary in the strong contamination model gets to choose the corruptions adaptively after inspecting all the samples. We point out however that, due to the random nature of the number of corrupted samples in the Huber model (and TV contamination model later in Definition B.5), these models are not strictly weaker than strong contamination, despite being "weaker expectation". Nonetheless, by Chernoff bounds, the number of corrupted samples will concentrate (1m) except with exp( (x)m)))(mm) probability.
Later on, in Appendix C, aim to show the neighborhood optimality of Estimator 1 as corollary of its robustness against Huber contamination. In those results, we aim for a failure probability at most ó when the algorithm is given input, as opposed to a failure probability that is (slightly) larger than 6. Consequently, we write our theorem below (Theorem B.4) for Huber-contamination robustness with a failure probability 5/2 + exp( ((pm)) so that it is upper bounded by when is sufficienlly large.
We will show Theorem B.4 corollary Corollary B.2, which a variant of the atrong-comtaminatte robustness result in Theorem 2.2, with failure probability 8/2 instead of 8. Then, recalling that the probability of having many corruptions most (xp(-9((ym))
union bound gives the target failure probability in Theorem B.4.
Corollary B.2. Given any distribution D with mean μ and variance o², parameters n, n, n let X be set of n-corrupted samples from D.
We point that, somewhat counter-intuitively the larger is, and the stronger the corruption is, the less likely that Huber contamination produces many more corrupted samples than adversarial corrpttion.
27

---

All-Purpose Mean Estimation over R
Suppose both log and 6 are bounded by some small universal constant, and suppose o S 24m at least 26 over the sampling process, Estimator I input ê and X will output an estimate ji with ervor at most
1 log 3. Then, with probability
l μl s.. (1 (1+)
2log & 222v/n
n
The proof of Corollary B.2 is almost identical that of Theorem 2.2. The main difference is, instead of using Fact 1.1 to guarantee the performance of Estimator on ii.d. uncorrupted samples, below. Specifically, Fact B.3 inputs the parameter ó to Estimator but asks for failure probability of 6/2 instead of 8, at the expense of a slightly larger "o(1)" term. Given the above target parameters, Fact B.3 is not black-box corollary of Fact 1.1. Nonetheless, follows directly from the analysis in Lee and Valiant's original paper (2022), so we state it without proof below.
stronger variant which is Fact B.3
Fact B.3 (Lee& & Valiant 2022). Given any distribution D with mean and variance o², parameters n, > O, let X be a set of n independent samples from D. Then, with probability at least 8/2 over the sampling process, Estimator on imput 8 and X will output an estimate i with error most
js - s (1+0(UN)
2log
Here, the d(1) term tends to 0 as
(oor3, - (0,0) and, crucially, is independent of D.
logg
We state and prove the robustness of Estimator against Huber contamination.
Theorem B.4. Suppose both log and 5 are bounded by some small universal constant. Given any distribution 1) with mean and variance o², parameters TI, 8,11 > O, and a set X of n p-Fluber-contaminatel samples fo some S 24en log 8 Estimator of LV22, when given access to n, 8, and X only, will, with probability at least - (7 + cexp(800p)) over the sampling process. yield an estimate fi with error at most
(a+OOUIN)
log
A pl a.
+ 222
2 331 /32//311
Proof. Note that sampling from distribution (1 D) + E is exactly identical to sampling from D with probability 1 and from E with y,. We bound the probability that such a sampling process samples more than 33ym samples from E.
Let 2 denote the indicator variable for the event that sample x, is sampled from E. By multiplicative Chernoff:
2 N 33mm] <
3333
Thus with probability least exp(-80mm) the Huber-contaminated sample has most 33m samples corrupted.
Conditioned on this happening. Corollary B.2 applies to the set of contaminated samples X with adversary capable of arbitrarily corrupting 33mm samples, with probability at least 1 2 8. Our theorem thus follows from union bound. L
Generalizing from Huber contamination slightly is the TV contamination model, which draws samples from a distribution D' that is within TV distance from the genuine underlying distribution D.
Definition B.5 (TV contamination (Diakonikolas & Kane, 2023)). Given a corruption parameter 7) and a distribution D on the uncorrupted data, we say that a set samples is an 17- Tooommmmiidd sample from D it drawn i.i.d. from some distribution D' such that Dry D, D') < 77.
And correspondingly, we have the following theorem showing that Estimator is robust against TV contamination.
28

---

All-Purpose Mean Estimation over R
Theorem B.6. Suppose both log and 6 are bounded by some small universal constant. Given any distribution with mean and variance o², parameters n. 5. lj > O, and a set X of n. D-TV-coontminatee samples from D, foror some lj S 24en log 8- Estimator of LV22, when given access to n, 6, and X only, will, with probubility at least (26 + eexp(-80rm) over the sampling process, yield an estimate fi with error at most
log j - pl a. (L+)ODI))
n + 222
/3311
337
Proof. Let D' be any distribution such that Drv (D, D') S 9). There exists a coupling between D and D' such that for any sample index i, the probability that the sample Fj from D and the sample z from D' differs is at most 1).
Let 2; denote the indicator variable for the event that differs from 24. By multiplicative chernoff:
e33-1 m
P 24 2 33mm]= -
3333
i=1
S exp( (800m)
Thus with probability at least 1 - cxp(-800rr) the TV-contaminated sample set has at most 33mn samples corrupted.
Conditioned on this happening, Corollary B.2 applies to the set of contaminated samples X with an adversary capable of arbitrarily corrupting 33m samples, with probability least 1 - Jo. Our theorem thus follows from a union bound.
C. Neighborhood Optimality of Estimator
Neighborhood optimality is a notion of bessaacc-by-instann optimality beyond the worst-case defined in Dang et al. (2023). In this section, we show that Estimator 1 is also asymptotically neighborhood optimal as a corollary to its robustness against TV contamination. We point out that our result matches that of Dang et al. (2023), which states that the median-of -fe-mn estimator is asymptotically neighborhood optimal, with the same choice of neighborhood structure and asymptotes.
For mean estimation in R. Estimator 1 achieves the optimal nab-Gaussian rate even up to the constants. Their optimality is only in the worst-case regime, i.e., there exists an instance of mean estimation which no estimator can perform better. A natural question to this observation is: Can we beat the sub-Gaussian rate for some distributions?
Dang et al. (2023) presented the following new universal estimation lower bound function:
Definition 2.5 (Dang et al. 2023). Given a (continuous) distribution D with mean and real number E [0, 1]. define the t-trimming operation on D as follows: select a radius r such that the probability mass in [er - r, + r] equals - f; then, return the distribution D conditioned on lying in [μ- T. f + +
Given n and 6, define the trimmed distribution D to be the 0.15 log } -trimmed version of D. When is implicit, we may n
denote this as D Now define the error function (D) |u+ - --7l + o, log where jr, and of are the mean and standard deviation of D respectively.
The ground truth error function 62,6 in Definition 2.5 applies simultaneously for all distributions with a finite mean, not just for the worst-case distribution, in the sense that for any distribution p we can construct neighboring distribution g that is indistinguishable with probability at least 1 - with samples, but the mean of p and q are well-separated by O(e,, (p)) in distance. Thus, no estimator can beat the error function on and g simultancously, since any estimator that can will be distinguisher between and
To formalize this notion of lower bound and optimality, Dang et al. (2023) presented the following pair of definitions:
Definition 5.1 (Neighborhood Pareto Bounds (Dang et al., 2023)). Let n be the number of samples and o be the failure
probability. Given a neighborhood function Nn.8 : P, > 2P,, we say that the error function (D. P, - I is a neighborhood Pareto bound for Pı with respect to N,.5 if for all distributions D E P1. no estimator K taking n i.i.d samples can simultaneously achieve the following two conditions:
29

---

All-Purpose Mean Estimation over R
For all D' E ( with probability - 8 over the i.i.d. samples from D', have j jur S cn, (D').
With probability 1 over the n i.i.d. samples from D. 12 pDl < (n,)(D).
Definition 5.2 ((K, 7) -eighhboood Optimal Estimators (Dang et al., 2023)). Let > 1 be multiplicative loss factor in estimation error, and r > 1 be a multiplicative loss factor in sample complexity.
Given the parameters K, T > 1, sample complexity n, failure probability and neighborhood function N a mean estimator j is (Mi nniihhhooooo optimal with respect to Nn.6 if there exists an error function (n, such that min(Er2/,,6DD) (D),, en, (D)) is neighborhood Pareto bound", and j gives estimation error at most K En, (D) with probability at least 1 - 8 when taking i..d. samples from any distribution D E PI.
Definition 5.1 enforces that it is impossible to "beat" the neighborhood Pareto bound locally, performing as good over the local neighborhood, while strictly better on the center p. It essentially enforees admissibility over every such local neighborhood, forming a smooth interpolation between instance optimality and admissibility, which are both classical definitions of optimality beyond the worst-case that fails in context of mean estimation in R.
Dang al. (2023) showed that there exists a neighborhood function Nn.6 for which 6n,6 as defined in Definition 2.5 is neighborhood Pareto bound, and for which median-of of---ens- is (k. neighhboooo optimal for some sufficiently large constant K. We capture the necessary components of their analysis and state them without proof in the following fact:
Fact C.I. There exists a neighborhood function Nn,6 Pi - 2P: for which 6n,5 as defined in Definition 2.5 is a neighborhood Pureto bound. Any estimator that obtains estimation error (p), for all distributions p E P1 is (x. neighborhdd optimal with respect to Nn.6 for some sufficiently large constant K.
Thus, to show that Estimator 1 is neighborhood optimal, it suffices to show that it asymptotically matches the performance of the ground truth error bound En,9. We present a reanalysis of Estimator 1 using its robustness against TV contamination that proves its neighborhood optimality in such a way.
Theorem C.2. Suppose both 1. and ō are bounded by some small universal constant. Denote by Nn.5 the neighborhood function whose existence is implied by Fact C.I. Estimator 1 is (k, (eiig)-oogh optimal with respect to Nn.6 for some sufficiently large constant
Proof. Let 6n, be the ground truth error function as defined in Definition 2.5. By Fact C.I, it suffices to show that Estimator 1 achieves an error rate of (p), for all distributions p.
Let p be any distribution with mean Ppp- Let e be the constant such that E log 3 = 80n log S 2den log 3. Let P be the n e log --trimmed version of p as defined in Definition 2.5, and let pv; and σyz be the mean and standard deviation of ph "
respectively. Let Gn be the error function as defined in Definition 2.5.
Observe that P., satisfies that Drv (Ph. p) S log 8. Thus, by Theorem B.6 with D = P/ and r7 a. log 8. we have that with probability at least 1 - (g0 + exp( (xx(-)8mm)) = 1 6,
2log + 2221 (1+ (1+0(1)1)
33c log 3
i Mp:1 5 Op
n
log 5 n
0
Jpt
Thus by the triangle inequality, we have that with probability at least 1- 8,
log 1
A - Hpl S 1pp - Mppll + la Mog S 1pp - Mppl +
Opa
O(En,)
Combined with Fact C.I, this implies that Estimator is indeed (H, neighhooooo optimal with respect to Nn.5 for some sufficiently large constant K, as desired.
'While it intuitive expect that error function decreases in n, it might not be true in general. Indeed, the function used by Dang (2023) (Definition 2.5) is not necessarily monotonic. This is the reason for the "min" in the neighhorhood Pareto hound requirement.
30

---

All-Purpose Mean Estimation over R
We point out that the proof of Theorem B.6 and Theorem C.2 does not depend the specific characteristics of Estimator 1, and instead only relies Theorem 2.2 holding. Thus, we can obtain similar neighborhood optimality result for any mean estimator that is sub-Gaussian and robust against adversarial corruption, and enjoys asymptotically matching bounds as in Theorem 2.2:
Corollary C.3. Any estimator that, when given 5 > 0 and a set of n n-corrupted sample from distribution D with mean and variance o², yields a mean estimate ji satisfying
log
+ vn )
A P S
is (M, neighborool optimal with respect to Nn. for some sufficiently large constant K.
D. Remaining Proofs of Section 6
In Section 6, we outlined the proof strategy of our main theorem for low moment performances of Estimator 1, which follows that of Lee & Valiant (2022), and provided the statement of the reformulation of Estimator 1 as a 2-parameter vi-estimator. In this section, present the full proof of Theorem 2.4, following the structure and organization of Lee & Valiant (2022). We present each component lemma along with the intuition behind it, and refer the reader to Lee & Valiant (2022) for more detailed motivations and discussions. For completeness, we restate our main theorem:
Theorem 2.4. Given any distribution D with mean μ and 2thh moment M, for some E (1,2), let X be a set of i.i.d. samples from D. Then, with probability at least - ô over the randomness of X, Estimator I on input ó and X will output an estimate fo with error at most
li - 11 s (M.) (1 (1+0(1) +o(1) (<z log 1 1-1
where 6₂ = = Here, the o(1) term tends to O as
log $ 5) - (), in a manner independent of D and
independent of
From the structural properties of Estimator 1 stated explicitly in Fact A.17, we make the simplifying assumption that the underlying distribution D has mean 0 and 2th moment M, 1, and that the initial estimate in Step 1 of Estimator 1 is replaced by O. For the rest of the appendix, we will refer to the error bound (c.log 1 //n) (omitting the + (11) factor).
Definition 6.1 reduced proving Chernoff bounds for Estimator 1, which is a sum of dependent terms, to proving Chernoff bounds for the sums of independent terms of the 2-parameter vl-estimator. Thus, it suffices to show that with high probability, the u--estimator in Definition 6.1 returns an estimate ğ that is close to 0-or equivalently, every pair (Ā', â') with pl far away from 0 must satisfy vXX, fu ,ā)
(')+ # O. We turn to analyze the following proposition, capturing this reduction:
Proposition D.I. There exists universal constant O such that, for all 1 < 2, fixing e' = -(1+ clog log
log
where e = ((c- log, 1
1-1 and c₂ = 2(5.6) we have that for all distributions D with mean 0 and =h moment 1, with
probability at least 1 over the set of samples X, for all ja, â where [M > e' and â > 0, the vector (6X, A. âc) # O.
We stress that the universal constant c in fact does not depend on 2.
Towards proving Proposition D. 1, we extend Lee & Valiant (2022)'s 's strategy, analyzing the function (XX,, f. àr) on a finite bounded mesh of values of P., & covering the most delicate range for our analysis, and show via standard e-net arguments that the proposition holds for any choice of [ > c', â. Specifically, from the origin in some direction, and is Lipschitz within the mesh. We then show how to reduce the analysis outside of the mesh to that inside the mesh
show that (i, f. â),, on the finite mesh, is far
way, we reparameterize & by u = log log"(1 (1/6)
To find a mesh to cover the relevant range of & in the right where in the denominator (as defined Proposition D. encodes the desired dependence on 2. We choose an evenly-spaced mesh over ii E (0.05, 555). This is analogous to the mesh on "0" in Lee & Valiant (2022)'s s analysis.
3
31

---

All-Purpose Mean Estimation over R
The main technical component of our (and Lee & Valiant (2022)'s) proof strategy is the proof that for each fi, @ = (1/8)
3an=22
from the finite mesh we analyze, (xX,, Ai, de) is far away from 0 in some direction. We linearize this claim and prove a stronger result, that there exists specific direction (()) such that with high probability, (x(X, â, is more than Ing(1/8) distance away from the origin in direction d. More formally, we prove the following lemma:
Lemma D.2. Let D be an arbitrary distribution with mean O and 2h moment 1 for some 1 < 2 2. There exists a
universal constant e independent of z where the following is true. Fixing μ = (1+ clog log à where c = (o= log and c2 2(5.6) - -1 then for all 8 smaller than some universal constant, for all ń E [0.05, 555], there exists a vector d( == (du, da) where dy 2 0, and both ne ddy and Idal are bounded by universal constant, such that log 3
1-!
log :
n
P X-DD
(d(τ))
.16 16 [x, [x,p= =
log log"(1/5) 32n
1 log
2
8
log 4
6
Furthermore, for i 0.05 we have dμ = 1/3.75 lus ne
da = 33; and i 555 we have du = 0, da < 0.
From here, Proposition D.1 follows from union bound over pairs of (Í², on the finite mesh, the monotonicity of (X,, f. a) beyond the mesh granted by the boundary conditions specified in Lemma D.2, and the Lipschitzness of (X, f. â) within the region covered by the mesh, formalized in the following lemma:
Lemma D.3. Consider an arbitrary set of samples X. Consider the expressions ( a), v â), reparameterized
log" 1
Jan=zz in place of â. Suppose the equation (X,(,,) = O has solution in the range w E [0.05,, 555). log y Then the functions ne y (X, it, â) and (x((X, a) are Lipschitz with respect to i the entire interval u [0.05, 555], with Lipschitz constant clog z for some universal constant c.
in terms of i
With these components, we now prove Proposition D.I, and subsequently formally prove our main theorem, Theorem 2.4, before returning to prove Lemma D.2 and D.3 in Appendix D.I.
Proof of Proposition D. By symmetry, instead of considering positive and negative ft, it suffices to consider the case f >> é' and show that this case succeeds with probability at least 4.
To prove the claim, we first prove a stronger statement on a restricted domain, that with probability at least 4 over the randomness of the sample set X, for each v E [0.05, 555] there exists a vector d = (dn, daa) such that d ( é', â) > 0,
with d, > 0 throughout, and, for い = 0.05 we have dy, = 33.75 log ne da = v3, and for n = 555 we have d,, = 0, da < O.
We will first apply Lemma D.2 to each vi in a discrete mesh: let M consist of evenly spaced points between 0.05 and 555 with spacing 1/ log" 3 (thus with G(log" }) many points).
elog 3 (which at least 1 - 4 for 8 smaller than some universal constant) over the set of n samples X, for all ve e M, there exists a vector d(w) such that d(w)) (X, fi = é', a) > 1/log J. where d further satisfies the desired positivity and boundary conditions, ne and where both log 1 |dpp and |da| are bounded by a universal constant. For the rest of the proof, we will only consider sets of samples X satisfying the above condition.
By Lemma D.2 and a union bound over these O(log" })) points, we have that with probability at least 1 A
Now consider an arbitrary w' E [0.05, 555] \ M and consider the vector db evaluated at á' = log" 2
2n= We wish to extend the dot product inequality to hold also for w' If via + 0 then there is nothing to prove: set dy = 0 and da = sign(wa)) otherwise, via = 0 means we may apply Lemma D.3 to conclude that both log 1/ (X, A. a') and soo (X, A, â') are Lipschitz with respect to á' on the interval áò e [0.05, 555] with Lipschitz constant clog 1 for some universal constant c.
me
Consider the closest ii E M to W', which by definition of M is at most 1/ log 3 away. By assumption on X, there exists ne log _ [d, and [da| are bounded by a universal
a vector d such that d constant. Because of the Lipschitz bounds on g, combined with the bounds on the size of d, and da. we conclude that the Lipschitz constant of the dot product (treating the vector d as fixed) is O(log 1). Thus, the large positive dot product at ú implies at least a positive dot product nearby at w.: d (Xx f ,',²') > log 5 small 8 as given in the proposition statement.
> 1/log J. with dz > O and both
O(log 4) logg > O, for sufficiently
32

---

All-Purpose Mean Estimation over R
Having shown the stronger version of the claim for the restriction jı e' and i E [0.05, 555] we now extend the entire domain via three monotonicity arguments. Explicitly, assume the set of samples X satisfies the dot product inequality above with the vector function d()), where d( satisfies the boundary conditions at ú = 0.05 and 555 specified in Lemma D.2.
log" à 3 and for any já 2 é.
From this assumption, we will show that v/ + 0 for any positive i
First consider vi > 555, still fixing js = c'. The function vh, = Σ
1 log }) is an increasing function of 3n
1 á, and thus decreasing function of प Log" 3 Since for v = 555, the dot product d u >> 0 with dy 0, da < 0, the dot product will thus remain positive for this same choice of d as we increase v from 555.
Next, for < 0.05, again fixing A = c', we analogously show that the dot product of (xX â) with the fixed vector (00005) will increase as we decrease w. The i-th term in the sums defining f) or tha depends on â (and thus ú) only in the factor min(áx;;; 1). Further, there is no dependence unless the first term attains the min, namely |ay S v1/ā, which in turn is upper bounded by v0.15 nc log 1 because of our assumption that v < 0.05. Thus, the only i-th terms in the dot product which have á dependency are simply equal to dæóaş + dz = dx? (da + v:d,). By our choice of de (0.05) = v3.75 l and da = v3 from Lemma D.2, the expression (da + rıd,)) 2 v3 - vo.15v 3.75 is thus always non-negative, and thus the overall dot product cannot decrease as we send i to as desired.
We have thus shown that, for all non-negative á log" 3 there is vector with d, 0 whose dot product with e',,'', '', â) is greater than 0. We complete the proof by noting that the only dependence on jú in e is that th is (trivially) increasing in js. Since d2 2 0, increasing from e' will only increase the dot product, and thus the dot product remains strictly greater than 0, implying that (XX, â) + 0, as desired.
To close out this section, we formally show that Proposition D.1 implies our desired main theorem, Theorem 2.4 for completeness, using the following fact about the performance of the median-of-ment means estimator for the initial estimate k:
Fact D.4 (Bubeck et al. 2012). For any distribution D with mean μ and 2hh moment ds the median-of estimate from grouping samples into Ollog {)) buckets, on input n samples, satisfies
log 0 (oz)=
1
P
|K - ul m
8
n
2
Here, the big-O notation hides a universal constant that is crucially also independent of z.
Again, we are free to choose to use other estimators for x in Step I of Estimator 1 as long as the above fact holds true for the estimator being used.
Proof of Theorem 2.4. We start by making the simplifying assumption that μ 0 and M, = 1, and reformulate Estimator 1 with Step replaced with x- 0 as a 2-parameter gi-estimator, that takes in n independent samples X -1,-.. T from D, and solves for the (unique) pair م. & satisfying v) and vio O, where the functions are defined follows:
(x ( =
(io 1,(1 min(da? 1)))
Na (X, 2. ④) = Σ min((aa, 3n log x
and outputs f in the solution. We denote by da the 2-element vector (1hys tba)
5 2. any jl, â' with | > (1+ C2 log 1- and á' > 0 satisfies that
By Proposition D.I, with probability at least 1 -
(x= 1
1-1
(X, a') * 0, and thus the solution á found by Estimator by solving vé = 0 satisfies | S (1 + o(1)
33

---

All-Purpose Mean Estimation over R
We now remove the simplifying assumptions using the structural properties of Estimator Let be the initial estimate in Step of Estimator say, computed by median-of-means. By Fact D.4, with probability at least 1 2
log 1 A 1-1
S O
n
log 3. (v
and by the Lipschitz bound of Fact A.17 with Lipschitz constant
this incurs an error on Estimator of most
((1 log 1 1-!
1-!
log
log
S o
Since 62 1-1 is lower bounded by universal constant, the above expression is also
((== log 1-7
Now consider any distribution with mean z and 2thh moment M2. By the affine invariance of Estimator of Fact A.17, Estimator suffers multiplicative factor of (M₂)* in the estimation enror.
Thus with probability at least 5, we have
log 1-1
IĀ(X) pl (M,) o(1))
n
desired.
D.1. Proof of Lemma D.2 and D.3
In this section, present the proof of Lemma D.2, motivated by the discussion in Section 6.2 and consequently Lee & Valiant (2022), modeling the worst-case Chernoff bound as max-min linear programming game. We later present the short proof of Lemma D.3.
Lemma D.2. Let D be arbitrary distribution with mean 0 and t moment for some 1 <<25> 2. There exists
universal constant independent of = where the following is true. Fixing j (1+ clog log
whhere = (c= log 1-!
log
and c₂ = 2(5.6)=-- -1 then for all 8 smaller than some universal constant, and for all i E [0.05, 555). there exists a vector d(w) = (dus do) where dy 2 O, and both log
ne dul and |dal are bounded by universal constant, such that
(d(i)- .
log log2 (1/6)
P X=DD
X, [ == =
2
322
log I
log
Furthermore, for v 0.05 we have d, v3.75llos log me
da 33; for i 555 we have d, 0, da 0.
Proof. We instead bound the contrapositive statement, namely,
(d(()) + (x, = á log (1/8)
=é,==
X+D"
300
log 7
log
We start by applying standard Chernoff bound analysis
1
IP D=
d(()) t (X, a.) log
P (xp(-d(()) v (x, R. a)) 2 exp
=
(Tog
log
34

---

All-Purpose Mean Estimation over R
2 E (exp (-d(Ø) & (X, R a))) X
by Markov's and exp
S 2 for suff. small
log 3
=2 E (exp (-d(w) (x. jr, áz)))" #4-D
by independence
= exp
-dup f + de log
E x+ D
exp (d/=z(1 - min(óx"" 1)) da min(dx" 1)) 1)))
3n
Motivated by our discussion in Section 6.2, we state the following technical claim, Lemma D.5, reminiscent of the constraint in (2). We formally prove Lemma D.5 in Appendix D.2.
Lemma D.5. For all i E [0.05, 553), there exists a >> 0, such that for all and y E E, letting C₂ 2(5.6) - the following holds true:
ay(1 - min(y,, 1)) - b minnny I log 1+ ay + |ul (30)8 (-1+
/3 3)
(4)
where a and b are bounded by constants. Further, for ú 0.05, the pair a = 0.75, v3 works.
For á E [0.05, 555), we use Lemma D.5, substituting y Våx, to choose d,. Vár log 3 a, do b. In particular, nev/30
for i 0.05, we have d, v3.75 log 1
ne and da v3. Then, the failure probability is bounded by
exp
-duís + de log
1
E
11
(1ayy ay 1310)) -1 a
3n
x+ y=ovā
V3w
1
1)
(1+
log nev 3w
- dy da
2
exp
-dpí de 3n
log 8)
(3rh) Beg-1
log
3
since D has mean 0, th moment
1
log 8
dyen du
2
exp
-dyftt + du 3n
log
1
-1 +
8)
log 3
1
log
(-1 +
enen
da
< 2 exp
dyuft + du 3n
log
+
8
8
log
3
since
+ x S ex for any æ
1 )) 5
= 2 exp
-djfft + d. 3n
log 6
log + due da 3n
log
2 exp
ddnnn(f - -e) - log 8
a
2exp
c log log
log
by choice of d, and ç
\/n
log 4
as desired for large enough e, since
a greater than some positive constant.
v36
For ve = 555, we use the following technical claim:
Claim D.6. For all 1 < 2 S for all values of the following holds true:
minnyy211 < log(11 + 54|y!*)
35

---

All-Purpose Mean Estimation over R
which is easily verifiable by two subclaims in the form of 4y² log(1 54y²) for 1 y 1 and 4 S log(1 + 54/pl) for y > 1.
We choose d = O and d, = -4. Substituting yields
4
1
(exp (4 minn(xx2,1) .))))
exp
3n
- log
σ)
E x=D
I 284/3
JE (1 + 54 vva (r)²)"
by Claim D.6
x+D
log 1
284/3311 (1 + 54
ym
since D has moment
nEv 31
log
S 284/3 exp
n 54
since 1 + S c
neV 3 555
1 log $
1
2/4/33 exp
n 54
8
by definition of
2
5.6
V1665
n
54
log 1
284/3 exp
28-15.0 5.62
/1665*
< 228/388-0-20 0.237
for all values of 1 < 2 <
6
< 281.096
for suff. small 6
log 8
as desired.
We have thus proven one of two components necessary to prove Proposition D.I. We restate and prove the remaining component, which is a Lipschitz bound over the region covered by our finite mesh over e E [0.05, 555]:
Lemma D.3. Consider arbitrary set of samples X. Consider the expressions 15p (X, it, â), v (X, reparameterized
log" 3än+22 in place of â Suppose the equation va(XX, â)) O has solution in the range e [0.05, 555). Then the functions log b
in terms of uh
1 (X, jr, â) and vir (x, â) are Lipschitz with respect i on the entire interval ú [0.05, 555),
with Lipschitz constant clog 2/8 for some universal constant
Proof. Consider the derivative with respect i of Va (x, = = min
log² 3n 27, 22, 3n
1 log logg) :)) The i
log"? log" 331-24 22,, 1) is either a a = a or O, depending on which term in the min is the smallest,
derivative of min
and in either case has magnitude at most in min(óx? 1). Thus, the overall á derivative of t va (X, f. â has magnitude at most 1 >; min m 1). Since by assumption Σ; min(áx?, 1) = 1/2 log for some ú E [0.05, 555), the derivative with respect v must be within constant factor of log 1 across the entire range, as desired.
to
Similarly, consider the derivative with respect to à of (X, () Ei= (A zz(1 min(áz? 1))). The ú derivative of (A - (1 min(dn? 1))) either - 5. or depending on whether x; S V1/ā, and thus the magnitude of the entire derivative is bounded by wva E, min(ax;, 1). Since Σ, min (āxş, 1) is bounded by a constant times log 4. and wva is
bounded by constant times 1
vanc since i [0.05, 555], the magnitude of the derivative of log 1 34 2 (X, p. à) is
v va log 3 bounded by a constant times log 3. desired.
D.2. Proof of Lemma D.5
In this section, we prove the technical Lemma D.5. Lemma D.5. For all un E [0.05, 555), there exists a > 0, such for all < S and y E R, letting c₂ 2(5.6)=''- te following holds true:
(-1+
ay(1 - min(p2.1) - b 1min(2211) 1) < log 1 ay + 1ul (300)
(4)
//0
36

---

All-Purpose Mean Estimation over R
where a and b are bounded by constants. Further, for ú 0.05, the pair 0.75, b v3 works.
Proof. We remark that Lemma D.5 is more nuanced than its counterpart in Lee & Valiant (2022), in part due to the introduction of new variable in the exponent. However, notice that taking the derivative with respect to of the right hand side of (4), omitting the outer logarithm- is monotone function-ain omitting terms independent of z, yields
xz w 7 (3x) &
(lulV3u)= 2--1
5.66-= 22-1.5.62-3 log
2 v 32
5.6
whose sign is determined solely by the sign of log
2/u and thus is independent of This implies that the right hand 5.6
side of (4) is monotone in and thus it suffices to show that (4) holds for the boundary cases 2 -> and 2. Since
lim c = lim (2(5.6) -
- (2(5.6)=---))
5.6,
we evaluate the limit - 1 of (4) by simply substituting
into the equation and replacing the term c with 5.6.
We now choose the values of the parameters b. We follow the choices of Lee & Valiant (2022) for w < 5.5: for w 0.05
we set a 0. 75, b v3 as promised in the lemma statement; and for (0.05, 5.5] we choose a /6+ / /6+961 i.e.
2v20
the positive root of the equation (2 - 12) + v6a = O, and 3 Note that these choices set a > 0, as promised
in the lemma. For w 2 5.5 we differ from Lee Valiant (2022) and instead choose the constants a 4.2 and b -3 (independent of v
Case and [0.05,5.5] In this case our lemma is identical to its counterpart in Lee & Valiant (2022) and thus needs no proof.
Case 2 and 2 5.5: In this case we choose = 4.2 and b = -3, and thus Equation 4 simplifies to
4.2y(1 min(y², (0)g2,1))) 1)) + min < log (1 4.2y + /2V330 2 2.2
For y outside the range [-1, 1]. the first two terms become the constant 3; and since the polynomial inside the logarithm expression on the right hand side is monotonically increasing in y outside of y E [1, when é 2 5.5, it is sufficient to prove the inequality for E 1].
Further, the logarithm term is the only term that depends on w, and the logarithm monotonically increases with w, so thus it sufficient to prove the inequality for the smallest value of wh, namely ii 5.5. We thus show:
4.2y(1 )²) + 3y² S log (1 + 4.2y + 2/ 5.5
To prove this, we note that both sides are smooth for y E [-1, 1]; thus we take derivatives of both sides and set them equal to each other. The derivative of the left hand side a quadratic polynomial; and the derivative of the right hand side the multiplicative inverse of a quadratic polynomial. So thus the solutions to this equation the solutions is straightforward to find these four solutions for y with a computer algebra package, and confirm that, at all of these four possible extrema and the points y - 1, y 1, the desired inequality is true.
quartic. And it
Case = = and w 2 5.5 Next, we turn to the case of = = 1 and w 2 5.5, where we set 4.2 and b -3. Equation 4 now simplifies to a condition independent of u:
4.2y(1 min(y) ( 1)) + 3 min( 1) S log (1 + 4.2y + |M] 5.. 5.2)
As above, the expression inside the logarithm on the right hand side is increasing outside the range E [-1,1] and the left hand side is constant outside this range, so it is sufficient to show this inequality for y E 1] in which case it simplifies to
4.2y(1 y2) 3y² < log (1 + 4.2y + 1v1 5.6 4.2)
37

---

All-Purpose Mean Estimation over R
For negative y, the left hand side is convex and the right hand side is concave, so the left hand side minus the right hand side is convex, and its maximum must be attained at one of its two endpoints, y -1 y = 0. Numerically checking both cases confirms the inequality for y I O. For positive y, in the previous case, we take derivatives of the left and right hand side and set them equal to each other, leaving us with a cubic equation, which thus has closed form solutions. We thus check that the desired inequality is true at all the positive roots of the cubic, along with the extreme points y = y,y =1 1.
Case 2 1 and w (0.05,5.5) 5.5): In this case we have chosen
-v6+v6++0 the positive root of the equation 2v22
(2 12) + Vba = 0 and 3 22 Since a is an increasing function of d it is easy to check that, for á in our range (0.05, 5.5) we have a E (0, 3.1]. Because of these relations between a, b, úł, we can simplify part of the expression in (4) inside the logarithm as
V3@ -1+
a
b
1
a
V3@
3
2
Using this relation, and substituting 6 = 33- a² into the left hand side of (4) simplifies (4) to:
ay(( - min(12, 1)) - (3 _ min (z2, 1) - log (1 + ay - 228aaay/ yl)
As above, we point out that the left hand side is constant for y outside the range [-1, 1] and the right hand side is monotonic away from this interval, so suffices to prove the inequality for y E [-1, 1] in which case it simplifies to
a² )リ < log (1 + ay + 2.8a|yl)
ay(1 1 -²) (3
(5)
We first show the y 2 0 case. Since a > we have ay 2 0. Substituting ay + x above yields the following inequality, which we show for x 2 and E (0,3.12]:
x +
(I3 +xx22 S log (1 3.8x)
2
The term x² + 3x. is nonnegative for x 2 0, and thus the left hand side is increasing in a. Thus it suffices to prove the inequality for the maximum value of 3.12, and all 2 O.
As above, we prove this by pointing out that both sides are smooth functions for 2 O, so we take their derivatives and set them equal to each other, which yields a cubic equation in x. Our inequality takes its extreme values at either a positive root of the cubic, or at the boundary value x = 0; we thus confirm the inequality in these cases to prove it in general.
We now show the y S case.
We point out that the left hand side of Equation 5, -y(1--y)) o )y, is increasing in y at y = O, convex for sufficiently negative y. and can only transition from convex to concave once. Meanwhile, the right hand side, log (1 1.8ay), decreasing everywhere for y S 0, and concave everywhere.
Let c be the location where the cubic function any(1 - -²) - (3 - - )y² transitions from convex to concave. For those y in the (possibly empty) interval [c. 0). the cubic is concave sincavee-inneeeeeee it is also increasing at y = 0. it must be increasing on this entire interval. Recalling that the right hand side of Equation 5 is decreasing for y S 0, the difference between the left and right hand sides attains its maximum in the interval y E [c, 0] at y O, which is just 0, satisfying the inequality.
And for those y < c, where the left hand side is convex, then the difference between the left and right hand sides is convex, and thus its maximum must occur either at the left extreme, y = -1, or the right extreme, y = c; however the difference at y = e we already showed was at most the difference at y = 0, so overall, the maximum difference between the left and right hand sides must occur at either y = or y = As above, the y = case trivial and remains to prove the y = case. For the y 1 case Equation 5 becomes:
2²
2 - 3 < log (1 + 1.8u)
The left hand side is convex and the right hand side is concave; so we prove the inequality by numerically checking both endpoints: a = and 3.12.
38

---

All-Purpose Mean Estimation over R
Case and i 0.05: In this case we choose 0.75 and b v/3 and Equation 4 becomes
0. 0.75y(1 min(y? 1)) min S log (1 + 0.75y + (.086/y)
where 2.086 is a lower bound on /5// (-1+
V 3)
As usual, for y outside [-1, we point out that the left hand side constant while the right hand side monotonically increases, so suffices to show the inequality for y E [-1,1].
For y 1, [,,, we trivially lower bound the right hand side by log(1 [ + 0.75y) (dropping the 2.086|yl term), and lower bound this logarithm expression with the quadratic 0.75y 0.75y². 2 The difference between the left hand side and this polynomial lower bound on the right hand side is thus -57 + (.75 v /3)y², which is negative for 4 which is below 1, and hence our inequality holds on the entire interval y E [-1, 1].
v3
Thus have shown all cases of the desired inequality.
E. Proof of Theorem 2.8
In this section, we present the proof of Theorem 2.8. We restate the theorem for completeness: Theorem 2.8. Let be a distribution with mean and variance o².
Let ji denote Estimator on input parameter ö and n i.i.d. samples from D. Also let X,, denote the sample mean. Then, fixing 8 and D and taking n + 0C, we have
Vnji B VnXa
that is, I/nii /vx,in 2x that Vnj converges to vnx, n probability. As a corollary, by the Central Limit Theorem, we have
Vnlp- - 1) A
N (0.0²)
That is, ü is asymptotically normal and efficient.
Proof. Without loss of generality, by the hift-and-scale equivariance of both Lee and Valiant's estimator and the sample mean, we assume js = O for notational simplicity, and that the variance of 1.
The second part of the theorem follows from the straightforward reasoning that, since Estimator converges the sample mean (as claimed in the first part of the theorem statement), and since the sample mean converges Gaussian (from the Central Limit Theorem), then Estimator also converges to the same Gaussian. Formally, this uses Slutsky's 's theorem and the fact that convergence in probability implies convergence in distribution. Hence it only remains to show the first part of the theorem, that Lee and Valiant's estimator converges to the sample mean probability, for fixed 8 and as n + co.
The claim that Vnp. B, Vnx is equivalent by definition to the statement that, for any fixed e >> 0,
lim P n
X, c) =0
First, recall that f differs from the sample mean by removing a total of flog weighted samples before taking the average. Thus, VnlA - Xx,I is upper bounded by e (log 5) /maxl// /n where mmax is the largest sample in magnitude (recalling that we assumed μ 0):
Vn + -(x;
(I; - x1 - min(a(x; - xk), Σ
1
(z. - k) min((((( - 1x==
Vn
F mmax Σ min(a(2; k)²,1)
39

---

All-Purpose Mean Estimation over R
Tmax Vn
log
3
Thus, the event vn x,, > implies [mmax] > cVn//((lgg 1), which we now show is an event that occurs with probability - 0 as n + oc.
We show the following claim, that the probability a single sample from D is larger than evr (log }) at most o(1/n).
Claim E.1. Fix any e and å E (0,1). Suppose we draw a single sumple X from a distribution with mean 0 and variance 1. Then,
((IX)> evi / [108 ()
1 12
=0
Here, the o-) is in the limit where e, and D are fixed, and n - co.
We prove Claim E.1 the end. Claim E.1 implies that the expected number of samples (among the drawn) with magnitude exceeding e (log 2)) is o(1) Thus, by Markov's inequality, the probability that at least one sample exceeds that threshold is also (1), showing Theorem 2.8.
We finish with the short proof of Claim E.I. Here, for generic non-negative random variable Y, we use a refined version of Markov's ss inequality that
EYLY 2 all
P(Y a)
Applying this to X² Claim E.I, we have
P x²> onn / 1og" (){ = E X²1 x2 2n / θ (ogg') 1
8 1
θ (log" 2) e2n
Since E[x²] = and c, and D are fixed, we have E [x1 [x2 2 en / (log" 1))] = o(1) as - co. Thus, the right hand side the above inequality is o(1/n), showing Claim E.1.
This completes the proof that f converges X, in probability, showing the theorem.
F. Proofs of the Folklore Robustness of Median-of-Meant.
For completeness, we provide formal proofs of Facts A.18 and A.23, two folklore facts about the robustness of the median-od of-means estimator against adversarial corruption, which we use in our proofs Theorems 2.2 and 2.3.
Fact A.18 (Folklore). For any distribution D with mean μ and standard deviation a, let X be set of n-corrupted samples from D. The median-of-means estimate K. from grouping samples into O(log 1 3 + mm)) buckets, on input X, satisfies
+ 1)
log
1 <
P
R
2
8
n
16
Proof. Let is denote the chosen amount of buckets. Choose 16(1og & + 1mm). Let μ4 denote the mean of the i-th bucket
before any adversarial corruption. Then each μ4, is independent with variance o / 16(log J + By Chebyshev's inequality,
Pl[m: - μo| 2 40 16(1og + < 16. Let d, denote the indicator variable for the event |14 - |p| I 4 16((og # +m))
then (d4) Z To By Hoeffding's inequality, IPE; d, < 9(lgg 1 + rm)] S e -4.5(log +on) < e (log a +mm) which is at
most e log i0
1 8' for large enough n. Note that for | μl 2 4a 16(log 3/ tm)) most k/2 8(log 1 + +m) buckets
can have 1p4 nl < 4a 16(log 3 +m) Accounting for the adversarial corruption, which can affect at most vyn buckets, at before adversarial corruption, which happens with
most (log & + m)) buckets can have I1 14| 5 40 16(log + +m))
probability most 8 desired.
40

---

All-Purpose Mean Estimation over R
Fact A.23 (Folklore). For any distribution D with mean y and standard deviation let X be set of n-corrupted samples from D. Assuming that rj S 2 log 3. the median-of-meant estimate v. from grouping samples into Ollog {)) buckets,
imput X, satisfies
log
1 6 22
|K pl 20 O
Proof. Let denote the chosen amount of buckets.
Choose 16log z. Let μy denote the mean the i-th bucket
before any adversarial corruption. Then each μ independent with variance ov 16log 1
By Chebyshev's inequality,
n
Pllm-- - μa] 2 40 16log S 16. Let d, denote the indicator variable for the event 1 - 11| I 40 16log then E(d,) 2 16'
By Hoeffding's s inequality, PlE; d S Glog }] S -1.5lo $ which most log 7 = 226 6 for sufficiently small 6. Note
16log at most k/2 2 Slog buckets can have 114 14 S 40
16(lng f +qa) AAcounting for the
that for |Kc μ 2 40
n
adversarial corruption, which can affect at most nmn & log 3 buckets, at most 9log 3 buckets can have 1 - 14| S 40 v 16log before adversarial corruption, which happens with probability at most zz 0 as desired.


Reviews:
[{"review_id": "eCnTrD41YU", "reviewer": "Reviewer_aQTr", "summary": "This paper can be seen as a follow up for the seminal work of Lee & Valiant (2022), which proposed an optimal mean estimator for distributions over the set of real values, i.e. $\\mathbb{R}$. Based on that, this paper further shows that the mean estimator of Lee & Valiant (2022) is ``all-purpose'', that is, it is robust to an $\\eta$-fraction of corruptions under the strong contamination model; meanwhile, for heavy-tailed distribution with bounded $z$-th moment ($z\\in(1,2)$), it has optimal estimation error comparing to a lower bound in Devroye et al. (2016). Futhermore, it also shows that all estimators with similar error guarantees imply the neighborhood optimal, hence solving an open question raised in Dang et al. (2023). Finally, the paper also proves that the estimator is asymptotically normal and efficient, further supporting its performance in many learning scenarios.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your appreciation of our work. To answer your question regarding high(er)-dimensional mean estimation: currently, even the construction of a 2-d mean estimator achieving the analogous guarantees of Fact 1.1 (i.e. with sharp constants) is an *open problem* in the field, so no such estimator is known at this moment. Furthermore, the neighborhood optimality notion is also only understood in 1-d. Hence, it's hard to say if our techniques will directly extend to high(er) dimensions, since our analyses do depend on the precise estimator being studied.\n\nThat said, asymptotic normality should be easiest to prove for any eventual 2-d mean estimator with sharp constant guarantees, since it's a much easier guarantee than Fact 1.1-style results. Also, we speculate that our low-moment analysis of the 1-d Lee-Valiant estimator can plausibly extend to 2-d (or constant-d), if the eventual 2-d estimator subsumes the 1-d Lee-Valiant estimator and is also naturally analyzed via the maximin linear programming games capturing Chernoff Bounds (cf Section 6.2).\n\nAbout the broader impact of our analysis: while we hope other authors will be intrigued by our results and try to prove analogous results in other settings, the techniques in our paper are very tailored to the specifics of the estimator---for the sake of a tight analysis. Let us know if there are more specific aspects of this that you might like to see discussed in the final paper.", "claims_and_evidence": "All claims are very clear with convincing evidence.", "methods_and_evaluation_criteria": "The method, or the algorithm, follows from prior work. The main contribution is the theoretical analysis for robust settings.", "theoretical_claims": "The theoretical theorems and lemmas, proof ideas, look sound to me. The algorithm remains unchanged. The paper aims to show that even when the algorithm learns from a corrupted set of data samples $\\tilde{X}$, an important ``influence parameter'' $\\tilde{\\alpha}$ calculated based on $\\tilde{X}$ will be lower bounded, hence upper bounding the influence from the corrupted samples.", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "This work solves an important problem by extending the performance guarantees of the mean estimator Th proposed by Lee & Valiant (2022) to robust mean estimation literature. More importantly, it shows that the nice feature of the optimality in leading constant terms of the error rate still carries over to the robust setting.", "essential_references_not_discussed": "Sufficiently discussed.", "other_strengths_and_weaknesses": "The paper brings very strong theoretical guarantees for robust mean estimation in one-dimensional space. It provides insights for the optimality of the estimator proposed by Lee & Valiant (2022) and median-of-means. The theoretical analysis and discussion look sound to me and the paper is well written.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "Can you comment on the broad impact of the analysis for the estimation of heavy-tailed distributions? In addition, if these techniques are applicable to higher-dimensional estimation?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "pHOxeTFtgY", "reviewer": "Reviewer_eHht", "summary": "This paper concerns the problem of estimating the mean of i.i.d. real-valued samples. \nThe authors studies an estimator due to Lee & Valiant 2022 and show that this estimator enjoys several properties not known before. \nThese include\n- optimal robustness against adversarial outliers\n- optimal accuracy for heavy-tailed distributions \n- optimal adaptation to unknown distributions", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive review and questions. Here, we answer the questions raised.\n\n**Thm 2.2 vs 2.3**: The difference is indeed subtle, but neither theorem implies the other, and since different readers might consider one or the other \"more natural\", we included both, to avoid leaving readers with lingering questions. (We consider Theorem 2.2 as being more natural; but 2.3 is more similar to what has appeared in prior literature.)\n\n**Line 146-149**: Thanks for catching the typo\n\n**Neighborhood Optimality**: Yes, we unfortunately had to make the conscious choice to omit the full definition, given the submission page limit. The definition is rather subtle, and is an adaptation of \"local minimax\" from the statistics literature. Essentially, the notion means \"local admissibility\" or \"local Pareto efficiency\" --- the performance of an estimator is neighborhood optimal if, even after we restrict attention to the \"local neighborhood\" of a distribution $D$, no other estimator can outperform our estimator simultaneously on all distributions in that neighborhood. We will include the definition (including the choices of local neighborhoods) to the main paper if accepted, using the extra page space.\n\n**Convergence equation**: we use the notation $X \\to Y$ to mean $|X - Y| \\to 0$ as you pointed out. We originally thought it is a reasonably common notation, but we are happy to further clarify in the paper to remove ambiguity.\n\n**Beyond 1-d**: Currently, even the construction of a 2-d mean estimator achieving the analogous guarantees of Fact 1.1 (i.e. with sharp constants) is an *open problem* in the field, so no such estimator is known at this moment. On the other hand, Lee and Valiant have a different paper named \"Optimal Sub-Gaussian Mean Estimation in Very High Dimensions\", which studies the regime where the \"effective dimension\" of a distribution is much much larger $\\log^2 1/\\delta$, and they yield $1+o(1)$-tight estimation error. The robustness of that estimator is basically trivial to analyze, although the extra error term is different from the $\\sqrt{\\eta}$ term we get in 1-d: that other estimator does not handle low-dimensional distributions well, and the $\\sqrt{\\eta}$ term from data corruption is a \"low-dimensional phenomenon\".", "claims_and_evidence": "All claims come with rigorous proofs.", "methods_and_evaluation_criteria": "NA", "theoretical_claims": "I didn't check the proofs in the appendix.", "experimental_designs_or_analyses": "NA", "relation_to_broader_scientific_literature": "NA", "essential_references_not_discussed": "NA", "other_strengths_and_weaknesses": "1. I'm not sure I understand the difference between Theorems 2.2 and 2.3. \nBesides the technical nuances in $\\delta'$ vs. $\\delta$, what's the fundamental reason to prove one in addition to the other?\nThey seem to have essentially the same quality given that neither $222$ in Theorem 2.2 nor $135$ in Theorem 2.3 is expected to be sharp.   \n\n1. Line 146-149 \"Comparing Theorem 2.2 with Theorem 2.3, the former asks for a failure probability $\\delta' > \\delta$, but correspondingly has a smaller sub-Gaussian error term (since $\\log\\frac{1}{\\delta'} < \\log\\frac{1}{\\delta}$)\". \nDo you mean \"latter\" instead of \"former\" since there is no $\\delta'$ in Theorem 2.2.\n\n1. After reading the first 8 pages, I'm still confused about what neighborhood optimality means. \nIt was not really defined in Definition 2.5. \nI suggest the authors formally define this somewhere in the main text. \n\n1. The convergence equation $\\sqrt{n} \\hat{\\mu} \\to \\sqrt{n} \\bar{X}$ in Theorem 2.8 and elsewhere is inaccurate since the RHS is $n$-dependent. \nDo you mean something like $|\\sqrt{n} \\hat{\\mu} - \\sqrt{n} \\bar{X}|\\to 0$?", "other_comments_or_suggestions": "NA", "questions_for_authors": "1. Unless I missed it, this paper doesn't seem to discuss at all what happens for mean estimation beyond *one dimension*, which is a natural question to ask and potentially more relevant to modern statistics. \nRobustness guarantees for high-dimensional mean estimation can be quite hard to derive. \nEven defining the notion of median is nontrivial, as briefly alluded to in the paper. \nI wonder if anything in the spirit of Lee & Valiant 2022 can be (or has been?) done.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "YrOuCsDqfg", "reviewer": "Reviewer_UmEB", "summary": "This paper considers the problem of designing \"all-purpose\"mean estimation algorithms that can be applied to a variety of scenarios. To be specific, the authors consider the estimator by Lee & Valiant (2022). This algorithm, is previously shown to be optimal in the standard finite variance and i.i.d. setting. This paper, further give the result that Lee & Valiant (2022)'s algorithm is optimal in other settings. To be specific, they proved that the algorithm is robust to data corruption, and also optimal for distributions that have infinite variance.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive review of our paper. We answer your questions below.\n\n**Beyond 1-d**: Currently, even the construction of a 2-d mean estimator achieving the analogous guarantees of Fact 1.1 (i.e. with sharp constants) is an *open problem* in the field, so no such estimator is known at this moment. On the other hand, Lee and Valiant have a different paper named \"Optimal Sub-Gaussian Mean Estimation in Very High Dimensions\", which studies the regime where the \"effective dimension\" of a distribution is much much larger $\\log^2 1/\\delta$, and they yield $1+o(1)$-tight estimation error. The robustness of that estimator is basically trivial to analyze, although the extra error term is different from the $\\sqrt{\\eta}$ term we get in 1-d: that other estimator does not handle low-dimensional distributions well, and the $\\sqrt{\\eta}$ term from data corruption is a \"low-dimensional phenomenon\".\n\n**Other setups, the phrase \"all-purpose\"**: We chose to study adversarial corruption, distributions with infinity variance, and asymptotic normality, because these are compelling and fundamental notions of performance that one could hope for in a mean estimator. These properties are the focus of widely known or folklore results on mean estimation. Thus we are motivated to ask whether all these properties can still hold in addition to the sharp performance guarantee achieved by the recent Lee-Valiant estimator. There are (of course) many other settings that are worth considering, for example what if the samples are not i.i.d., but many desiderata might be incompatible with the extremely strong 1+o(1) performance guarantee of the Lee-Valiant estimator. As for the name \"all-purpose\", we also weren't completely happy with the naming -- we wanted to convey the meaning of \"swiss-army knife\" but without the clunkiness of the phrase. We welcome any suggestions!", "claims_and_evidence": "The proof of robustness to corruption is given in Thm 2.2 and 2.3. Optimality under infinite variance is proven in Theorem 2.4.", "methods_and_evaluation_criteria": "No evaluations is involved by this work. It is a learning theory work.", "theoretical_claims": "I didn't check the proof correctness in detail.", "experimental_designs_or_analyses": "No experiment in this work.", "relation_to_broader_scientific_literature": "Not sure how this work is related to broader scientific literature.", "essential_references_not_discussed": "No missing essential references.", "other_strengths_and_weaknesses": "Strengths: Proof the optimality of the previously proposed algorithm under some scenarios. The optimality results is important to the community. \n\nWeakness: The term “all-purpose” may be an overstatement. I am not sure why the robustness under certain scenario can be regarded as \"all=purpose\".", "other_comments_or_suggestions": "I would suggest that the authors give more explanation of why the robustness under the mentioned scenario can be viewed as \"all-purpose\". It might be good to emphasize why those scenarios are important.", "questions_for_authors": "The studied estimator is 1-d. Is there multi-dimensional estimator proven, or shown in experiment, to be efficient?\n\nIs there any other setups that worth considering? Other than contamination and infinite variance?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "WA6rAdTUnB", "reviewer": "Reviewer_vs1w", "summary": "Mean estimation is the following simple task: given samples from a probability distribution D on R, estimate the mean mu of D. Although mean estimation has been studied since the dawn of time, various elementary and fundamental questions about mean estimation are still being tackled. \n\nA natural goal is to obtain optimal *nonasymptotic* errors. That is, for a given number of samples n and error rate delta, design an estimator hat(mu) which satisfies an inequality of the form Pr( |hat(mu) - mu| < error ) \\geq 1-delta, for as small a function error(n,delta) as possible. If D is Gaussian, the empirical mean gives the best possible estimator, but since the real world isn't really Gaussian, we would like to obtain estimators with such guarantees, ideally with the function error(n,delta) matching the one we would get for Gaussian D, under much weaker assumptions on D.\n\nLee and Valiant in 2022 constructed a mean estimator which obtains the optimal error(n,delta) under only the assumption that D has bounded variance. Their estimator even adapts to the variance of D.\n\nWhile the Lee-Valiant estimator is highly robust in the sense of tolerating a broad class of underlying distributions D, the question this paper addresses is whether it is robust in other senses, in particular:\n\n-- adversarial contamination/data poisoning -- what if a small fraction of the sample are chosen adversarially?\n-- nonexistent variance -- what if even the variance of D does not exist?\n\nThe authors prove that the Lee-Valiant estimator satisfies strong robustness guarantees in both these senses. First, they show that it is resilient to an \\( \\eta \\)-fraction of adversarially corrupted samples in the strong contamination model, achieving the optimal error bound \\( O(\\sigma \\sqrt{\\eta}) \\). Second, they establish that when \\( D \\) has only a finite \\( z \\)-th moment for \\( z \\in (1,2) \\), the estimator attains the minimax-optimal error rate, matching known lower bounds. Third, they show that it satisfies *neighborhood optimality*, meaning that it adapts to the structure of the underlying distribution and achieves the best possible error beyond worst-case guarantees. Finally, they prove that the estimator is asymptotically normal, converging efficiently to the true mean as the sample size grows.\n\nThese results show that the Lee-Valiant estimator is not just optimal in the standard setting but also robust across a range of challenging conditions, making it a strong candidate for practical use over alternatives like median-of-means or trimmed means.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your appreciation of our work!", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "no", "experimental_designs_or_analyses": "n/a", "relation_to_broader_scientific_literature": "Robustness is statistics is a long running theme with thousands of publications. Prior works have developed estimators which achieve all of the guarantees of the lee-valiant estimator separately, but as far as I am aware no single estimator is so far known (until this work) which has the sub-Gaussian error guarantee (including the right constant), robustness to adversarial contamination, and minimax optimal rates under weaker moment assumptions.", "essential_references_not_discussed": "n/a", "other_strengths_and_weaknesses": "The paper is well written and elegantly argues for the usefulness of the Lee-Valiant estimator.", "other_comments_or_suggestions": "non", "questions_for_authors": "non", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: **Summary.**

The topic of this paper is 1D robust mean estimation. Lee and Valiant (2022) proposed an estimator for the mean which is optimal and tight down to the leading constant for the class of distributions with finite variance (algorithm reported in Estimator 1 and guarantee reported in Fact 1.1.).

In this paper, the authors demonstrate through careful analysis that the estimator (without any modification to it):

* Achieves optimal guarantees in the adversarial contamination model.

* Achieves optimal guarantees for the class of distributions with finite $z$th moment for $z \in (1,2)$ (specifically, it achieves the lower bound in Devroye et al., 2016 up to constants).

* Achieves so-called “neighborhood optimality” (Dang et al., 2023).

* Is asymptotic normal and efficient (in the finite variance, uncontaminated setting).

Following the above, the authors deduce that the Lee and Valiant’s estimator is “all purpose”, that is, it should be the one used in practice, in lieu of more classical algorithms such as median-of-means or trimmed mean.

**Strengths.**

* The problem is of strong interest to the ICML community (and the more general ML community).

* No soundness concerns were raised, and the writing is clear.

* Novelty: this is the first time an estimator was found to satisfy optimality to the leading constant in the finite variance setting, and is at the same time robust to adversarial contamination and optimal for distributions with infinite variance.

* The main claim that the estimator is “all purpose” is convincing; this is particularly important for practioners, as it removes the need to make additional assumptions on their data.

**Weaknesses.**

The presented analysis may not extend to higher dimensions (aQTr , eHht, UmEB); however, devising optimal estimator in dimensions higher than one is known to be a hard problem in the field.

**Discussion and reviewer consensus.**

There is strong consensus among the reviewer that the paper should be accepted.

**Additional remarks.**

Some minor points were raised by eHht, I recommend the authors to include more details on neighborhood optimality in their final version if the paper gets accepted.

**Overall evaluation.**

This is a serious contribution to the ICML program; I recommend acceptance.
Decision: Accept (oral)