Summary
This paper studies outlier-robust location estimation for symmetric(-like) distributions. For "semi-product" distributions, the authors show that one can achieve $O(\epsilon \sqrt{\log 1/\epsilon})$ asymptotic error with a polynomial number of samples (and time), and $O(\epsilon)$ asymptotic error when given quasipolynomially many samples (and time poly in the sample set size). For elliptical distributions, the authors show that as long as the scatter matrix has $\Omega(\log d)$ effective rank (hiding $\epsilon$-dependence here), then in quasipolynomial time we can yield asymptotic error $O(\epsilon \sqrt{\log 1/\epsilon})$. Crucially, for the last result, the scatter matrix is not known to the algorithm.
Strengths
Prior works in (algorithmic) robust statistics get "stuck" at the $\sqrt{\epsilon}$ asymptotic error, when the covariance of the distribution is not known, even when the underlying distribution is guaranteed to have higher moments or might even be sub-Gaussian. This paper identifies semi-product distributions and elliptical distributions as special classes for which further progress can be made. The author(s) adapts the filtering framework, and proposes using variants of the Huber loss as score as opposed to the basic quadratic score in the filtering step. This allows the author(s) to beat the $\sqrt{\epsilon}$ error even when covariance/scatter matrices are unknown to the algorithm.
Weaknesses
I find some parts of the writing clarity can be improved. In particular, I'm still a bit confused about how the guarantees of this work compare with prior works, re: knowledge assumptions on the algorithms. Some of the technical claims are also a bit over-sold (unless I misread or am misunderstanding). See the "Questions" section for more details.
Another weakness, for me, is the motivation: the practical relevance of semi-product and elliptical distributions seems to be rooted in mathematical finance. However, at least from the cited works, the relevance of these distributions appears to more or less be "because we can write down theorems". I hope the authors will consider adding a more self-contained discussion on why we should care about these distributions; I think it will make the paper more convincing.
Questions
More important:
- Knowledge assumption on algorithm in Theorems 1.4 -- 1.6: one of the selling points from the introduction is that the algorithm doesn't need to know the covariance or scatter matrix. However, it was unclear to me whether this means the algorithm knows absolutely nothing about the scatter, or if it only knows very little (such as an upper bound). The theorems can be a lot more explicit in saying exactly what the algorithm needs to know (or explicitly say that it needs to know absolutely nothing about the scatter matrix). For example, does the algorithm in Theorem 1.4 need to know the parameter $\rho$, which is essentially an upper bound to the covariance, at least in the Gaussian case? This distinction seems pretty important to me.
- Result statement of Theorems 1.4 -- 1.5: the statements are of the form "if $n$ is sufficiently large, then we get this almost-sub-Gaussian error rate plus the claimed asymptotic error". However, it seems that the required $n$ lower bound is large enough that the almost-sub-Gaussian error is already dominated by the asymptotic error. Yet the prose following the theorems seem to sell how the theorem gets close to the sub-Gaussian rate (for Theorem 1.4, and for constant $\delta$ and large $C$ for Theorem 1.5). Am I misunderstanding something?
- Theorem 1.6: Line 170 claims that Theorem 1.6 is only slightly sub-optimal in the no-corruption part of the error. But that error is multiplicative in terms of the effective rank and $\log d/\delta$, which is much worse than the sub-Gaussian rate of *additive* error. This error is equal to the naive analysis of entry-wise median-of-means. In fact, entry-wise median-of-means does not actually need the $d$ in $\log d/\delta$ from the naive union bound, and can get error $\sqrt{\mathrm{Tr}(\Sigma)\log\frac{1}{\delta}/n}$, so the error in Theorem 1.6 is even worse than entry-wise median-of-means. Am I missing the point here?
- It is unclear to me that even the sub-Gaussian rate is the correct error rate for the non-robust part of these theorems. For 1-d symmetric distributions, and without corruptions, it was shown by Stone (1975, Maximum Likelihood Estimators of a Location Parameter) that asymptotically one can achieve Fisher information rates, which can be much better than the variance-based sub-Gaussian rate.
- The appendix was hard to follow. There are three appendices with filtering algorithms, but Appendix I was titled only "Filtering Algorithm". It also seemed a bit weird that Appendices H and I appeared last, even though they prove Theorem 1.4, which was introduced earlier than Theorems 1.5 and 1.6. In terms of the actual content, there doesn't seem to be much discussion on how the techniques in the appendices relate to each other. I could see that Appendix E generalizes Appendix D, but how does Appendix I (and relatedly, Appendix H) relate to Appendix E (and C)?
Less important:
- Notation is slightly confusing, with the bold and capital letters. There is no distinction between random scalars and random vectors (e.g. in defining elliptical distributions).
- Page 3, it was claimed that the first 2 properties of semi-product distributions allow for accurate non-robust (i.i.d.) location estimation by using entry-wise median. This seems true only when $\rho$ is small?
- Footnote 1, does $\alpha$ need to be known by the algorithm?
- Footnote 2, there is an $O(\log 1/e)$ which I assume is a typo? Is "$e$" supposed to be "$\epsilon$"?
- CTBJ22 reference: they show how to do mean estimation robustly when only $1+\alpha$ moments exist, but (1) they do not handle the full adversarial corruption model because of sample-splitting issues and (2) they require an upper bound to the $1+\alpha$ moment in every direction.
Rating
5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.