Adapting to both finite-sample and asymptotic regimes

I agree to the main concerns raised for the rejection of the previous version of this paper: https://openreview.net/forum?id=CIv8NfvxsX.

The generalization bound of Theorem 3.2 is far from optimal, and there is an other algorithm already out there which reaches the optimal performance and not even mentioned in this paper by Lee and Valiant (FOCS, 2021): https://doi.org/10.1109/FOCS52979.2021.00071. I believe this result is too relevant to be ignored here.

The algorithm of the paper is not completely self-tuning, it has two tuning parameters $v_0$ and $V_0$ which need to bracket the unknown variance. This issue should be discussed because it challenges the adaptivity of the presented algorithm.

The bound of Theorem 3.2 is scaled by an extra $\sqrt{\log(n)}$ factor compared to the optimal performance. Worse, the "constant" C is scaled by the standard deviation $\sigma$ as mentioned in line 1480 and the derivation above, and it seems to me that so it can even grow arbitrarily large. So it is not clear then what is the real dependence of the bound of Theorem 3.2 on $\sigma$.

Here are a few minor weaknesses:

1. Subsection 3.2 sounds a bit off compared to the rest of the paper (the language is sloppy and the presentation not as clear), I think it could be better rewritten

2. There's a typo in the captions of Figures 3 and Figure 5 ("distributution")

• Missing Comparisons: It is concerning that the authors have repeatedly avoided comparing their work to [Lee and Valiant 2021], which addresses optimal sub-Gaussian mean estimation without knowledge of the variance. Previous reviewers have highlighted this omission, but it remains unaddressed. The estimator in [Lee and Valiant 2021] achieves optimal finite-sample guarantees and asymptotic variance (“as accurate as the sample mean for the Gaussian of matching variance”) without requiring prior knowledge of the exact variance. The omission is significant, as [Lee and Valiant 2021] presents a concentration result with an optimal dependence factor of $\sigma (1 + o(1))$ before the $\sqrt{2\log(1/\delta)}$, while the current submission’s concentration result (e.g., Theorem 3.2) shows a gap and depends on some numerical constant $C$.
• Self-tuning property without knowing the variance: Contrary to the paper’s claims, the proposed estimator does not fully exhibit the self-tuning property for unknown variance. It requires upper and lower bounds on the variance (as outlined in Section 3), yet the authors provide no practical guidance on selecting these bounds in the numerical experiments. By comparison, the results in [Lee and Valiant 2021] do not rely on such assumptions.
• Paper Scope: The current title is too wide and could be made more precise. Adding specific terms like “mean estimator” would make the title better reflect the paper scope and contributions.
• Inconsistent Notation: Notable inconsistencies appear throughout the main body, where $\hat\mu (\hat v)$ and $\hat\mu(\tau)$ are used interchangeably. Additionally, it would improve clarify $\sigma_u$ is defined before $\sigma_{x^2}$, as the notation for sigma_{x^2}$ is too specific.

[Lee and Valiant 2021] Optimal Sub-Gaussian Mean Estimation in R. FOCS 2021.

I believe this paper requires some fundamental changes in order to be published in any venue.

The title is really not informative and should be changed. What is being adapted "to both finite sample and asymptotic regimes"? That is not clear until all the paper has been read.

The paper is nearly impossible to read, as it is inconsistent in stating its results and the precise model under consideration.

The introduction is confusing. One one hand it contains irrelevant details (like the definition of sub-gaussian variables) and on the other hand is really generic: it states that in practice you have noisy data, but this doesn't automatically imply a heavy tailed distribution. As a matter of fact, the paper simply studies sub-gaussian noise with mean zero and finite variance.

The specific loss that you are using is redefined a number of times, until finally defining 2.5. Everything before that in section 2 is superfluous. Additionally, you fix $a=0.5$ by looking at the population loss. This to me is a fundamentally unjustified choice.

The significance of the contribution is also not clear to me. If I were to look at the sklearn implementation of Huber regression I would also find a modification of the Huber loss where one optimise for the estimator and a "robustness" parameter [1], which is in essence the same idea of the paper.

Minor points: There are a number of inaccuracies and inconsistencies. I list some of the most glaring ones.

1. Line 34: what assumed Gaussian shape?
2. Line 36: I am inferring you mean that the mean is not finite. If so it would be better to write it.
3. Line 59: it's not clear the role of the parameter $\tau$
4. Line 74: $d$ was not defined before.
5. Line 140: when referring to sub-Gaussian performance, it would be good to point to the relevant equation before
6. Line 141: adding a new parameter $v$ serves no purpose as $v = \sigma$

[1] A. Owen 2006, "A robust hybrid of lasso and ridge regression"