Uniform Mean Estimation for Heavy-Tailed Distributions via Median-of-Means

We thank the reviewer for taking the time to read the manuscript and provide constructive feedback.

In the following, we will address the reviewer’s comments in the order they were given, except for those regarding experiments, which we will address last.

Claims and Evidence: We first address the reviewer’s comment on the main results being quite technical and difficult to follow. We will add further explanations in the paragraph following Theorem 3.4. Specifically, we will clarify that the precision parameter $\varepsilon$ affects both $m$ (the number of samples used in each mean estimate) and the precision of the net, with the intuition that we want both the mean estimates to be $O(\varepsilon)$-close to the mean and the "rounding" in the net to have precision $O(\varepsilon)$. Additionally, we will clarify that $\delta$ influences only the number of mean estimates $\kappa$, as this parameter is used to increase the probability that more than half of the $\kappa$ mean estimates are successful - this ensures that the median of the mean estimates, which is the output of MoM, is correct. We appreciate the reviewer’s suggestion to clarify this point.

Theoretical claims: We agree that readability would be improved by keeping the constants in Lemma 3.8 as $c=\frac{4769}{10000}$ instead of $a=\frac{4769}{10000}$ and $d=\frac{331}{1000}$ instead of $b=\frac{331}{1000}$ to mirror the constants in Lemma 3.7. We will make this correction in the next version of the paper.

Methods And Evaluation Criteria: We thank the review for pointing out that the estimator could be better presented. We will make an pseudo-algorithm environment illustrating the procedure of the MoM.

Weaknesses: We thank the reviewer for pointing out that some of the theoretical assumptions could be more clearly stated. For example, in Theorem 3.4, we did not explicitly state that $\mathbf{X}=(\mathbf{X}\_1,\ldots,\mathbf{X}\_{\kappa})$ is drawn from $(\mathcal{D}^{m})^{\kappa}$, so that $\mathbf{X}\_i \sim \mathcal{D}^{m}$, making it unclear what $\text{MoM}(f,\mathbf{X})$ means: $\text{median}(\mu\_{f,x\_1},\ldots,\mu\_{f,x\_{\kappa}}).$ We will correct this in the next version of the paper, along with other suggestions from the reviewer to improve clarity.

Experiments: As also mentioned by reviewer (giju), including experiments would be interesting, but we were pleased that neither reviewer required us to do so. Conducting such experiments would be quite involved. Testing the uniform convergence property would require running the estimation method (in this case, MoM) on all possible functions in the function class and then taking the maximum error. If the function class is infinite, this is infeasible. Thus, one would need to develop a reasonable discretization that is both computationally tractable and fine-grained enough to simulate uniform convergence over the class in the heavy-tailed case.

We thank again the reviewer for their feedback and hope that we have addressed their concerns. If not, please let us know, and we will do our best to address them.

We thank the reviewer for taking the time to read the manuscript carefully and provide feedback.

Theoretical claims: We would like to address the reviewer’s comment about the magnitude of the constants in Theorem 3.4. We agree that the constants differ from the empirical mean estimate of a single function, and we provide the following explanation. The main reason for the larger constants is that we are trying to estimate multiple functions (possibly infinitely many), unlike in the case of a single function. In achieving this goal, the symmetrization, discretization, and permutation steps each introduce additional constant factors into the final bound, which leads to the larger constant. Furthermore, we did not optimize the constants in the proof of Theorem 3.4. We believe it is a good idea to add a comment about this in the next version of the paper and thank the reviewer for suggesting it.

Experiments: We are pleased that the reviewer does not necessarily require us to include experiments in the paper, although we agree that it would be exciting to see the results of such experiments. However, conducting such experiments is quite involved. Testing for uniform convergence would require running MOM and the empirical mean estimate on all possible functions in the function class and then taking the maximum of the error. If the function class is infinite, this is not feasible. Thus, one would need to develop a reasonable discretization that is both computationally tractable and sufficiently fine-grained to simulate uniform convergence over the class in the heavy-tailed case.

Relation to broader scientific literature: We also make a brief remark on emphasizing that we are not the first to provide uniform convergence bounds under heavy-tailed noise, as described in the manuscript in the Related Work section. We differ from previous work due to the focus on the sample complexity of the problem instead that on the estimation error. Thanks to a new analysis technique, and due to the introduction of a novel complexity measure that, differently from previous work (focussing instead on the Rademacher complexity), is log of the size of the relaxed version of a discretization. Our main result (Theorem 3.4) enabled us to give improved sample complexity bounds in the important cases of k-means clustering and linear regression with general losses, which is instead unclear how to derive from previous work.

Relation with Lee and Valiant 2022: We thank the reviewer for pointing out the breakthrough work from Lee and Valiant on optimal mean estimation. As noted above, while we didn't attempt to optimize the constants in our bounds, moving from the task of estimating a single mean to that of estimating the means of each function in a possibly infinite class is likely to introduce additional (and potentially large) constant factors for any estimator. On top of that, often, the estimates of size of the particular function class of interest suffer from possibly large constant factors that may hide the benefits even of asymptotically optimal estimators. As a result, proving bounds with optimal constants (which, at the best of our knowledge, are still unknown) in uniform convergence, is likely to require alternatives to the symmetrization, discretization, and permutations, in addition to the adoption of more refined estimators (e.g., Lee and Valiant 2022). This challenging problem is an interesting research direction for future work, and we will mention it in the next version of the manuscript.

Strengths and weaknesses: We thank the reviewer for highlighting that we could have presented some of the more technical details in the proofs more intuitively and accessibly. For instance as pointed out of the reviewer, the definitions of $\hat{S}\_{b}^{>}(f,\varepsilon)$ and $\hat{S}\_{b}^{\leq}(f,\varepsilon)$ could be better explained, and we will do it in the revised version.

Other Comments or Suggestions: We also thank the reviewer for providing several suggestions for improvement, which we will incorporate into the next version of the paper.

If the reviewer has any further comments please let us know, and we will do our best to address them.

We first thank the reviewer for carefully reading the manuscript and providing constructive feedback.

Relation To Broader Scientific Literature: We would like to comment on the reviewer's concern about the relevance of MoM in light of novel more refined estimators. We start noting that, similar to the MoM estimator, even the best-known bounds for the trimmed mean suffer from sub-optimal constants in the single mean task (see Oliveira, Ornstein, and Rico 2025, Theorem 1.1.1, for the case $p=2$). In addition, MoM is widely used as a sub-routine of other methods, including in the optimal Lee and Valiant estimator. Furthermore we notice that in the uniform convergence setting, differently from the single mean estimation case, it isn't even clear what the optimal constants are. Therefore, we believe that it still makes sense, to analyze the MoM in the more general uniform convergence setting. We thank the reviewer for eliciting such an interesting discussion.

Strengths and weaknesses: We appreciate the reviewer’s efforts in walking us through their experience of reading the manuscript and highlighting that the current introduction of the $\mathcal{D}$-discretization is suboptimal. Regarding point 5), we would like to provide some high-level intuition about why we chose this weak notion of a net. As the reviewer pointed out, the discretization allows consideration of realizations of the samples $X_{0},X_{1},X_{2}\in (\mathcal{X}^{m})^{\kappa}$ to estimate any function $f\in \mathcal{F}$ except on a small fraction of the $\kappa$ subsamples $X_{0}^{i},X_{1}^{i},X_{2}^{i},$ where the approximation of $f$ can be arbitrarily bad. Since we are considering heavy-tailed distributions, we cannot expect that all subsamples will allow us to estimate the function accurately, thus why we did not see how to show the result with out this definition of the discretization allowing for the discretization to "fail" on a small number of subsamples. More specifically, in the case of k-means, we can assert that most of the mean estimates on the subsamples $X_{0}^{i},X_{1}^{i},X_{2}^{i},$ are small, but we cannot make any claims about the remaining mean estimates. With knowledge that the mean estimates on most subsamples are small, we can discretize the functions on these subsamples and disregard the discretization on the remaining ones. A similar argument is used in the proof of regression. As alloted to earlier we did not see a way to prove the theorem without this weaker notion of a net. We again thank the reviewer for emphasizing the need for a more detailed explanation of the discretization, which we will improve in the next version.

If the reviewer has any additional comments, we would be happy to address them.

We thank the reviewer for taking the time to read the manuscript and provide feedback.

We also appreciate the reviewer’s suggestions for improving the organization and presentation by first giving the theorems and then the proof sketch.

We also make a brief remark on emphasizing that we are not the first to provide uniform convergence bounds under heavy-tailed noise, as described in the manuscript in the Related Work section. We differ from previous work due to the focus on the sample complexity of the problem instead that on the estimation error. Thanks to a new analysis technique, and due to the introduction of a novel complexity measure that, differently from previous work (focusing instead on the Rademacher complexity), is log of the size of the relaxed version of a discretization. Our main result (Theorem 3.4) enabled us to give improved sample complexity bounds in the important cases of k-means clustering and linear regression with general losses, which is instead unclear how to derive from previous work.

If the reviewer has any further comments, please let us know, and we will do our best to address them.