Optimality in Mean Estimation: Beyond Worst-Case, Beyond Sub-Gaussian, and Beyond $1+\alpha$ Moments
Authors: Trung Dang
Jasper C.H. Lee
Maoyuan Song
Paul Valiant
Venue: NeurIPS 2023 poster (2023)
Keywords: mean estimation
instance optimality

Abstract: There is growing interest in improving our algorithmic understanding of fundamental statistical problems such as mean estimation, driven by the goal of understanding the fundamental limits of what we can extract from limited and valuable data.
The state of the art results for mean estimation in $\mathbb{R}$ are 1) the optimal sub-Gaussian mean estimator by [Lee and Valiant, 2022], attaining the optimal sub-Gaussian error constant for all distributions with finite but unknown variance, and 2) the analysis of the median-of-means algorithm by [Bubeck, Cesa-Bianchi and Lugosi, 2013] and a matching lower bound by [Devroye, Lerasle, Lugosi, and Oliveira, 2016], characterizing the big-O optimal errors for distributions that have tails heavy enough that only a $1+\alpha$ moment exists for some $\alpha \in (0,1)$.
Both of these results, however, are optimal only in the worst case.
Motivated by the recent effort in the community to go "beyond the worst-case analysis" of algorithms, we initiate the fine-grained study of the mean estimation problem:
Is it possible for algorithms to leverage *beneficial* features/quirks of their input distribution to *beat* the sub-Gaussian rate, without explicit knowledge of these features?

We resolve this question, finding an unexpectedly nuanced answer: "Yes in limited regimes, but in general no".
Given a distribution $p$, assuming *only* that it has a finite mean and absent any additional assumptions,
we show how to construct a distribution $q_{n,\delta}$ such that the means of $p$ and $q$ are well-separated, yet $p$ and $q$ are impossible to distinguish with $n$ samples with probability $1-\delta$, and $q$ further preserves the finiteness of moments of $p$.
Moreover, the variance of $q$ is at most twice the variance of $p$ if it exists.
The main consequence of our result is that, no reasonable estimator can asymptotically achieve better than the sub-Gaussian error rate for any distribution, up to constant factors, which matches the worst-case result of [Lee and Valiant, 2022].
More generally, we introduce a new definitional framework to analyze the fine-grained optimality of algorithms, which we call "neighborhood optimality", interpolating between the unattainably strong "instance optimality" and the trivially weak admissibility/Pareto optimality definitions.
As an application of the new framework, we show that the median-of-means algorithm is neighborhood optimal, up to constant factors.
It is an open question to find a neighborhood-optimal estimator *without* constant factor slackness.

Optimality in Mean Estimation: Beyond Worst-Case, Beyond Sub-Gaussian, and Beyond 1 + a Moments
Trung Dang
Jasper C.H. Lee University Wisconsin-Madison jasper lee@wisc.
The University of Texas Austin addtrung0cs. utexas edu
Maoyuan Song
Paul Valiant
Purdue University maoyuanrs@gmail. com
Purdue University pvaliant@gmail com
Abstract
There is growing interest improving our algorithmic understanding of fundamen-- tal statistical problems such mean estimation, driven by the goal of understanding the fundamental limits of what we can extract from limited and valuable data. The state of the art results for mean estimation in R are 1) the optimal sub- nub-Gaussian mean estimator by [Lee and Valiant, 2022], attaining the optimal sub- Gaussassi error constant for all distributions with finite but unknown variance, and 2) the analysis of the median-of-meat -ea-- algorithm by [Bubeck, Cesa-Bianchi and Lugosi, 2013] and matching lower bound by [Devroye, Lerasle, Lugosi, and Oliveira, 2016), characterizing the big-O optimal errors for distributions that have tails heavy enough that only 1 + a moment exists for some these results, however, are optimal only in the worst case, Motivated by the recent effort in the community go "beyond the worst-case analysis" of algorithms, we initiate the fine-graine study of the mean estimation problem: Is it possible for algorithms to leverage beneficial features/quirks of their input distribution beat the sub-Gaussian rate, without explicit knowledge of these features?
(0, 1). Both of
We resolve this question, finding an unexpectedly nuanced answer: "Yes in limited regimes, but general no". Given a distribution p, assuming only that it has a finite mean and absent any additional assumptions, we show how to construct a distribution 9n.6 such that the means of p and q are well-separated, yet p and q are impossible to distinguish with n samples with probability - 8, and further preserves the finiteness of moments of p. Moreover, the variance of is most twice the variance of if it exists. The main consequence of our result is that, no reasonable estimator can asymptotically achieve better than the sub-Gaussian error rate for any distribution, up constant factors, which matches the worst-case result of [Lee and Valiant, 2022]. More generally, we introduce new definitional framework to analyze the fine-grained optimality of algorithms, which we call "neighborhood optimality", interpolating between the unattainably strong "instance optimality" and the trivially weak admissibillty/Paree optimality definitions. As an application of the new framework, we show that the median- offiinn-f--masss means algorithm is neighborhood optimal, up constant factors. It is an open question to find neighborhood- optimal estimator without constant factor slackness.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Introduction
Mean estimation over I is one of the most fundamental problems in statistics: given n i.i.d. samples from some unknown distribution p. how do we most accurately estimate the mean of p, with probability 2 1 - 6, from the n samples? The conventional approach is to take the sample mean, the empirical average of the samples, as the estimate; this is justified by the law of large numbers, which says that that in the limit of having infinitely many samples, the sample mean will converge to the true mean. However, has been long known that while the sample mean is optimal for estimating the mean of well-behaved distributions such as Gaussians, it is sensitive to the presence of outliers in samples drawn from heavy-tailes distributions, for which the sample mean estimator can have abysmal performance.
The classic median-of-means estimator [e.g. [e.g.NNY8] NY83 JVV86 AMS991. independently invented several times in the literature, was proposed to mitigate the sensitivity of the sample mean. Its accuracy on any distribution p with finite variance is up to constant factors as good as the accuracy of the sample mean on Gaussian with the same mean and variance as p. In other words, the error is of sub- Gaussian rate. The past decade has seen renewed interest across computer science and statisties in understanding the limits of the mean estimation problem. In one dimension, the current state of the art is 1) for distributions p with finite variance og. the recent mean estimator proposed by Lee and
( log //n, which is tight even in its constants, up to a + (1) factor, and 2) the work of Bubeck, Cesa-Biant Bianchi and Lugosi [BCL13] showing upper bounds matching the lower bounds of Devroye, Lerasle, Lugosi and Oliveira [DLL016,, which show that for heavy-tailed distributions having only a 1 + ah moment for some a E (0, 1). the median-of-meane algorithm in fact still achieves the optimal accuracy up to a constant factor. Both of these results, however, are optimal only in the worst case, meaning that [LV22 DLLO16) have optimal performance with respect the class of distributions with the same 2 or + t1 moments respectively; but estimators may do better than these bounds on particular input distributions.
Valiant LV22 has sub-Gaussian rate op- (V2 + o(1)) (v2+
The natural and immediate next question is, even though Gaussian distributions are the hardest case in mean estimation, and thus sub-Gaussian performance is worst-case optimal: can one do better, at least for some "easier" distributions? Can we develop "instance-dependeen"" algorithms and analysis techniques? Is it possible for algorithms to leverage beneficial features/quirks of their input distribution to beat the sub-Guub Gaussian rate, without explicit knowledge of these features and without losing robustness to heavy-tails?
We resolve this question and show an unexpectedly nuanced answer: "Yes in limited regimes, but in general no".. For some distributions, even of can beat the sub-Gaussian bound, but only for a limited parameter regime per distribution- namely. if the number of samples is not too large (Proposition 14). In general however, we show a strong and comprehensive negative result, Our main technical result (Theorem 2) is fine-grained indistinguishabiliy construction: given a distribution p, assuming only that p has a finite mean and absent any further assumptions, we show how to construct a distribution 9n.6 9n.8-in in terms of sample complexity and failure probability 8 such that p and are impossible to distinguish with n samples, with probability 2 21-5, and yet the means of p and q are well-separated by some function (p)) (stated formally in Definition 1}. This in particular implies that no n-sample estimator with failure rate can simultaneously have error less than (p) on both p and q. The function (p) is such that, for p with finite variance, if we take
log ///n - 0, we have (p) - 2((pp/ /1og /n), showing that no estimator can asymptotically outperform the Sab-Gausiian rate for both p and qn,5 simultaneously. Additionally, as shown in Section 2.1 the construction of 9n.5 is conservative, such that < at all points, meaning that g dp
has a finite 1 + th moment whenever does, and furthermore, of < 20 whenever of exists. Thus, the same indistinuusshability result still applies even if we further require the existence of higher moments for both p and q-
The key message of our paper is that such lower bounds are to be circumvented, through identifying additional favorable distribution structure for the mean estimation problem [1 This observation has already led further work in the area, guiding the design of new algorithm that outperforms
"Favorable distribution structure", in particular, cannot mean just the existence of higher moments, since indistinguishabiiity construction applies even in this case.

---

the Lub--aussian rate via symmetry assumption. Gupta et al. [GLP23] show that, assuming the distribution is symmetric about its mean, one can achieve sample and instance-dependen Fisher information rates for mean estimation, which can be significantly better than sub-Gaussian rates. We view our paper and the [GLP23] result together as call arms to explore other structural assumptions that can sidestep our lower bound construction.
Beyond the asymptotic implications in the finite variance setting, our results fully characterize mean estimation in the regimes of I) finite variance and finite samples, and 2) infinite variance, and indeed, even when no + at moment exists for any constant a >> In particular. we give a simple, yet very general re- re-analysis of the median-of-meet -eanss estimator on distributions only assumed to have finite mean. Its estimation error on distribution p, with probability 1 6 over n samples, ((,,,6 (p)) (Proposition 14), matching our main indistinguishabiiity result up to constants (Theorem
1.1 Our Results and Techniques
Our main result is an indistinguishabiliy result, for every distribution p. which serves as mean estimation lower bound. Ideally, given the motivation earlier in the introduction, we want to show that the sub-Gaussian rate is lower bound, but such bound cannot hold in finite samples. To see this, consider distribution which has < 1/n mass that is extremely far away from the mean, and which contributes the majority of the variance, yet only minuscule portion of the mean. Given only n samples, with high probability we will not see any samples from this mass, and so mean estimation can in fact be "effectively" performed on the conditional distribution without this outlier mass. The conditional distribution has essentially the same mean as the original, yet has far smaller variance, thus allowing to beat the sariiacee-eepndentt sub-Gaussian rate. We thus start this section by defining an error function 6n.5 (p) for each distribution p (Definition 1). capturing the estimation error expect for p, taking into account that we intuitively expect both algorithms and lower bounds to ignore outlier mass. Our main result will then construct, for every distribution p, a new distribution that is indistinguishable from p using n samples, yet has mean difference least 6,,6 from p.
Definition Given a (continuous) distribution p with mean up and a real number t E [0, 1]. define the t-trimming operation on p as follows: select a radius such that the probability mass in (wp - T; Up + +r] equals I; then, return the distribution p conditioned on lying in 1زpp - Y, Up + r].
Given n. and 6, define standard trimmed distribution P to be the 0.45 log -trimmee version of p. When ō is implicit, we may denote this as py We also define the error function en,
4.5log 1
1pp- Mp: + Pr.
Theorem 2 shows that, given any distribution with a finite mean, it is possible to construct a distribution 6n.6 such that 1) p and 9 are indistinguishable under samples with probability 1 8, yet 2) the means of p and q are separated by ((c,,,())) The construction of 9.,6 is also such that dg/dy= < 2, showing that, in many senses, "y does not have more extreme tails than y".
Theorem Let n be the sample complexity and be the failure probability, and recall the definition of the error function 6u.5 from Definition 1) Assume that there is a sufficiently small constant which
upper bounds both log and 6. Then for any distribution p with a finite mean Pp there exists distribution q + p with mean Pg such that:
114 Hpl 32 (p))
log(1 - (p. 2
1 log 48
2m
dg dp
2
In particular, by standard fact Fact Ty on the squared Hellinger distance, this implies that and are indistinguishable using n samples, with probability 1 1-6 8. Furthermore, since dg ap < 2, we have
o < E, - = < E,[([ (((x--,,)91 2 -,,))]= 20²
Using a standard
reduction, it follows from the main theorem that there can be no estimator that can achieve error at most En (p) simultaneously on p and 5-
3

---

Corollary 3 Let n. be the sample complexity and ó be the failure probability, and recall the definition of the error function C., fr.6.frmm Definition 1 Given a distribution p with finite mean, consider the construction of q in Theorem 2 Then, there is no estimator that achieves error less than 64 Cn,6 (p) over n samples with probability 1 1 8, for both p and q.
We contrast this lower bound with more standard impossibility results that have the flavor: "one cannot estimate the mean to within o (v2 + o(1)) / /oog //nn, since there are a pair of Gaussian distributions of variance 0, separated by twice this distance. that are indistigguishable in n samples up to probability 8". As opposed to showing the indistinguishabiliyy of "nice" distributions like Gaussians, we instead show that for any distribution p of interest (with finite mean), we exhibit generic construction of a hard-to-distee -odittiiiit "partner" distribution g, of rather different mean, yet all of whose tails are comparable to those of p.
For reference, the definition of Hellinger distance and the standard fact we reference above are:
Fact 1 Consider the squared Hellinger distance between two distributions p and q, defined as
(a(p. = 2 (v ddg)²
If the two distributions and are such that log (p(p.))) distinguishes p and 9 with probability 1 5 using samples.
2
1 log 46, then there no test that 2n
Complementing the specific construction of q and analysis of its properties, we also introduce a new and general definition framework, speaking to the challenge of capturing "beyond worst case analysis" in this nuanced setting. In Section 3 we motivate and introduce this notion. Broadly, we want to capture the intuition of "instance-optimal" algorithms,, namely, an algorithm that performs as well on the given distribution p as any algorithm customized towards yı however, this definition is unattainably strong in our setting. By contrast, weaker notions such as "admissibility" or Pareto-efficiency too weak to rule out trivial and effectively useless estimators. We introduce a new notion which we call "neighborhood optimality" that subtly blends between these notions. See [Section 3 for details. /Appendix A.3 also gives an in-depth discussion comparing neighborhood optimality with the more commonly-used notion of local minimax [AD20b] AD20aa HLY21). While the two definitions look superficially similar, we show in the appendix using a general proposition and a concrete example-that our new notion is a stronger and also more robust definition in the context of mean estimation.
As an application of this new framework, we show in Section 4hthat the standard median-of-meant esti- mator is neighborhood optimal up to constant factors. is an open question to design a neighborhood- optimal estimator which does not have such constant factor slackness.
1.2 Open Questions
We briefly discuss few open questions and future research directions raised by our results.
Optimal constants for neighborhood optimality estimators- in theory and in practice While median-of- enjoys neighborhood optimality as we show, the hidden multiplicative constants constants in our analysis are not tight. The median-of-meant estimator is also not recommended in practice due its large asymptotic variance [Min19). The goal thus is to show that more modern estimators, for example [LV22], also enjoy neighborhood optimality. Ideally, such analysis would yield optimal constants.
Other distributional structures for aveiding asymptotic sub-Gaussian lower bound As men- tioned in the introduction, we view our paper as a call to arms to investigate distributional structures and assumptions that allow mean estimators to go beyond the sub-Gaussian error rate. The paper of Gupta al. (LPP23] is the first work aiming cireumvent our lower bounds showing the benefit of symmetric distributions for mean estimation. The hope, and challenge, is to find other realistic settings that enable mean estimation algorithms beyond the sub- Gaussian benchmark.
High--iimnsional Neighborhood Optimality Generalizing the framework and results of this paper to the high-dimensiooall setting is a compelling direction for future work. In high dimensions,

---

for a distribution with covariance Σ, the corresponding sub-Gaussian rate for mean estimation under the lg norm is e v V tr(E) + lo] 2)) We conjecture that, like in the I-dimensional case, mean estimators cannot outperform the sub-Gaussian rate in the asymptotic regime as n + op. More specifically, we conjecture that whenever a distribution p has a finite covariance, a version of Theorem holds for some (p) that approaches the high-dimensional sub-Gaussian error as + o0, up to constants. Further, for distributions without finite covariance matrix, it is open to fully characterize the Instance-by-instaiee error rates in high dimensions, and finding an analog of (p) that characterizes both the upper and lower bounds.
1.3 Related Work
The mean estimation problem has been extensively studied, even in one dimension. In the classic setting where the underlying distribution is assumed have finite but unknown variance, the median- of-means algorithm, independently discovered by different authors (e.g..VV80 AMS99 NY83). was the first to achieve sub- Gaussian rate to within a constant factor in the high probability regime. The seminal work of Catoni [Cat12] reinvigorated the study of mean estimation, by proposing the first estimator which attains Sab-Gaassian rate tight to within a + o(1) factor, but his estimator requires a-priori knowledge of the variance, a bounded 4th moment assumption that allows accurate estimation of the variance. This work further showed that the sub-Gaussian rate a lower bound on the optimal estimation error. Subsequent work by Devroye et al. (DLLO16) proposed a different estimator, also attaining 1 + o(1)-tight which has additional structural properties. Recent work by Lee and Valiant [LV22] constructs an estimator achieving sub-Gaussian rate to within a 1 + o(1) factor for any distribution with finite but unknown variance, absent any knowledge assumption bounded 4th moment assumption.
Gaussian rate under the bounded 4th moment assumption,
In the more extreme setting where the underlying distribution may have infinite variance, but is guaranteed to have finite (but unknown) + at moment for some E (0, 1), Bubeck et al. [BCLI3) proved an upper bound on the error achieved the median-of-means estimator, and Devroye et al. (DLLOT6) showed matching lower bound up to constant factor.
See the in-depth survey by Lugosi and Mendelson [LM19] on sub-Gaussian mean estimation and regression results prior to 2019.
"Beyond worst-case" analysis is theme of much recent work and attention in the computer science literature. See [Rou21] for examples of "beyond worst-case" analyses in various contexts in computer science and statistics including, for example, combinatorial algorithmic problems, auction design, and hypothesis testing. Both of the above tightness results in mean estimation are in the worst-case, and in this work, we present (to our knowledge) the first "beyond worst-case analysis" results for the mean estimation problem. We emphasize also that our results are applicable even to distributions with finite mean, but without any finite + th moment for any a O.
The notion of admissibility in statistics and the analogous concept of Pareto efficiency serve as a main motivation for our definition of neighborhood optimality, introduced in [Section 3) They are well- studied notions in their respective fields, to the extent that they are standard topics in undergraduate courses. See for example the textbooks by Keener (Kee10) and Starr (Sta97] for expositions.
The other main definitional motivation is the notion of instance optimality, which falls under the umbrella of "beyond worst-case analysis" in the computer science literature. We highlight some of the uses of instance optimality in statistical contexts. Valiant and Valiant (VV17) gave the first instance optimal algorithm for the identity testing problem (in total variation distance) for discrete distributions. In later work [see VV16), the same authors showed how to instance-optimally Iearn discrete distributions (in total variation distance).
different line of work studies "instance optimality" in the context of mean estimation with differen- tial privacy (DP) [e.g..[ADe |.D20) AD20a HLY2T). Specifically, these works address the problem of differentially-Pee privvttlly estimating the mean of a data set, where the data set itself (or equivalently, the uniform distribution over the data set) is the instance. In the DP setting, instance optimality is also not satisfiable by any estimator for the same reason as the non-DP setting, since the hardcoded estimator is always differentially private. They instead use local minimax (or locally worst-case) notion of optimality (although in these works this notion sometimes also called "instance optimality"; we take care to distinguish the two definition styles in this paper), where the particular localityneighborhood
5

---

structure they use is restricted to data sets that have Hamming distance from the instance, since this a key component in the definition of DP. The local minimax notion of optimality is closely related to our notion of neighborhood optimality. We compare and contrast the two notions in Appendix A.3 and explain why our definition is stronger and more appropriate for our context.
2 Proof of main results
This section gives the construction and proof of main result, TThooemm 2
Our construction of q from p will have 2 cases, depending on which of the terms in the definition of the error function 6n,5 dominates. Recall that the error 5n,5(p) is the sum of two terms involving the "trimmed" distribution ph: (ignoring constants) 1M4 - Pys and pn; v /log 1/ //n; intuitively, the first term measures to what degree has an "asymmetric tail", and the second term measures the variance of p in its central region.
First, consider the case when the first term is larger, namely, 1pp- Mp; > op% 4.5log t/n. Our goal in constructing q is to maximize 1ppp - Meg subject to g being indistinguishable from p. Given that 1) the mean of PM is already far from the mean of p by assumption in the case analysis, and 2) p and Ph are by construction hard to distinguish since only a small amount of probability mass was trimmed from p make Ph we simply need to construct g as a carefully chosen convex combination of and p,, and show that this indeed satisfies all the properties in the definition of on.
Next, for the remaining case when the variance term yy V 4.5log //n is larger than the remaining term Hp Mp: 6n.5 we now want to construct q such that the mean shift |M, - Hyy is large
compared to the variance term opt v 4.5log //n, while ensuring that is indistinguishable from p. To achieve this, we create q that "skewed" version of p, scaling the probability density by linear function 1 + az, where larger means more mean shift between and but also means that it is easier to distinguish q from p. Technically, we truncate the linear scaling factor + ax to lie between 0 and 2. so that will satisfy Condition 3 of the requirements for presented in our main theorem. [Theormm 2. the probability mass might not be after this skewing, so we might need to normalize; also, we point out that for the purposes of Thhorem we do not care whether the mean of q is shifted to the left or right of p (corresponding to choosing a positive or negative parameter a), and the construction makes use of this choice.
Definition 4 (Construction of indistinguishable pair) Given a distribution p. we construct dis- tribution q in a shift-and sifft-and-scale invariant manner as follows.
Case 1: 1pp Mpp > Jp; V
4.5 log
Define X = 3 and construct to be the weighted average
q= Ap (1
X)p
Case 2: 1pp- Mppl S 0pz V 4.5
log
Without loss of generality, assume that pyp O. Let parameter
a be the solution in the interval 0,
log
to the below equation characterizing the
mean shift, as guaranteed by Lemma 23
Appendix B
(-x)dp+ dp a f x² dp + 10
log 1 8
dd 8 pr
We construct two non-unit measures q" ,q, defined as scaled versions p. as dp (z) + min(1, max(-1, (nx(-11,aaz)) F.x)). By symmetry the masses of at and q sum to 2; thus one of 4+,9 has mass at least 1. Construct by choosing that one of qq.q" and downscaling it by a factor be E [3, 1] such that the total probability mass is indeed
dg
In the rest of the subsections, we will prove all the properties of the construction needed by Theorem We observe that the non-unit measure q is "symmetric" to qt. in the sense that its first moment shift

---

from is identical but of the opposite sign. Therefore, most of the analysis below will assume the q" case without loss of generality.
2.1 Checking that de dp
<
It is straightforward to check that dg ap
by construction, for both cases of Definition
Lemma Suppose there is a sufficiently small absolute constant that upper bounds log 1 Given
distribution p. if we construct as in Case I (the large |ppt. Hpl case) in Definition 4 then dg
s 2.
Let the support Pr be [eet Fright]- At x & [Tieft, P. we have Otherwise, E [Ziett Fright]. we have
Proof.
A
3/1dp < 2.
dp dp
dp
dg dp
Adp + A) dpt
Ap
(by the definition of p.) S
dp
dp
0.45log
where the last line follows from the fact that À is a constant (0, 1) and log à is assumed to be bounded by some sufficiently small absolute constant.
Lemma Suppose there is a sufficiently small absolute constant that upper bounds log Given distribution p. if we construct as in Case (the small |pp; Hpl case) in Definition 4 then dg S 2.
at x)) for some value of at, and the right hand side is always between 0 and 2; proven similarly, have 0 dg constructed by scaling down one of and gt, we also have dg
Proof. For qt, we have dg (x) = 1 +
dp I 2. Noting that is
dp
< 2.
2.2 Bounding the squared Hellinger distance
We consider each case of the construction in Definition 4 separately. We first bound the Hellinger distance between p and the q constructed in Case of Definiion 4 (when Mp Mp; is large).
Lemma 7 Suppose there is sufficiently small constant that upper bounds both and 5. Given a distribution p. if we construct as Case (the large [P'; Hpl case) Definition 4 then log(1 d 4)) 2 2n. log 45.
Since Case of the construction of in Definition 4 linearly interpolates between and-a very slightly trimmed version of p. namely- P". the resulting distribution q remains close to p; the calculation is in An/ppdddiix B. The next lemma bounds the squared Hellinger distance of and in Case of Definition 4 (when [pp Myg small).
Lemma 8 Suppose there is sufficiently small constant that upper bounds both log 2 and 8. Given a distribution if we construct as in Case 2 (the small 1pp: Hpl case) in Definition 4 then log(1 di 4)) 2 2n
1 log 46.
The proof (see Appendix B.1 uses a technical lemma to relate dr 4) to du (p. g+) or dir(p, qT), and then uses linearization of the definition of Hellinger distance to relate it to the mean shift. between and qt or which is bounded by Definition 4
2.3 Lower bounding [Pg Mpl
We show the lower bound separately for the two cases in the construction of q Definition 4 The small Mpp; Hpl case is direct corollary of Lemma 23 which bounds the mean shift in this case.

---

Lemma Suppose there is a sufficiently small constant that upper bounds both log and 6. Given a distribution if we construct as in Case I (the large 1pp. Hpl case) in Definition 4 then 1pg- Mp 2 (p))
Proof. Without loss of generality, assume that Mp 0. Recall that q Ap + (1 A)pt and 1/2 from Case 1 of Definition 4 Thus, 164g - ppl =lmm ppl. Furthermore, we have
(p) 1p4 Ppp + or; V 4455 log 1 from the definition of (p))(p) and IMp; - Ppp Opū V 4.5 log 1 n
" from the lemma assumption and Case of 4 which then imply that 6n,6 (p) S 2/ppp: Apl
Combining the two inequalities yields |pg - Hpl 2 (p))(p) as desired.
Lemma 10 Suppose there is a sufficiently small constant that upper bounds both log 1 and Given distribution p. if we construct in Case 2 (the small [ppt Hppl case) in Definition 4 then 1pg- Mp 2 Cn.s
Proof. Without loss of generality, let qt be the non-unit measure used to construct that is y for some E 1 1]. By the bound on b as well as the construction of qt in Definition we have lA4e - Mpl = ʃ x dd - J x dpl 2 1
by
log Additionally, we both have (
lpp; - -Mpl + pz V 4.5 Log from the definition of en, and lpp: upl S op; V /.5 log 2 from
the lemma assumption and Case 2 of Definition 4, both of which imply (p) S 20,; pm / 4.5 log 1
Combining the two inequalities above, we have that 1Mg Hpl (p).
3
Neighborhood Optimality: A New Definition Framework
Our main result is a specific and technical indistinguishabiiity result. This section aims to clarify, through a new definition framework, the optimality notion that our technical result implies.
3.1 Neighborhood Optimality
Usual notions of "beyond worst-case optimality" include "instance optimality" which is unattainably strong, and "admissibility"""Pree efficiency" from the statisties and economics literature, which is too weak. In particular, the latter notion is too weak in the sense that a trivial estimator that always outputs the same hardcoded mean estimate is actually admissible, despite being algorithmically "vacuous". We define and explain these notions formally in Appendix D
Given that neither of the usual definitions suitable for mean estimation, in this work we give a new optimality definition, which we call neighborhood optimality. We state its definition in this section, and explore its basic properties and intuition in Appendix A] including how the definition smoothly interpolates between instance optimality and admissibility. Our definition is also related to the notion of local minimax optimality, which we compare with in Appendix A.3 The differences subtle, yet, as we show in [Appendix A.3] local minimax is too weak a notion and, when instantiated inappropriately, allows for absurd bounds be proven. We thus advocate for this new optimality definition, which correctly rejects such absurd bounds. As an application of our new framework, we prove in /Section 4 that the median-of-means estimator is neighborhood optimal up constant factors. It is an open question to find a neighborhood optimal estimator without the constant factor slackness.
Let P1 be the entire set of all distributions with finite first moment over R. We say that N is neighborhood function (defined over Pt) if N maps a distribution p E P1 to a set of distributions N(p) C Pt. For the purposes of the rest of the definitions, it will not matter whether p E Np)). Similarly, an error function e maps distributions to non-negative numbers, like 6,,5 in our main result, Theorem In the later definitions, use the notations Nn.6 and 6n,6 denote their dependence on the sample complexity n and failure probability 8.
Given these two notions, we can now define neighborhood Pareto bounds with respect to Nn,5, which imposes admissibility structure within the local neighborhood N,,s (p) of every distribution p E Pt.
8

---

Definition 11 (Neighborhood Pareto bounds with respect to Nu.6) Let n. be the number of sam- ples and 8 be the failure probability. Given neighborhood function No.5 P1 + 2 we say that the error function sn,((p) ) P1 + Bg is a neighborhood Pareto bound for P1 with respect to Na. if for all distributions p PI. no estimator ji taking i.i.d. samples can simultaneousty achieve the following two conditions:
we
For all E (P) with probability - 6 over the v. ii.d. samples from 4, li Pul S (n)
With probability 1 8 over the i.i.d. samples from p. já Hpl cn,s(p).
Note the strict inequality in the second bullet: namely, it is impossible to "beat" the error function over an entire neighborhood, where "beating" is defined as attaining the error function over the neighborhood, and performing strictly better than the error function for The above two bullet points essentially capture admissibility within the local neighborhood (p) U {p}-compare with Definition and the definition requires admissibility within every such local neighborhood, over every possible p.
The neighborhood (p) in a neighborhood Pareto bound can be interpreted as the set of distri- butions 'near p" which, if an estimator performs well on distribution p. then we should reasonably expect or want it to perform well also on all the distributions in the local neighborhood &p)
Using the notion of neighborhood Pareto bounds, we estimators, which are estimators whose performances are matched by neighborhood Pareto bounds.
define n-neighborhood optimal
Definition 12 ((K, Neighbbboood optimal estimators) Let K. > 1 be multiplicative loss factor estimation error, and т > be a multiplicative loss factor in sumple complexity. Given the parameters K, >> 1, sumple complexity failure probability 8 and neighborhood function Nn.s. a mean estimator ji is -eeee-hnhhooooo optimal with respect to Nn.6 if there exists an error function (p) such that min(Cn/r,5 ((D): (p)(()) is a neighborhood Pareto bound" and jt gives estimation error most k <n,6(p) with probability at least ō when taking n i.i.d. samples from any distribution E P1.
As basic example and sanity check, in Appendixx E hardcoded mean estimate cannot be n-nceihborhood optimal with respect to our chosen neighborhood function (Definition 15 in Secciin 4) for any
we show that any trivial estimator that outputs
3.2 Indistinguishability implies a neighborhood Pareto bound
Even though it might not look obvious how prove neighborhood Pareto bound from its definition, we show that our main indistinguishabbiity result essentially implies such a bound, The proof essentially follows the straightforward estimation-to--ee -oo-ttttnnn reduction intuition, and we give it formally in Appendix A.2
Proposition 13 ("Local" indistinguishabiliy bounds imply neighborhood Pareto bounds) The error function 6n,8 is a neighborhood Pareto bound with respect to the neighborhood function Nn.6 if for every distribution E Pi, there exists a distribution g E Nn,s(p), with * such that Up - 1g 2 (p) + (g)(()) and it is aeformatioontheorrtiicee impossible distinguish p and with probability 5 using samples.
Median-of-Means is Neighborhood Optimal
To apply our new definitional framework, we choose a reasonable neighborhood function Nr,5 and show that the median- -e-ms algorithm is neighborhood optimal with respect to this choice.
In Anrpppdix C we give the following (straightforward) re- re-amalysis of median-of means, which will form the upper bound part for neighborhood optimality.
Whiiee it is intuitive to expect that an error function decreases in n. it might not be true in general. Indeed, the definition of (p) we use in the main result is not necessarily monotonic. This is why we use a min in the neighborhood Pareto bound requirement.

---

Proposition 14 Consider distribution p with mean Me- a sample size n. and a median-of-means group count 4.5log,, 3. Let Pi, be the 2.45 log 3 --rrmmed distribution from Definition 1 and Mya and Op, be the mean and standard deviation of Pr respectively. Then, the median ooaatto----manss- estimator has error 11p
Mrg. 30pp V 4.5log i except with probability at most 8.
We can now discuss the neighborhood choice for the corresponding neighborhood Pareto bound. Recall that, intuitively, neighborhood optimality is asking "how well can our algorithm do on p given that we also want our algorithm do similarly well on neighborhood of p"; and thus, the smaller we choose the neighborhood, the stronger the resulting theorem. We thus define the neighborhood of p to consist of distributions that are similar or similarly nice in 4 different ways:
Definition 15 (Choice of neighborhood function N,,5 in Theorem 16) Define Nn,((p) to be the set of distributions q E Pi such that
1. (n) _ (0)
2. log(1 d4 9)) 2 bл log 48
3. [ng - Mpl S kn,
4. For all R,
dg ap (z)
As a basic sanity check, we show in Appendix that trivial, hardcoded estimator cannot be neighborhood optimal- this is mostly a consequence of Property 3 above. See Appendix El for formal statement and proof. We then show:
Theorem 16
Let n be the number of samples and 8 be the failure probability. Assume that there is a
sufficiently small constant which upper bounds both log 3 and 8.
Consider the neighborhood function N,.5 of Definition 15
Recall the error function defined in Then, for some sufficiently large constant
Defimition I as 6,,5 1,4p 1pp pp V the error function 1/2 minn(nn/388 6n,6) is neighborhood Pareto bound with respect to No.5-
4.5log 2
T2
Combined with Proposition 14 4Astaaing that the median-of ootonn-----a--ns-- means estimator has error function (fn,s) this implies the median-of- estimator is (K, (K,3)--ed -)e--nnghbooooood optimal with respect to Nn.6-
The main component of the proof is construction of q. and the accompanying analysis of Theorem 2 ssooiing that is well behaved in several senses. We specifically show Lemma 17 a slight extension of Theorem 2]
Lemma Let be the sample complexity and the failure probability, and recall the definition of En, from Definition 1 Assume that there is sufficiently small constant which upper bounds both log 1 and 8. Then for any distribution p. there exists distribution q # p such that the mean of is
82 (p) different from the mean of p. and log(1 di 4)) 2 1 log 46, and g E Nn,s(p).
2n
See Appendix for the proof Lemma I7 We will now use Lemma 17 to prove Theorem 16
Proof of Theorem 16
By Proposition 13] it suffices to show that, for every distribution Pi. there exists distribution 9 E (p) with q * p such that 14p Mggl 2 x (minn(Cn/3.. (p)
min(tn/33. /3,5 6n,5 (4)) for some large constant s, and no tester can distinguish p and g with probability 1- 8 using n samples.
Given distribution p E P1. consider the distribution E sp, guaranteed by Lemma 17 Since satisfies log(1 (1 - di (p, q)) 2 1
2n log 46, by Fact 1 we know that p and q are indistinguishable with probability using n samples.
remains to check that 1pp - Mgl 2 (min((n/aa) (n. (p) + min( (n.) for some sufficiently large constant By Lemma f7 we have
|Mp Myl 2 (p),,,(p)) 2 ((Cn, (p) (p)) 2 2(Cn/3,69)) + cn)(pp) by Lemma 17
2 Mmiin(E//..5 (p) min(en./.666n.550))
which completes the proof of Theorem 16
10

---

Acknowledgements
We thank the anonymous reviewers for insightful comments and suggestions on this work. Jasper C.H. Lee is supported in part by the generous funding of a Croucher Fellowship for Postdoctoral Research, NSF award DMSS2023223 CCF-2006200 Maoyuan Song is supported in part by NSF award CCF-1910411 NSF award CCF. 2228814, and NSF award CCF-2127806. Paul Valiant is supported by NSF award CCF-2127806.
NSF Medium Award CCF-2107079 and NSF AiTF Award
References
[AD20a]
Hilal Asi and John C Duchi. "Instance-optimallty in differential privacy via approximate inverse sensitivity mechanisms". . In: Advances in neural information processing systems
33 (2020), pp. 14106-14117.
[AD20b]
Hilal Asi and John C Duchi. "Near instance-optimality in differential privacy". In: arXiv preprint arXiv:2005, 10630 (2020).
[AMS99]
Noga Alon, Yossi Matias, and Mario Szegedy. "The space complexity of approximating the frequency moments". In: J. Comput. Syst. Sei 58.1 (1999), pp. 137-147.
[BCL13] Sébastien Bubeck, Nicolo
and Gábor Lugosi. "Bandits with heavy tail". In: JEEE Trans. Inf. Theory 59.11 (2013), pp. 7711-7717.
[Cat12] Olivier Catoni. "Challenging the empirical mean and empirical variance: a deviation study". In: Ann. I. H. Poincaré PPR 48.4 (2012), pp. 1 118--1885.
[DLLO16] Luc Devroye, Matthieu Lerasle, Gábor Lugosi, and Roberto Oliveira. "Sub-Gaussian mean estimators". In: Ann. Stat 44.6 (2016), pp. 2695-2725.
[FLNOI] Ronald Fagin, Amnon Lotem, and Moni Naor. "Optimal aggregation algorithms for mid- dleware". In: Proceedings of the twentieth ACM DEMMOD-SIGACT-SIGAE symposium on Principles of database systems. 2001, pp. 102-113.
[GLP23) Shivam Gupta, Jasper C.H. Lee, and Eric Price. "Finite-Sample Symmetric Mean Estimation with Fisher Information Rate". In: To appear in Proc. COL.7'33. 2023.
[HLY21]
Ziyue Huang, Yuting Liang, and Ke Yi. "Instance-optimal Mean Estimation Under Differential Privacy". In: Advances Neural Information Processing Systems 34 (2021), pp. 25993-26004.
[JVV86]
Mark R. Jerrum, Leslie G. Valiant, and Vijay V. Vazirani. "Random generation of combinatorial structures from a uniform distribution". In: Theor. Comput. Sci 43 (1986),
pp. 169-188.
[Kee10]
R. W. Keener. Theoretical Statistics: Topics for Core Course. Springer Texts in Statis- tics. Springer New York, 2010.
[LM19]
Gabor Lugosi and Shahar Mendelson. Mean estimation and regression under heavy-
tailed distributions a survey. 2019.
[LV22]
Jasper C.H. Lee and Paul Valiant. "Optimal Sub-Gaussian Mean Estimation in R._ In:
2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS). IEEE. 2022, pp. 672-683.
[Min19]
Stanislav Minsker. "Distributed statistical estimation and rates of convergence in normal approximation". In: Electron. J. Statist. 13.2 (2019), pp. 5213-5252.
[NY83]
A.S. Nemirovsky and D.B. Yudin. Problem Complexity and Method Efficiency in Optimization. Wiley, 1983.
[Rou21]
Tim Roughgarden. Beyond the worst-case analysis of algorithmss. Cambridge University Press, 2021.
[Sta97]
Ross M. Starr. General Equilibrium Theory: An Introduction. 1997.
[VV16]
Gregory Valiant and Paul Valiant. "Instance optimal learning of discrete distributions". In: Proceedings of the forty-eighth annual ACM symposium on Theory of Computing. 2016. pp. 142-155.
[VV17]
Gregory Valiant and Paul Valiant. "An automatic inequality prover and instance optimal identity testing". " In: SIAM Journal on Computing 46.1 1 (2017), pp. 455.
11

---

A Interpreting Neighborhood Optimality
In this section, we derive basic properties and intuitions about the definitions of neighborhood Pareto bounds and neighborhood optimality.
In particular, we show that neighborhood optimality is notion that smoothly interpolates between instance optimality and admissibility, depending on what neighborhood function is used to instantiate the definition. We also show sufficient condition for proving that error function is a neighbor- hood Pareto bound (Proposition 13). Lastly, we discuss and compare neighborhood optimality and the notion of local minimax optimality that has appeared in the literature.
A.1 As an interpolation between instance optimality and admissibility
Recall that Detinitions II and 12 both require specifying the neighborhood function. Our first observation is the monotonicity in the definition of neighborhood Pareto bounds, in the sense of the following straightforward proposition which we state without proof.
Proposition 18 Suppose the neighborhood functions No.5 and N₁,5 are such that (p) S Na, for all p. Then, if a given error function 6n,5 is a neighborhood Pareto bound with re- spect to Na.5. then en is also neighborhood Pareto bound with respect to No a.."
We can extend this monotonicity observation from neighborhood Pareto bounds to neighborhood optimal estimators.
Proposition 19 Suppose the neighborhood functions Nn.5 and N₂, are such that N (p) S &(,(p) for all p. Then, if fa is k-neighborhood optimal estimator with respect to Nn,5- then is also k-neighborhood optimal with respect N Na,
To understand how the set of neighborhood optimal estimators vary as we change the neighborhood function, we examine the two extreme examples as special cases, where Nn.5 = 0 and Nn,8 =\t Pt.
Let us first consider the case when the neighborhoods are all empty. In this case, Definition II simplifies requiring a neighborhood Pareto bound 6n,5 to be such that, for every distribution p E P1. no estimator á (specialized to p) can have eπror strictly less than (x, with probability 1- 8 over samples from p. straightforward to check that any estimator that is x-neighborhood optimal with respect to empty neighborhoods is equivalent to being instance optimal (Definition 27 in Appendix D) up to a x factor, which as explained before, is impossible to achieve. The only possible neighborhood Pareto bound with respect to empty neighborhoods is 6n,6 = 0, since every distribution has trivial estimator that outputs its mean hardcoded.
At the other extreme, consider the case where all the neighborhoods contain all the distributions in Pi. Here, Definition 1T simplifies (after taking a contrapositive)
requiring neighborhood Pareto bound e to be such that, for every distribution E P1,, if an estimator has error at most 6 (q) with probability 1-6 for all distributions q & p E PI, then it must have error at least (p,)(p) with probability 1 ó for distribution p. It is again straightforward to check that, by definition, an estimator 1-neighborhood optimal with respect to the constant-Pp neighborhood function if and only if the estimator is admissible in Pi DDfinition 28 in Appendix D) As explained before, admissibility is somewhat weak notion on estimators, and includes trivial hardcoded estimators.
Combining these two extreme cases and the monotonicity propositions, we have shown that neighbor- hood optimality is notion which interpolates between instance optimality and admissibility. More technically, neighborhood optimality can be viewed as a homomorphism mapping the partial ordering of neighborhood functions (the ordering induced by set inclusion) the partial ordering of sets of estimators (also ordered by set inclusion).
We remark that, while it may be tempting to view neighborhood Pareto bounds as lower bounds, and neighborhood optimality as exhibiting an estimator whose error function matches a lower bound up to a constant factor, such an interpretation is actually not valid. The reason is that, depending on the choice of the neighborhood function, given an estimator with error function upper and a
6,5
neighborhood Pareto bound p. it can be the case that on some distributions p E Pi. we have pareto (p) 2,.6
upper (p): namely, these Pareto bounds should not be viewed as lower bounds. A simple
12

---

example is the previous case where the neighborhood function is P1, in which case it is straightforward to check that for any (hardcoded) constant fi R. the error function < (p) = j /4pl is neighborhood Pareto bound. For any distribution p whose mean is extremely far from the constant jt, the median-of of-means algorithm will have accuracy better than 1 Mpl- Because of such examples, we take care not to refer to our bounds as lower bounds, but instead call them Pareto bounds in this paper.
A.2 Indistinguishability implies a neighborhood Pareto bound
We restate Proposition 13 from Section 3.2 here for clarity, and give the proof of it below.
Proposition 13 ("Local" indistinguishabbiityy bounds imply neighborhood Pareto bounds) The error function En.6 is a neighborhood Pareto bound with respect to the neighborhood function N,. if for every distribution p E 1ı, there exists a distribution g E Nn,,(p), with q F p. such that 1pp Mg 2 Ga, (p) + (n,5(4) and it is iiformation-theortiicle impossible to distinguish and with probability 8 using n. samples.
Proof. Suppose the "if" condition in the proposition is true, yet, for the sake of contradiction, that 6n,6 is not neighborhood Pareto bound. Then, there exists distribution p E P1 and estimator taking n iidd. samples such that
For all distributions q E Nn,s(p), with probability 6 over the n i.d. samples from q.
j - Mayl S (1))
* With probability 1 1-6 8 over the n i..d. samples from p. 1/ Hpl < (n)
By the proposition condition, there must exist some distribution E (p)) such that 1 Mby 2 (p) + (q) and it is iioommtion-thhorretilllly impossible to distinguish p and q with probability 1- using samples. However, we can construct the following distinguisher: compute a mean estimate f. return p if f is within (p)(p) of Up and return q otherwise. By our assumption on f., this distinguisher will succeed with probability at least - 8, thus contradicting the proposition statement.
We remark that the proof of Proposition 13 13jcttally establishes a stronger result, that the error function 6n,6 neighborhood Pareto bound for the singleton neighborhood N (p) {((p)) where g(p) is the q constructed from p according to Proposition 13 Recall that the monotonicity property of Proposition says that neighborhood Pareto bounds are stronger for smaller neighborhoods; thus this bound for singleton neighborhoods implies the corresponding bound for any larger neighboorhoods
Nn,8 C n.5
A.3
Comparing with local minimax optimality
Here, we compare our definition of neighborhood optimality with the notion of local minimax optimality from prior literature. At a high level, neighborhood optimality imposes admissibility within each local neighborhood, whereas local minimax optimality imposes minimax optimality within each local neighhorhood. We argue that local minimax is too sensitive to the choice of neighborhood structure, although the two definitions are different in a rather subtle way and perhaps difficult to see at first glance. We concretely illustrate their differences via 1) proposition showing that for practical purposes, local minimax bounds are weaker notion than neighborhood Pareto bounds and 2) a simple example choice of an "inappropriate" neighborhood structure, such that an intuitively absurd local minimax bound holds for this neighborhood structure, but the same bound fails to satisfy the definition a neighborhood Pareto bound. Together, these results show that neighborhood optimality is stronger and more robust notion than local minimax optimality.
For ease of comparison, we first phrase the local minimax definition in the same form as our definition of neighborhood optimality.
Definition 20 (Local minimax bounds with respect to N..s) Let n be the number of samples and 8 be the failure probubility. Given neighborhood function Nn.8 Pi 2P, we say that the
error function (n)(p) Pi + BJ is local minimax bound for Pı with respect to Nn. if for all
13

---

distributions p E Pi, there is no estimator ja such that for all distributions E ( U {p), when given n i.i.d. samples from q. the estimator ja achieves 1 pql < c,, with probability 6.
Definition 21 (s-locally minimax estimators) For a parameter K. 1, sample complexity n. failure probability 8 and neighborhood function functioon Nn.6, mean estimator fa is K- K-locally minimax with respect to Ns,5 if there exists an error function En. such that 6n,((p) is local minimax bound, and ja gives estimation error at most K (n,(()) with probability at least 1 - 5 when taking n i.i.d. samples from any distribution p E P.
The notions of local minimax bounds and locally minimax estimators also have the same monotonicity properties as neighborhood Pareto bounds and neighborhood optimal estimators, analogous to Prropo Sitions 18 and 19 When the neighborhood function N,.6 is constantly equal to the empty set, local minimax optimality again coincides with instance optimality. Furthermore, local minimax bounds can be proved using indistinguishability arguments, via a reduction analogous to toPrrpssiiion 13 to minor changes in parameters.
However, one key difference between the two styles of definition arises when we consider proving neighborhood Pareto bounds or local minimax bounds using such indistinquishabiiity arguments. Recall from /Section 3.2 by relying on onooopooiiionn 13, the main technical result of this paper is to show that for every distribution p. there exists a "neighbor" ((p) whose mean is far from p. with ((p) satisfying suitable structural properties (so that q(p) E Nn,(p) in our eventual choice of No.s in Definition 15), such that p and y cannot be distinguished with probability 1 - â using n samples. As explained in |Seettion 3.2] this proof strategy effectively proves a neighborhood Pareto bound over the singleton neighborhood function N N (p) = {q(p)}. J. Thus, it is meaningful to compare neighborhood Pareto bounds and local minimax bounds when the neighborhoods are singletons. The following proposition shows that, up constant factor of 2 in the error, a neighborhood Pareto bound on singleton neighborhoods implies a potentially much larger local minimax bound.
Proposition 22 (For singleton neighborhoods, local minimax bounds are weaker than neigh- borhood Pareto bounds) Let be the number of samples and 5 be the failure probability. Consider a neighborhood function N such that for all p E PI. (P) is a singleton set containing a distribution g (p)) + p. Suppose en,5 is a neighborhood Pareto bound with respect to No,6 and that (p) > 0 for all p P1- Then, the function 2/2 (p) + En,5 (q(p)) is a local minimax bound with respect to No Note that the above function is lower bounded by M(max(( (n,s()) & ((((((())) and can be much larger than (p))
Proof. Suppose for the sake of contradiction that (p) tn, (g(p)) is nor local minimax bound with respect to No but 6,,5 is a neighborhood Pareto bound.
We observe that, since Gr,5 is neighborhood Pareto bound, it must be the case that for every distribution p E PI, we have 1Mp- - -Pyl 2 sn,((p) + <n,s(((())) Otherwise, for any distribution not satisfying the above, there
trivial hardcoded estimator that outputs a number such that lā - Ma/ < <x,,5((())) and jā Hpp < (p,)
Since (p) + 6n, 5nn66n( (g(p) is not a local minimax bound, there exists some distribution p and some estimator A such that 1) with probability at least 1 1- 5 over n samples from p. Íp 12-14p Mpl < ] (C., (p) + (g)(((())) and 2) the same for q. However, we already know that [1, Mll c,,s(p) + Cn (g(p). which implies that we can use the mean estimator ja to distinguish and with probability 1 1-6 over n samples. Using this distinguisher, we construct new estimator ji' which outputs Hlp if the distinguisher thinks the distribution is p. and n4 otherwise. This new estimator já' has O error with probability 1- 8 over n samples, which contradicts the assumption that cn,5 is a neighborhood Pareto bound and that sp) > O.
The notion of local minimax bounds is therefore (potentially much) weaker than the notion of neighborhood Pareto bound we introduce in this work. We now show that this can actually happen, if we do not choose the neighborhood structure carefully. We give concrete example of neighborhood structure in which an absurdly large local minimax bounds holds, but this bad bound is (rightfully) rejected by the definition of neighborhood Pareto bounds.
As representative simple example, consider p = (0, 1) and define its neighborhood as a singleton set (p) bq NVnn, 1)} where 77 < 1 is small enough that and g are indistinguishable with
14

---

samples. Now define the neighborhood of q to also be a singleton set . (g)) = { where is constructed by moving a tiny bit of mass of q such that My 7) + 10", but q and q' are indistinguishable. Consider an absurd error function <(p) n/2. E(q) 10 /2, which far too large for since we expect O( /log //n) estimation error for q (e.g. by using standard uub-Gaussian
mean estimator). Yet, e is a local minimax bound (c.f. Definition 21) under the neighborhood function N, since, given two indistinguishable distributions p and g. no estimator can get eπror less |pp - My /2. On the other hand, we can also check that Definition 12 rejects this absurd error function from being a neighborhood Pareto bound. To see this, consider the neighborhood of p. consisting only of g. Consider the hardcoded estimator jı always outputting O: f violates the condition of neighborhood Pareto bounds since its error for p is ر/ Upl 0 < n/2 and for q is j Mal 7 < 10
This example, together with Proposition 22 show that neighborhood optimality is a more robust notion than local minimax optimality when being applied inappropriately chosen neighborhood structures. While we believe our paper uses an "appropriate" neighborhood structure, we still emphasize the importance of introducing definitions that are properly resilient to absurd instantiations. For this reason, we have chosen to present our results in this paper as a neighborhood Pareto bound and optimality.
B Remaining proofs for Theorem 2
In Definition 4 we claimed that there exists parameter satisfying certain conditions in Case 2 of the construction. We formally show that this parameter exists in the following lemma.
Lemma 23 Let be the number of samples and and 8 be the failure probability, and assume that log & is bounded by some sufficiently small absolute constant. Let p be any distribution such that
ppp Mpp
S pr V
log
and we assume that Pip = 0 without loss of generality. Then, the equation
{ x dp
1 dp
log 8 n
(-z)
pp
8
always has solution
0,
log
opt
Proof. We first point out that, for the (potentially) non-unit measure a+ defined by dg dx- 1 + min(1, max(-1, ar)), the left hand side of the equation equals the difference between the first moments of qt and p. Namely,
dp
[ rdda* - dp) = L x min(1, max(-1, ax)) dp = - (-x) a / x² dp 2ddp J x
Our goal is to find 0,
log
such that this first moment shift equals o V
log - n
0p
Because min(1 max( -1, ar)) is increasing in and continuous in the first moment shift is also increasing and continuous in a. When 0 then q² p. and the shift clearly equals Thus
max(-1,
suffices for us to show that the first moment shift is at least } op: /
/og when aph
log t The
lemma then follows from the intermediate value theorem.
Consider the construction of p", in Definition and let r be the trimming radius of p. We do case analysis, either
log
1/r
log
1/r.
5% 12
15

---

Vuee 1/rr At
V/aa have
Case
1
Op
a
x dp
2 a
x² dp since a S 1/r
[ -op)) dp since the mean squared error is minimized the mean
a
dp
log
2
a
pi.
since over [-r, we have
dp
0.45 S 2 for suff. small
log
"
1 1
log
by definition of
PL.
log
=
2
Pm
log &
Case
1/r: Ata
we have
7
(
[ (-x)
f xdp since
(-x) x) dp
x xdp 2
2 r
ddp
111-r.1
r 0.45log
by the definition of p, and r
log
= 0.45r a onn
log x
2 0.450pa
since a 2
Summarizing, in either case, at
log y we have that the first moment shift between qt and
p is
(-x)dp+aa / x² dp 1
xc
log
log
ddp 2 min 5. 0.45
on
>
8
7
yielding the lemma.
B.1 Bounding the squared Hellinger distance
We restate Lemmas
and
8 from Section 2.2 for clarity, then give the proofs of them below.
Lemma Suppose there is a sufficiently small constant that upper bounds both log and Given distribution p. if construct in Case I (the large |pp: Mpl case) in Definition 4 then log 46.
log(1 (p. 4))
Proof of Lemma 7. Since Case 1 in the construction of q Definition 4 linearly interpolates between p and Pr,, with interpolation constant À 1' thus the Hellinger distance between and can be exactly computed as function of 1) 0.45log 1 which determines the masses of p, y inside and outside of p's trimming interval, along with 2) the ratio dy inside and outside p's trimming interval, ap
which also depends only 0.15 and X. We then bound this (essentially) univariate expression.
16

---

Without loss of generality, assume that Up 0, and let the support of pn be [-r,r]. Recall the
construction of q in Case of Definition 4 q Ap (1 A)p At x & [-r, we have dp (æ) X.
Otherwise, at x: E [-r, r], we have de (x)
dp Ap +
(x) by the definition of p. 0.15
1-1
dp
which is in turn equal to (1 - 0.45log $ )/(1 0.451og +))
Given the above equalities, we can explicitly calculate 1 - dli 9) as follows.
1 - (p 1) = / Vdpdg
- dppqq
/
v
dp
0.15log 8
-J JEXI-rV
Vxd++
dp
0.45log 1
[-rpel
n2
VĀ- 0.45log 1
1 0.15log
(1-
0.45log $
by the definition of ph
0.4blog 1
n
v 0.45log 1
0.45log à 0.45log
(1
A n
n
We now show technical lemma lower bound the quantity in the last line.
Lemma 24 For any A e 1 1] and 3 [0, 1], we have
V + (11 (3)(1 - 3) ((A-1)B
Proof. Take the second derivative of the left hand side with respect to 3, giving (01-8)9/(11>10110
(A-1)2
which is negative. On the other hand, the right hand side e(A-1),8 is an exponential in 3 and hence convex in 3. Therefore, left hand side minus right hand side is concave, meaning that the difference is minimized at either 3 = 0 or 3 = 1. At = 0, both sides are equal to 1. At 3 = 1, the left hand side vÀ whereas the right hand side is e^ A The inequality vā 2 ed-1 is true for any À E [3 1]. 0
Using this lemma, we have shown that
VĀ. 0.45log
A 0.45log 1
(1
0.45log 1
log(1 - gp. = log
0.45log 1
(1 X) 4.5
4.5 log d
2 (A 1)
n
10n
0.9 log 48
2 (1 A)
since 5 is sufficiently small
n
2 2n
log 46
by the definition of X = 3/4 and that log 46 < 0
Lemma 8 Suppose there is sufficiently small constant that upper bounds both 3 and 8, Given a distribution p. if we construct q as Case 2 (the small [pp; Hpl case) Definition 4 then log(1 dp 4)) 2 2n. log 45.
Proof Lemma Recall that given a distribution p, Case 2 of Definition 4 we construct by picking one of the two non-unit measures qt and g which has mass 2 I. Without loss of generality (via an appropriate reflection of p with respect to μp), let gt be this non-umi unit measure,
17

---

then use bg* We use a to denote the corresponding solution to the equation in Definition 4 nnte that a 0).
To relate di (p. 9) to (p. we will need to use the following lemma concerning the general- ization of squared Hellinger distance between distribution and non-negative measure with mass bigger than 1.
Lemma 25 Given distribution p. and non-negative measure 9 with 8 2 1 probability mass, define the (extended) squared Hellinger distance as (p. [ (vdp- - vdq)². Then, we have
(p q) 2 (p,
Proof. For any 2 0, we have
di (p.(())))) 04) = / (Vdp- Vbdd)²= 2
(fidp- 2V8 / Vāpdq+ + b' ldg)
2
= 2 1 - 2/8 / Vappq+ + b)
V'
The derivative in // is therefore
1 ( I Adpdg
2
V/
The derivative is greater than 0 if and only if
V
Vdpd(by)
The right hand side is the Bhattacharya coefficient between two distributions, and by, and hence upper bounded by 1 as standard fact. The left hand side on the other hand is at least for all 8' E [b, 1]. Therefore, di (p, d'q) is an increasing function in /' for the range 6' E [b, 1], meaning that (p, di (p, bq), desired.
We can now upper bound the squared Hellinger distance as follows.
(p. 9) (p, (p,bbt) b)
by Lemma 25 since 1 2 1 :
di (p,
1
(Vdp )
2
1
1 v min(1, max_,,,, dp by definition of q*
2
1
min(1, (ar)?) dp since the inequality holds pointwise
2
1
1 dp + 2
2 dp
+
1 dp
2
1
dp
2² dp
2
a
a
x))
dp
a
2 dp
+
dp
2
log
since satisfies the equation of Definition 4
2
n
log
log 1 à
pp
since a is upper bounded by Definition
71
Opt
16
n
18

---

log. 16n
log
4n S
since is sufficiently small
Observe that for sufficiently small 2 > O, we have log(1 2) 2 to be sufficiently small, have
-2z. Since and log are assumed
1 log
log(1 di (p.
44
log 48
2n
2n
C Error analysis for median-of-mean.
In this section, we present the matching upper bound result of the performance of the median-of of-ne estimator. We restate the estimator and the proposition for the sake of clarity.
Algorithm Standard Median-of- of-Means Estimator
Inputs: n independent samples { from an unknown distribution p; and confidence parameter 8
1. Divide the samples into 4.5log à groups with equal size.
2. Compute the mean of each group.
3. Return the median of these 4.5log means.
Proposition 14 Consider distribution p with mean Hp, sample size n, and median-of-means group count 4.5log g. 0r; be the mean and standard deviation of p", respectively. Then, the median-of-mean estimator has
Let pr, be the 0.45 9.45 n log -trimmed distribution from Definition 1 and Pey and
error 1pp - Mp; -3pp V 1.5log {
except with probability at most ö.
To prove this proposition, we use the following lemma:
Lemma 26 Defining Ph to be the 0.A5 4-trimmed version of p. then the empirical mean of n n 4.5log z samples from p is within 3 "2 of Per, except with prohability at most 5*
Proof. Recall ph is but with 0.45 log 1 probability mass trimmed (and then scaled up to have total mass 1). Thus the probability that any of the n' 4.5log samples from are not in the support of PA is at most 10 by the union bound.
Conditioned on the event stated above not happening, we can view the sampling process drawing n' samples from p with mean μy; and standard deviation dyp- The standard deviation of the mean of these n samples is thus Tni By the Chebyshev inequality, the probability of the sample mean being more than 3 times its standard deviation from the true mean is at most J.. Thus the empirical mean is within 3 "ri of Mp;. except with probability at most J
Vn
Combining these two case, where the event happens and where it does not, the overall probability of the empirical mean of n samples being more than Tr /n
away from the true mean Po; is at most
TU
to Lemma 26 for each group of the estimator, and with the fact that the mean of p My, we arrive conclusion that median-of-meant will have error 1ppp Mpa 30p;
Proof of Proposition 14 Substituting in n' 4.5log f
1.5log t except when at least half of the 4.5log & groups have error
30pp 4.5log i Since the probability of each mean having big error is most \ by Lemma 26 the overall failure probability is thus at most the probability that 4.5log coins each of bias will yield majority heads. Letting & = 4.5log 1, we bound this probability with Chernoff bound, which
19

---

for our choice of t 2 0. yields (ge² + )
- v. The upper bound is minimized at t = log 4,
attaining its minimum of ($)*. Since k = 4.5log f. this probability is less than 8.
D Definition of instance optimality and admissibility
This paper needs suitable notion of optimality beyond the worst case. One natural definition to consider the notion of instance optimality (see Definition 27 in (Appendix D from the computer science literature [FLNOT]. which intuitively states that "our algorithm performs at least as well on any instance p as any algorithm customized to p". However, it immediate that no algorithm A can satisfy such definition in our setting for every distribution p. there is a trivial estimator that is hardeoded to output the mean μp without looking at any data; and this hardcoded estimator beats any other estimator A. On the other hand, the statistics literature commonly uses a different natural notion called admissibility (see Definition 28 in Appendix D also analogous to the economics notion of Pareto efficiency), which states that "no algorithm can perform at least as well as algorithm, and strictly outperforms our algorithm on some instance." " While instance optimality is impossible to satisfy, admissibility has the dual problem of being somewhat too weak and too easy to satisfy: trivial estimator which outputs a hardcoded mean estimate estimate-ignoring any samples-is admissible.
In this short appendix. we give the formal definitions of instance optimality and admissibility for mean estimation over
Recall the notation Pi for the set of distributions over R with a finite mean.
Definition 27 (s--nnstance Optimality in Mean Estimation) For a parameter K. >> 1, sample com- plexity n and failure probability 8, mean estimator is whose error function is C,,6 is-instance optimal if. for any distribution p E Pi, every estimator fi' has error at least Cn,5 with probability 1 over ii.d. samples from p.
As we remarked in the introduction, there is no instance optimal mean estimator for any >> O, since for any estimator i. we can find distribution on which it has some nonzero error, and thus ja cannot be instance optimal, because it performs infinitely worse on in comparison with the trivial "hardcoded" estimator that always outputs He without looking at any samples.
Definition 28 (Admissibility in Mean Estimation) For sample complexity and failure probability a mean estimator j whose error as a function of the distribution is Ep.)()), is called "admissible" there no estimator jl with error function e',55 such that
For every distribution p E Pı, (. S <n,((p)
There exists a distribution p" E Pi such that "n" < kno(p")
E
Hardcoded estimators are not neighborhood optimal
We perform the basic "sanity check" for the neighborhood structure of Definition 15, and formally show that under this neighborhood definition, no trivial hardcoded estimator is n-neighborhood optimal for any K > 1.
Proposition 29 Consider mean estimator Aa which ignores any of its inputs and always outputs the value 3 for some / E R. For any parameter k. > 1, f&g cannot be k-neighborrhod optimal with respect to Nn. defined in Definition 15
Proof. For the sake of contradiction, suppose P.g is k-neighborhood optimal. The error function cg for Aツ simply c)(p) Pp 3). Since Ae x-neighborhood optimal, there must exist some error function parreoo > e such that pareto is a neighborhood Pareto bound with respect to Nn.s. We will reach contradiction by showing that parrto cannot be neighborhood Pareto bound.
Pick an arbitrary distribution p whose mean Pp is 3 + (1 + x2) sp). This is always possible since 6n,5 (p) is translation-invaria in p. By Property 3 of Definition 15 and the reverse triangle inequality, any q sp) has mean Mg such that Eg(g) [4g 3 x² <enn)(p)) Since pareto
20

---

is neighborhood Pareto bound, there must be no estimator js such that for every distribution q E Nn.6(p) (p). ji Hy < ( with probability
over samples from q: otherwise. we would have 1 - Myl (p) I My 3 1 (g)) I p (g). which contradicts c being neighborhood Pareto bound. However, we can simply pick jí = Myy the trivial estimator that outputs Uup always. Again by Property offDeiinition 15 we have for every q E Nn.s(p) U {p} that |14 - ji] IMy 1lp (n,a(p) < Ken,, (D) for 1. We have thus reached the desired contradiction.
F Remaining proofs for Lemma 17
In Snecttio 2] we have already shown that the construction of in Definition 4]satisfies properties and 4 of Definition 15] To complete the proof of Lemma 17, we show that q satisfies property in Appendix F.1 and property in Apppeddix F.2
F1 Upper bounding I,g Hpl
We show in this section that, for both cases in Deñiiiion 4, the construction of q such that 1/g Upl is appropriately upper bounded. We will show that [Pg Mtp I fn.((p), as part of the proof showing that q E N,,6 (p). We furthermore show other upper bounds of 114 Hpl. for example, that [Ag- Mp < if is the trimming radius for the construction of Pz from p. which will be useful for the later sections.
Lemma 30 Assuming has mean O, and is trimmed to the interval [-r,r] when constructing ph (as Definition 1), then Case (the large [py; - Uyl case) of Definition outputs a distribution q such that (1g Up I and 114g - 11pl S (p))
Proof. The distribution q constructed to be convex combination of and p%, with interpolation parameter equal to by definition. Thus [ig Ppl I à 2114p - /Apl. where this last quantity is at most & since p, is supported on [-r,r] r] and thus can have mean at most distance away from the origin. Furthermore, by the definition of (p)( we have 1kg Pol < 3 Prr - Mpl S ( D
Lemma 31 Assuming has mean O, and is trimmed to the interval |-r, -r.r) r] when constructing Pt, (as in Definition 1), then Case 2 (the small lup; -Mpl case) of Definition 4 outputs distribution q such
log log As corollary, this is further upper bounded by c
that |1a Mpl S pp. V
Additionally, if logg is upper bounded by some sufficiently small absolute constant, then g V log 1 can also be bounded by :
Proof. Without loss of generality, suppose qt is the non-unit measure constructed by Case 2 of
Definition which will be downscaled to create g. We know from Lemma 23 that | x dq
S x(dq - dp) Opp
log 1 n
Since is a downscale of gt. we then arrive at |pyl S
JS dd pp: Iog
By the definition of 6n,5 (p)(()), we have ligg - Mpl S pop V log
S
(p)
For the other corollary, observe that since 's support is in [-r, r.. opt is then upper bounded by
2r. Therefore, under the assumption that log à is bounded by a sufficiently small constant, we have
10 log 5
F22 Showing that en/3,6(g) S (p),
Since en/3,6(1) o (Im, M0 + Taiys
log 1
we will separately show that |M4 Majja
(p),,(pp) Lemma 35) and 0g
log
O(En. (p)) Lemma 36
21

---

For the second item, the proof of Lemma 36 is relatively self-contained, though requiring some minute calculations. On the other hand, the analysis of [4 Hyi,a non-trivial. To upper bound this term, we consider an intermediate (non-unit) measure q resulting from trimming q to the same interval as Pn. We then show Lemma 32 which bounds the difference between first moments of Fa/3 and q. and Lemmas and 34 which bound the difference between the first moments q and q the two cases of the construction of The combination of these three lemmas gives Lemma 35 which bounds 14g H as desired.
In much of the analysis in this section, we will assume without loss of generality that p has mean is trimmed to the unit interval [-1, 1] when constructing Pr.
Let n be the number of samples and be the failure probability, and suppose there is sufficiently small absolute constant which upper bounds log 3 Given distribution p with Hy 0 and whose trimming radius for constructing pr, is equal to I, suppose the distribution 9 is such that dg
Lemma 32
2.
dp < 2 and |pyl S 1. Letting 9n/3 be the (L log 1/2 )trrimedd version of distribution trinming to some interval [1gg r.g My rgl. then:
+When [mg. r.. Pa + rgl is a subset of [-1, 1] then
51 (s-
(((--1a) (4) (x-)
I (x (bg dq
3 pp
4.5 4.5log'
I Slup Mel
n
When Leg ras Ma + ro] extends outside
[-1, 1] then
5 (10 pa) dq // (x Ha) dg 5 2.8125log x
< s
My-
Proof of the first bullet. Define S = [-1,,1]] [Hqg - rgg + rgl. Firstly, due to triangle inequality. we have
1/g (a un) du S
$1 ((p Ma) dn + 11/ (x (c--mp) up) up) Slup uyl + 1/(e (x up) cq
The Cauchy-Schward inequality then says that
Is (5-1)) s VI100 (0--1)) 1p)? day/ Ss dg
Note that the second integral in the right hand side is bounded by the amount of trimmed probability mass, which is at most 1.35log 1. The first integral, since dp < 2, is bounded by twice the variance
of p in [-1, 1], namely 20pp:" Thus the product of the square roots of the two integrals on the right
hand side is bounded by on; V 1.35log 2 yielding the desired bound.
a
Proof of the second bullet. Without loss of generality, we assume M4 Mp = 0. Thus by the assumption of this case, that [My Tq. Pa + rg] extends outside [-1, 1]. we have that Ha + ra > 1, because of the asymmetry that f, 2 0. Since br S _ by the lemma assumption, we also have
rg 2 4-
Recall that p has a total of O. 0.15log mass outside [-1, 1] by the lemma assumption, and that de "
dp < 2.
This implies that has at most 0.9log & mass outside [-1, 1]. As 1.35log & mass is trimmed from q to construct 2./30 there is thus at least 0.45log mass trimmed from g inside the interval [-1, 1). Furthermore, since dp
dg < 2, we conclude that there is thus at least 0.225lng 1 mass trimmed from
p inside the interval [ 1]. Now denote the set on which is trimmed, restricted to [-1, 1] by S = 1] [Mg Tg. Pg + rgl. Since p has at least 0.225log mass in S, meaning that 5 + 0, and M4 + Tq 1 from earlier, it must thus be the case that Mag Tg -1 and therefore T4 < 5
22

---

Since min |.s] > Ss x² dp 2 22:20 n
2 we conclude that (0p;)²= + (Hpx)) = S-1 x² dp 2 =- dp z
log 2 Using the standard inequality that the & norm is at least the & norm.
have that on Pra 2 v(ar=)² (1p;)
log
Thus, since
4.5log n
S 3 by the
27.20 n
4.5log
4.5ing This yields the
lemma assumption, we have that en. = pz second inequality in the second bullet point.
80
We now prove the first inequality in the second bullet, which bounds the difference between two integrals; we bound this by bounding the probability mass in each integral and multiplying this by bound on the integrand of each integral. Explicitly, the amount of probability mass of g that is in [-1,1] 1] but outside of [Mg gg. My + rgg is at most 1.35log å and furthermore, for every [-1, [Mg "g. My + rgl. we have |z- - Mgl S ] due to |ug1 - 3- In parallel, the amount of probability mass of p that outside of [-1, 1] but in [M, Tgg Mg rrg] is at most 0.45log 1 and since dp $ 2, we conclude that q has at most 0.9lug å mass outside of [-1, 1] but in [Pg Tg. My + rgl- n
dg
Also, for every E [Mg - rg Ma + rg] \ [-1,1] 1], we have x M4l S 1
5 because ry S 5 Thus, the 1'
left hand side of the second bullet is at most (2 3) 0..45 log 2.8125 log 1 as claimed.
Lemma 33 Given a distribution p with = and whose trimming radius for constructing P7 is equal to 1, let q be the distribution constructed from in Case (the small ppr. Ppl case) of
Definition 4 Then [ (x Ma) dg| s 50p / 1og
Proof. Notice that
S JAI-LLN (a- (a-Ma) ua) do S
1 |
1 S -Mg dq I | x dg
dg
+ lngl
and since 1pg1 S $ ph
log I
by Lemma 31
we only have to bound the first term by some constant
log
multiple of pp
Recall the construction of y in Definition 4 as downscaled version of either yt or Without loss of generality (by reflecting p and q as appropriate), we assume we use qt. Specifically, yt the non-unit measure such that dp (x) + min(1 1, max(-1, ax)) for some value specified in Definition 4
Since is downscaled version of gt. we will bound [f x dg s [ dq
by
constant multiple of pra log
Observe that for any O, we have that æ and min(1, max( 1, az)) have the same sign everywhere, which means
Vey- x min(1, max( - ax))) dp s If x min(1, max(mmx az))) dp
Additionally, because 1og is upper bounded by a sufficiently small absolute constant and
|Mpz11 I Jpp V
log from the lemma assumption, we get 0.4%
Heg
S 20p; v
0.45 0.45
log S
log
4.50pp; V
We can now upper bound [ x dd+ as follows.
23

---

SENt-LI rdq
x(1 min(1, max(- -x))))))))) dp
RV1-1111
/ [a(-1.11 x minnnn, max( az)))) dp
x rdp
+
181-1.11
/ x minnI,, max(-11a ax))) dp
x rdp
+
RM(-1.11
+ | xxdqa dp)
x xdp
Mpg
/ dg
since H4p 0
0.45 log 3
J
Mp
since is a downscale of gt by factor at most 2 + 2 |gg1
0.45 log 3
I
log
50pt
using the prior bounds the two terms and that 4.5 + S 5
7
Lemma 34 Given a distribution p with Pp and whose trimming radius for constructing P7 is equal to 1, let be the distribution constructed from as in Case I (the large 11pp. Ppl case) of
Definition 4 Then [ (x M4) dg s 5/pp; Upl
Proof. From the construction, g outside [-1, 1] just consists of the corresponding portion of p multiplied by E 10. Thus
SAN--N (x- Myg dq
= > (x - pgg dp
3V(-1.11
> (Hg - Mp) 0.45log 1
+
(x - Mp)
[R(-1111]
11pg 14p
S 1pp Me +
0.45log
n
Since is an interpolation between p and p",, the mean of q is in between the mean of p and the mean of ph, and thus 1Ap Mal Mpp. Upl- Furthermore, since !ooog is upper bounded by some sufficiently small absolute constant, the entire bound above can be finally bounded by 5 5/pp desired.
Lemma 35 Given a distribution p with μp 0 and whose trimming radius for constructing P", is equal to I, consider constructing according to Definition 4 Recall also the notation for the distribution 4213 which is the 1.35 log )-trimmed version of q as in Definitiin 1. and suppose Fn/3
is formed by trimming q some interval [My Taq Ml + Tgl. Assuming that log is upper bounded by some sufficiently small absolute constant, then |pg - Mat S 50cn,6(p).
Proof. By the definition of g2
1.35log 5
1.35log 5 Mg M4
1.35log
Mains + f J
1
Mg +
I dg
24

---

Further noting that JRN - ral tot My dg 1.35lgg Mg. since we trim exactly 1.35lgg mass outside of [Mg Tqx Hy + reb we can rearrange the above to get
probability
(1 1.35log
8 (1-1.350033
/ (Hg M4inps)
L JaN
(xr 1aa dg
As result, to bound 1ogg M it suffices to bound By the triangle inequality, we have that
1 1bg dq
= | 11111111
(z-Ma) dg) + [" (x (x-Ma) - f puutro
(x Myy dq
(x -
(x 1-H4) dq
M4 Na
(x - My) + [ (x- ((g) dq
f (x - Mgg dg
p
281-1,11
H4-ro
and we bound the two terms separately.
log t By Lemmas 33 a3andd 34 have SRN(-1.1( myy) dq/ S 51 - Mpal + 50p;
in either case n
of the construction of g.
To apply Lemma 32, need to verify that the construction of q is such that 1ing Upl S 1/4 when the trimming radius for constructing p. from is 1. This was shown in Lemmas 30 and 31
Therefore, by the two cases of Lemma 32 we have (x (4) dg
f (a M4 dg S
max (1p Mgl + Viopa
4.5log 2mn(()) From Lemmas 30 and again, we have that
Ipp- - Mgl S (p))(p).
Combining all these bounds, we have
(Ver--n (x Me) dg
pootto + / (x pg)dq
1pg. Motn 15 1 1.35log
(xc Mag dg
Ma
$ (1111-111
+ S' (xr Mgy dq p
R11-1.11
(x M²) dg
(xr
mkg) do
M0-
log
(no(P) + 1/3 15
4.5log
< 10|Mp Mppl 10
+ 2 max
2cn,
n
n
< (0)n,s())
where the last inequality uses the definition of (n, = 111p Ppr, pp
4.blog
Lemma Given a distribution p with Pp = and whose trimming radius for constructing Pt, is equal to I, consider any distribution q such that dg <2 and |pg S Recall the notation for the dp
distribution La13 which is the (1:35 log 3 )-trimmed version of g as in Definition 1 and suppose Lu,3
is formed by trimming to some interval [Pg TTq My + rgg. Assuming that log 5 is upper bounded by some sufficiently small absolute constant, then 0g < 50(0p;; 1ppp Pp=
Proof. Without loss of generality, assume that By 2 to upper bound Ex+g- [X2] by 57((pp;)2 (4z;)?), which implies og S [X²] <
the following proof, we will aim
V57 (op;) (Mp;)) < 8(0p;, + |Mp; [), yielding the lemma statement.
Before we bound Ex (x2), we first show that by the assumption of Ny 2 0, it must be the case that My Ng -.
25

---

Recall that p has a total of 0.45log & mass outside [-1, 1] by the lemma assumption, and that dp n
This implies that q has at most 0.9log & outside [-1, 1]. Since 1.35log mass is trimmed from g to construct ///3 there is thus at least 0.45lng mass trimmed from q inside the interval 1-..1].
Since Ma 2 Ap O, it must be the case that H4 2 -1; otherwise 2 1 and hence H4 + 2 1, which would mean that [ig Tg: My + rgl completely contains [-1, 1/. contradicting the fact that trims non-zero mass from the interval [-1,1] 1].
We will now start bounding Ex-q- [
p ty
E
[X2]
x du
X X
Me t
x² dg
1.35log
11
2
Ho
dq
x² dp
since
1,35log
dp
Tg
max(L-llatre)
2
2
x²a dp
x22 dp
1.35log
1.36log 1
We can bound the two integrals separately. First:
[ x² dp < [- z²dpp, since P" is scaled up after trimming to renormalize
-1 =Oop; )2 + (pp:))
Second, we will bound p (max(1, x² dp. If pq + < 1 then the integral is O. Otherwise, we have Py + T. 1, and we have bound the above integral, using the following bounds on Tgg My and the second moment of pr.
Consider the mass of g that was trimmed from within [-1, 1). Since M4 + rg the (at least 0.45log mass that was trimmed from must be within [-1, M4 Tg] Further recall that dg
dp < 2,
which implies that p has at least 0.225log mass within [-1, My - -rgl. Since the trimming interval for constructing pt from p is [-1, 1], and pt, is constructed from scaling up the trimmed version of p, conclude that p" also has at least 0.225log mass within [-1,
rgg]
As we assumed that fy < 4 furthermore implies that |14 -r 2 2. Thus the > 0.225log i probability mass of p", in [-1, Mq Tol
1 in the lemma statement, we have from Me + rg > 1 that rgg 2 4.
3 This
0.225log 1 to the second moment of p namely Ex+p; [X > 0.225 1og
contributes at least 2/2
4
We can also bound rg 3. since My Tg > -1 and M4 I t: thus My 3.
26

---

Therefore,
Hatto
Muttr dp
x²2 dp S (Mg + rg)2
9 tot
dp
9
0.45log 1
["
0.45log 1
$
since
dp
4
7
n
S 18
E [x²]
using the prior bound on the second moment
X+P:
= 18(()r;) )² + (ppp))2)
Summarizing, when log 1 is bounded by some sufficiently small absolute constant, we have
2
2
max(1,
E [x2] S
x²² dp + 1 1.35log
x² dp
X X
1 1.35log
n
"
S (1 18) ((op:) )² + (1pp;)
?
57((pp; ) (pp;)
which yields the lemma, by the argument the very beginning of the proof.
Lemma 37 Consider constructing distribution q from p according to Definition 4 Assuming that
loR is upper bounded by some sufficiently small absolute constant, then /n/3,8 (g) < 100e (p).
Proof. Since the construction of q in Definition 4 satisfies the assumptions of Lemma 36 this lemma
follows directly from summing up the bounds of Lemmas 35 and 36 that
4.5log +
4.5log 1
(n)3,6(9) = 1 10
50en, (0)n,())) +lpp -op DV
100
n
where the last inequality uses the definition of (p) = 1/4p Mpp op bounded by a sufficiently small constant.
4.5log and that log
27


Reviews:
[{"review_id": "t96V7bcEAT", "reviewer": "Reviewer_iso5", "summary": "This paper studies the 1-dimensional robust mean estimation from the perspective of \"beyond the worst-case analysis\". They show somehow a negative result, that is, for any distribution, we can always construct another distribution that is close in probability distance, but their means are well-separated. Furthermore, to analyze the fine-grained optimality of algorithms, they propose a new definitional framework called “neighborhood optimality”. They show that the classic MoM estimator is neighborhood optimal up to some constant.", "questions": "N/A", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- This paper studies the 1-dimensional robust mean estimation from the perspective of \"beyond the worst-case analysis\", which is a very important and interesting view for this problem.\n\n- Their construction might be adapted in other settings.", "weaknesses": "- As discussed in the paragraph (lines 69-76), there exists a class of distributions (symmetric distributions) whose error rate can be better than the sub-Gaussian rate. My question is can we modify the current construction to reflect this result by restricting the feasible domain of the perturbed distributions?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Yes, one could use the framework of this paper to attempt to design a construction for symmetric distributions $p$ (constructing a symmetric alternative, $q$), and thereby obtain a Fisher information rate estimation lower bound. In fact, (as discussed in [GLP23]) the Fisher information rate bound of symmetric mean estimation really comes from the related problem of location estimation, which is the \"parametric\" version of mean estimation: suppose we know the density of the data distribution, but not its shift, the goal is to estimate the shift from i.i.d. data. As such, the correct lower bound construction is likely just shifting $p$ slightly to form $q$, or slight variants of this.\n\nThe algorithmic techniques of [GLP23] for symmetric mean estimation come from their study of the location estimation problem in previous papers. From our communication with the authors, they have also been trying to prove lower bounds for location estimation, but so far they have not been successful in getting a finite-sample and high-probability Fisher information rate bound. Thus, it remains an open question to show such a bound. On the other hand, if we only care about the error variance, then the well-known Cramer-Rao bound states that every shift-invariant location estimator must have variance at least $I/n$, where $I$ is the Fisher information of the distribution. So there's already good (but not definitive) evidence that the Fisher information rate is optimal.\n\nWe also refer the reviewer to our general response discussing how we view our paper more as a \"call to arms\" than as a negative result. We believe that there is more work to be done in identifying reasonable distributional assumptions (besides symmetry), such that the sub-Gaussian error bound barrier can be overcome."}, {"review_id": "OIe8THGDUV", "reviewer": "Reviewer_x13e", "summary": "This paper studies the fundamental task of 1-dimensional mean estimation. There has been recent interest in the community to understand “beyond worst-case” analyses of statistical problems, where guarantees are able to encompass properties of instances that may make them more tractable than worst-case instances. This work motivates and initiates such analysis for mean estimation. The main result aims to show negative evidence for this perspective: proving that for any distribution $p$ with finite mean there is another distribution $q$ where it is hard to distinguish $p$ vs $q$ and their means are separated by the sub-Gaussian rate. Moreover, in many senses $p$ and $q$ are “similar”, so this indicates hardness to beat the sub-Gaussian rate even when just designing an algorithm to perform on $p$ and “similar” distributions. This perspective is further developed by the formalization of “neighborhood optimality” and median-of-means is shown to be approximately neighborhood optimal.", "questions": "Could you further explain your claim on line 70 that your paper shows introducing extra assumptions are necessary for the [GLP23] results? A naive reading of this claim feels strong in that worst-case lower bounds already show the need for additional assumptions, but perhaps the desired claim is that your work shows the assumptions must not be qualities that $q$ preserves in your transformation? Relatedly, does [GLP23] imply that it is open whether a result similar to your Theorem 2 is possible where $q$ additionally preserves (i) symmetry, or (ii) Fisher information, but it is impossible to (iii) simultaneously preserve symmetry and Fisher information?\n\nDo you have more intuition to share regarding whether it is a reasonable goal to naturally hope for $(1+o(1), 1+o(1))$-neighborhood optimality?\n\nAs some of the motivation for neighborhood-optimality originates from failing the hardcoded estimator, are there known references that alternatively tackle this by restricting the estimator to have desirable properties (e.g., being translation invariant)?\n\nMinor details:\n* On line 380, is the mention of $\\log(1-d^2_H(p,q)) \\ge \\frac{1}{2n} \\log 4 \\delta$ redundant from $q \\in N_{n,\\delta}(p)$?\n* The equation above line 391 has an extra pair of parentheses", "limitations": "Limitations are well-discussed.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "It is an extremely fundamental pursuit to understand mean estimation and what nice properties of distributions permit better rates. The perspective introduced in this work of analyzing the optimal algorithms that perform on some distribution $p$ and “similar” distributions is both novel and insightful for progress in this pursuit. \n\nWhile this paper mostly focuses on one (relatively well-motivated) notion of “similarity”, the landscape of analogous results clearly is dependent on what similarity notion is used. This is perhaps one of the most appealing aspects of the paper, as it gives a concrete framework within which to use notions of similarity as proxies for the properties that make distributions nicer in the beyond worst-case sense. As an example, the notion of similarity in this paper enforces $\\frac{dq}{dp} \\le 2$, indicating that the similar distributions which are still hard have similar moments and thus limiting how much moment-based guarantees can make distributions more tractable. On the other hand, the later work of [GLP23] (I believe) implies that analogous results cannot hold when similarity preserves both symmetry and Fisher information, highlighting how permissible similarity notions in this framework may help demarcate helpful properties.", "weaknesses": "Although likely outside the reasonable scope of this work, the existence of results such as [GLP23] indicate how this perspective would benefit from deeper investigations into various neighborhood functions.\n\nFrom the exposition, it is not immediately clear how conducive the neighborhood optimality perspective is towards thinking about tightness without constant-factor lossiness (the paper seems to hint that proving a guarantee without such lossiness may be a reasonable-sounding future direction).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your insight on our work, and your questions. We particularly enjoyed reading your summary of the strengths of the paper.\n\nHere we respond to the questions raised in the review.\n\n**Q1**: What we meant is that, in order to beat the sub-Gaussian bound for *any* distribution, even asymptotically, we would need to introduce new assumptions that are not properties satisfied by the construction of $q$ in Theorem 2. And so the claim is not only about the worst case, but in fact essentially for *all* cases. We will clarify this in the paper.\n\n**Q1.5**: You are correct. If the construction of $q$ preserves both symmetry and Fisher information, then there can't be a Theorem 2 with a mean separation as large as the sub-Gaussian bound (even only asymptotically). The tight construction that yields a Fisher information rate lower bound, we conjecture, is probably $q$ being just $p$ shifted slightly, or some variant of that, without changing the shape from $p$ to $q$. The Fisher information rate bound comes from the parametric problem of location estimation. So far, there has been no proof of a finite-sample high-probability Fisher information rate lower bound for location estimation, as far as we know (from communication with the authors of [GLP23]). On the other hand, there is an essentially tight result if $p$ is sufficiently smooth (if $p$ is the convolution of some distribution with a small Gaussian), see [Gupta, Lee, Price, Valiant NeurIPS 2022].\n\nIt is indeed unclear what happens if we require $\\frac{\\mathrm{d}q}{\\mathrm{d}p} \\le 2$ yet only 1 of symmetry or Fisher information not blowing up, whether we can still get a construction with asymptotically sub-Gaussian mean separation. We do want to point out, however, that a hypothetical construction preserving symmetry yet getting sub-Gaussian mean separation is almost by definition \"unreasonable\", in that the resulting neighborhood Pareto bound is larger than the upper bound given by [GLP23]. This suggests that the neighborhood choice is too weak, that the \"$q$\" construction did not preserve enough properties of $p$ (e.g. the Fisher information, in this case).\n\n**Q2**: We draw the distinction between the potential *existence* of such $(1+o(1), 1+o(1))$-optimal estimators, and their *analysis*.\n\nExistence should be doable: if we relax the neighborhood enough, then we get back to admissibility, and existence is trivial (hardcoded estimators are $(1+o(1))$-admissible, which is easy to prove). We don't see any good reason why a $(1+o(1))$-optimal estimator shouldn't exist for a more reasonable neighborhood structure.\n\nAnalyzing such estimators seems much more challenging: we believe that the literature doesn't have the right tools yet.\nTo get a tight analysis (through indistinguishability between two distributions), we need to develop tight tools to calculate the $n$-sample TV distance between a pair of distributions.\nHowever, the only generic tools we're aware of are *asymptotic* results coming from the \"large deviations principle\" such as Cramer's theorem, or non-asymptotic bounds that are off by constants in the exponent of the failure probability, even in the Gaussian case---based on the high-probability Pinsker inequality (based on KL divergence), or based on squared Hellinger distance. None of these approaches can give tight finite-sample bounds on the estimation error.\nTherefore, before we could refine our \"$q$\" construction and give tight analysis, we would first need to find better tools to bound the $n$-sample TV distance.\nThis is probably a medium/long-term project, and not something accessible in the immediate future.\n\nNonetheless, we emphasize that constant-factor results (such as those in this work) are meaningful, since variance can be much more than a constant factor different from Fisher information.\n\n**Q3**: We are unaware of additional references.\nStein's paradox shows (particularly for the multidimensional case) that in general, we shouldn't take translation-equivariance for granted - the right estimator might not be translation-equivariant, depending on the objective/loss. We agree that it is interesting to continue to develop and refine new frameworks and perspectives on the mean estimation problem, and on beyond-worst-case analysis in general."}, {"review_id": "hXzXfhg4a6", "reviewer": "Reviewer_Z2th", "summary": "This paper is about analyzing the optimal bounds for mean estimation, beyond the worst-case setting given in the recent breakthrough result of Lee and Valiant giving optimal subgaussian error rates for all distributions with unknown, finite variance. This prior work shows only that there exists a single \"problematic\" distribution class, for which the given error rates are best possible. Thus, a natural approach to make progress is to prove instance-dependent bounds for estimating the mean that are able to outperform the worst-case bounds at least for some distributions. The main result of this paper is that, assuming only that the distribution has finite mean, this natural approach cannot asymptotically improve over the worst-case optimal subgaussian error rates. In particular, given a distribution $p$, a failure probability $\\delta$ and a number of samples $n$, the authors construct a distribution $q_{n,\\delta}$ such that: \n1. $q_{n,\\delta}$ cannot be distinguished from $p$ with $n$ samples and success probability $1-\\delta$.\n2. The means of $q_{n,\\delta}$ and $p$ differ by an amount that asymptotically approaches the optimal worst-case subgaussian bound.\nTogether, these two properties show that instance-dependent bounds in this setting offer no improvement. The paper also introduces a framework called \"neighborhood optimality\" which interpolates between the (too weak) notion of admissibility and the (too strong) instance-optimality.", "questions": "Minor comment:\nLine 203 states that $q$ satisfies all the properties of definition $N_{n,\\delta}(p)$, but as far as I can tell $N_{n,\\delta}(p)$ hasn't been defined yet.", "limitations": "Yes.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The paper is well-written and gives and intuitive, straight-forward construction showing that it is not possible to improve on the worst-case optimal subgaussian bounds assuming only that the distribution has a finite mean. This is a valuable contribution by itself, and also has to deal with subtle technical difficulties arising in the case that the distribution has small mass very far from the mean, which none-the-less contributes significantly the the variance.\n\nFurther illustrating the utility of such a construction is the fact that follow-up work has already utilized the intuition behind it to prove improved bounds for symmetric distributions. In particular, the construction relies heavily on the ability to consider distributions with tails that are very skewed in one direction, and so symmetric distributions are a natural candidate for improved bounds guided by this construction.", "weaknesses": "The neighborhood-optimality framework seems interesting, but the results in the paper so far are not entirely convincing that this is the \"right\" way to go beyond the worst-case for mean estimation. However, the construction showing that subgaussian bounds are optimal when there is a finite, unknown mean is in my view the main contribution and quite significant on its own. So any potential limitations of the neighborhood-optimality framework are not much of drawback in my view.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive and in-depth review of our paper.\n\nRegarding your comment about the neighborhood optimality definition, we want to emphasize that, prior to this paper, the community would basically just use the local minimax definition. As we show in Appendix A, local minimax allows meaningless bounds which should be rejected as absurd, and it is thus reassuring that  our neighborhood optimality notion provides a principled framework with which to reject these bounds. Furthermore, for the common use case of indistinguishability between two distributions, neighborhood optimality is a stronger notion than local minimax. Thus, in this paper we are at least giving an improvement to a standard definition.\n\nAs discussed by reviewer x13e, our paper gives a *flexible* framework, accommodating many different instantiations and interpretations, and our contribution to the mean estimation problem is philosophically different from much prior work.\nEven *if* neighborhood optimality doesn't turn out to be the \"right\" definition, we want to note that it is common for a community (e.g. in crypto or in various other parts of math) to \"negotiate\" definitions in a series of papers, until a good definition is ultimately found. We hope this paper at least initiates this conversation, by pointing out the shortcomings of local minimax and proposing an improved alternative. \nWe welcome the continuing academic process of presenting a new definition which is then discussed by the community, and iterated on in future papers."}, {"review_id": "anrIFo46rD", "reviewer": "Reviewer_bzea", "summary": "The paper studies one-dimensional mean estimation in a beyond-worst case setting.\n\nThe main contributions are twofold. First, it gives indistinguishability results which, given a distribution p of finite mean, construct a “partner” distribution q that preserves the moments yet has mean far from p. This implies the subguassian rate via median-of-means is optimal in general. Hence, this result can be viewed as an impossibility theorem against beyond-worst-case analysis for mean estimation.\n\nSecond, they give a new framework of neighborhood optimality, and show that median-of-means is optimal up to a constant.\n", "questions": "This indistinguishability claim reminds one of the sample amplification framework proposed by https://arxiv.org/abs/1904.12053. It might be worth a remark if there’s any formal connection. \n\nIn the related work section, I would suggest citing this survey: https://arxiv.org/abs/1906.04280\n", "limitations": "It's addressed in the paper.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The question studied here is well motivated. I believe this is the natural next step following the recent work of Lee-Valiant (2020) and early papers on median-of-means. The paper essentially settles the beyond-worst-case analysis problem in this space (in the negative direction)\n\nThis is a quite solid paper at a technical level. The main contribution is interesting and to me somewhat surprising.  I didn’t not check the proof details from the appendix, but reading the main body the main claims appear correct.\n\nOverall the paper is well-written. \n", "weaknesses": "I would be most interested in an extension of the result to the multivariate setting. \n\nOther minor comments below.\n\nBy “worst case”, this paper refers to the worst over all distributions (under certain moment constraints). I think this should be remarked early in the introduction, since beyond-worst-case analysis in the TCS community typically refers to non-worst-case data. In our case, the data are drawn from a distribution already. So we are not using this notion in the classic sense.\n\nAbstract line 17:  The construction of q preserves the density of p up to a factor of 2 -> I would just state it formally: “the construction ensures dq / dp <= 2 at all points, thus [...]”\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive assessment of our work and for your questions. We address your comments below.\n\n-----\n**High dimensional setting**: This is an interesting question, and would likely need the full extent of the notion of neighborhood optimality to address, going beyond the \"$p$ versus $q$\" counterexamples (\"singleton neighborhoods\") analyzed in this paper. We conjecture that, even though in the low dimensional case, the $\\sigma \\sqrt{\\left.\\log\\frac{1}{\\delta}\\right/n}$ term in sub-Gaussian estimation error is replaced by our error function $\\epsilon_{n,\\delta}(p)$ for instance-by-instance bounds, the $\\sqrt{\\mathrm{Tr}(\\Sigma)/n}$ term in high-dimensional sub-Gaussian estimation will probably remain the same. This is because the term is an expectation/constant probability phenomenon, and independent of the failure probability $\\delta$. Also, in contrast to the low-dimensional setting where constructing the lower bound examples is challenging, in the high-dimensional setting we expect the main challenge to be finding and analyzing a neighborhood-optimal estimator.\n\n**\"Worst case\"**: thank you for pointing this out; we will add a clarification in the paper. We also point out that, even within the TCS community, the terms \"worst case\" and \"instance optimality\" can be used to refer to distributional instances, in the same sense our paper uses. See for example [VV16,VV17].\n\n**Sample amplification** (Axelrod et al.): that line of work is pursuing a rather different goal from ours. In both cases, we are trying to prove indistinguishability (which is a standard approach/argument), but:\n\n1. in sample amplification, $q$ is essentially an output of the algorithm and not just a tool inside the analysis; the input $p$ is crucially *unknown* and only available via sample access.\n\n2. in our paper, we crucially aim to construct a $q$ that has mean far from that of $p$ despite being indistinguishable, while the other paper has no particular restrictions on $q$.\n\nThus while both works may use some techniques that are standard in the field (e.g. Hellinger distance as a proxy for indistinguishability), we think it is hard to formally connect the two frameworks.\n\n**Survey**: We agree that the Lugosi-Mendelson survey provides relevant context, and we will cite it.\n\n-----\n\nWe also refer the reviewer to our general response, that, despite our result essentially settling instance-by-instance mean estimation (in 1-d) in the negative direction, we view our paper more as a \"call to arms\" than as a negative result. We believe that there is more work to be done in identifying reasonable distributional assumptions (in addition to symmetry), such that the sub-Gaussian error bound barrier can be overcome."}]

Author rebuttal:
We thank the reviewers for the positive assessment of our work, and of course also for the constructive reviews and many interesting questions raised.
We are particularly encouraged that the reviewers find our paper 1) well-motivated/important (Reviewers iso5, bzea), 2) an extremely fundamental pursuit (Reviewer x13e), 3) giving a surprising result (Reviewer bzea), 4) significant (Reviewer Z2th) and 5) ultimately, opening up a new research direction (paraphrasing Reviewer x13e).
Here, in this overall response, we would like to re-emphasize the main conceptual message and contribution of the paper in light of the reviews.
We address the research questions raised by the reviewers as responses to each review.

This paper studies the problem of optimal mean estimation in the most basic and widely used setting of 1 dimension. We go beyond worst case analysis, by considering optimality on an instance-by-instance basis. Motivating this from a different perspective:  Gaussians are known to be hardest instances for mean estimation under the finite but unknown variance assumption. We thus ask, are there "easier" distributions for which algorithms can beat the sub-Gaussian error bound? Can an algorithm leverage the beneficial structure of a distribution, without explicit knowledge of this structure?

Our paper provides an unexpected and subtle answer: "yes in limited cases/regimes, but in general no". For some distributions, even standard algorithms can beat the sub-Gaussian bound, but only for a limited parameter regime *per distribution*---namely, if the number of samples is not too large (Proposition 14). In general however, we show a strong and comprehensive negative result. Fixing any distribution $p$, then for large enough number of samples $n$: no estimator can outperform the sub-Gaussian bound by more than a constant factor, unless it has essentially "hardcoded" knowledge of $p$, and thereby misestimates another "similar" distribution $q$ (see Theorem 2/Corollary 3, and the construction of $q$ in Definition 4).

As reviewer x13e puts it, our paper provides a correspondence, mapping a neighborhood structure---"similarity" notion---to a beyond-worst-case analysis. For the natural and minimalist neighborhood notion that "$q$ has tails not much larger than those of $p$", we show a strong negative result, essentially ruling out better-than-Gaussian performance. The key point---a **call to arms** in a sense---is that such negative results are to be circumvented, through identifying additional favorable distribution structure for the mean estimation problem.
Inspired by our results and construction, [GLP23] already showed that if we additionally assume the data distribution to be *symmetric* about its mean, then it is possible to get substantially (and in fact arbitrarily) better-than-Gaussian performance, in fact achieving the Fisher information rate.

We hope the perspective and framework introduced in this paper will inspire further work, investigating structures other than symmetry, towards understanding how to break worst-case performance barriers and overcome them algorithmically.

Meta-review: This paper studies optimal bounds for mean estimation in one-dimensional distributions, beyond their worst-case settings. The existing work has already characterized the optimal Subgaussian error rates for all one-dimensional distributions with unknown, but finite variance. This paper strives to answer the following question: Are there instance-dependent bounds for estimating the mean that are able to outperform the worst-case Subgaussian error rates? This paper provides a strong negative answer to this question. In particular, given a probability distribution with an unknown but finite mean, this paper designs a surrogate distribution that satisfies two key properties: (1) the two distributions cannot be distinguished with a fixed number of samples and a fixed probability, (2) The means of these distributions differ by at most the aforementioned Subgaussian error rates.  Further, the paper introduces a new framework to analyze the fine-grained optimality of algorithms, which the authors call “neighborhood optimality”. As an application of this new framework, the authors show that the standard median-of-means algorithm is neighborhood optimal, up to constant factors.

Four reviewers have reviewed the paper, and their overall assessment of the paper was very positive. I agree with this assessment and believe that the paper has important and interesting implications within the field of robust mean estimation.

The authors are highly encouraged to take into consideration the comments made by the reviewers. The AC also suggests that the authors include a brief discussion on the possible extension of their approach to the robust mean estimation in higher dimensions (especially the interplay between the dimension and the error rate).
Decision: Accept (poster)