Beyond Catoni: Sharper Rates for Heavy-Tailed and Robust Mean Estimation

We study the fundamental problem of estimating the mean of a d-dimensional distribution with covariance Sigma preccurlyeq σ2 Id given n samples. When d = 1, citecatoni showed an estimator with error (1+o(1)) · σ √frac2 log frac1δn, with probability 1 - δ, matching the Gaussian error rate. For d>1, a natural estimator outputs the center of the minimum enclosing ball of one-dimensional confidence intervals to achieve a 1-δ confidence radius of √frac2 dd+1 · σ left(√fracdn + √frac2 log frac1δnright), incurring a √frac2dd+1-factor loss over the Gaussian rate. When the √fracdn term dominates by a √log frac1δ factor, citelee2022optimal-highdim showed an improved estimator matching the Gaussian rate. This raises a natural question: Is the √frac2 dd+1 loss necessary when the √frac2 log frac1δn term dominates? We show that the answer is no -- we construct an estimator that improves over the above naive estimator by a constant factor. We also consider robust estimation, where an adversary is allowed to corrupt an ε-fraction of samples arbitrarily: in this case, we show that the above strategy of combining one-dimensional estimates and incurring the √frac2dd+1-factor is optimal in the infinite-sample limit.