Near-Optimal Algorithms for Gaussians with Huber Contamination: Mean Estimation and Linear Regression

Summary

In this paper, the authors give an improved algorithm for estimating the mean of a multivarite Gaussian random variable under the Huber contamination model. Diakonikolas et al. Have given the first algorithm in this model that achieves the information theoretical optimal $\ell_2$ loss of $\Theta(\varepsilon)$ using a polynomial number of samples when the noise rate is $\varepsilon$. Pensia et al. have given a fast streaming algorithm for the same problem with an $\ell_2$ loss of $\Theta(\varepsilon\log \varepsilon^{-1})$ with a sample complexity of $d^2\varepsilon^{-2}$ where $d$ is the dimension. The authors carefully combine the ideas in the above two papers to achieve the sample complexity of $d\varepsilon^{-1}$ which is optimal. At a high level, a mean vector $\mu’$ and a subspace $V$ is first found such that $\mu’$ and $\mu$ are close in $\ell_2$ norm in $V^{\bot}$. Moreover, $V$ has dimension at most $\mathrm{\poly}\log(d\varepsilon^{-1})$ such that a high sample-complexity inspired from DIakonikolas et al. is affordable. The finding of this subspace $V$ uses ideas from the Pensia et al. Paper by looking at a random direction where the eigenvalue is large as opposed to looking at the top k eigenvalues as in the Diakonikolas paper which incurse the worse loss. The paper also gives a linear-sample algorithm for robust Gaussian linear regression by reducing it to the robust mean estimation problem of a certain conditional distribution of the multivariate Gaussian. This algorithm is slightly surprising to me as any continuous distribution has zero probability of exactly seeing a particular item in the sample space and therefore conditional sampling in infeasible. However, the authors manage to achieve their reduction by carefully considering a large enough ball that allows their reduction to go through. I have not carefully checked the mathematical details of the paper.

Strengths

The robust statistics in general and the multivariate robust mean estimation, in particular, have received wide attention recently. Therefore, the improved sample-optimal algorithm derived in this paper should be very interesting to the community.

Weaknesses

None.

Questions

A question to the authors: all the papers in this line of work achieves a recovery rate of say $\varepsilon/1000$ which looks quite lossy to me. Univarite robust estimation achives close to $\varepsilon$ rate, or smaller constants as do several other papers in statistics such as: [arxiv:2002.01432]. So, my question to the authors is: is there any hope that the constant can be improved, or this filtering technique has some inherent barrier?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

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.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

Limitations

None.

Summary

The authors study here a classical problem in statistics: the estimation of Gaussian means and linear regression with Gaussian covariates in the presence of Huber contamination. This paper proposes a novel polylog time algorithm to compute the mean of a Gaussian in an $\epsilon$-corrupted, high-dimensional setting. This algorithm is obtained as a concatenation of two algorithms presented in the literature. They apply this algorithm in Gaussian linear regression and analyze this setting.

Strengths

The paper seems technically sound and addresses some relevant questions in the field. The approach is based on an algorithm previously known in the literature [Dia+18], enhancing it with ideas from [DKPP22]

Weaknesses

While the paper provides a solid theoretical analysis of the time and sample complexity for these algorithms to work, it could be more concerned with seeing it applied. A section could have been dedicated to applying the algorithm in some cases where the parameter values are relevant to some applications. Additionally, the work is focused on proving that the algorithm performs as claimed, but it needs to address the limitation of the analysis of the algorithm. The conditions and assumptions are not clearly stated in the introduction of the problem. The first part of the paper is straightforward and gives a clear introduction to understanding the questions addressed by the paper. It is pedagogical to explain the position in the current literature. The technical part of explaining the algorithm (specifically Section 3.2) takes more work to follow.

Questions

I believe actual experimentation is lacking: Is it possible to test the algorithm and see its performance for some distribution choices? While it is clear that the distribution is Gaussian, are there some constraints on the other distribution?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

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.

Soundness

2 fair

Presentation

2 fair

Contribution

2 fair

Limitations

The paper is theoretical is nature, so there are no limit

Summary

Gaussian estimation and linear regression are fundamental statistical tasks, and the Huber contamination model is one of the most well-studied models for robust statistics. This paper works to design algorithms for these tasks with near-optimal sample complexity, error, and almost linear running time. The main result is for Gaussian robust mean estimation with near-optimal sample complexity of $\tilde{O}(d/\varepsilon^2)$, almost linear running time, and near-optimal $\ell_2$ error of $O(\varepsilon)$. (Previously there have only been algorithms with (i) near-optimal error but polynomially-suboptimal sample complexity and running time, or (ii) near-linear runtime but suboptimal error.) The paper obtains similar guarantees for robust Gaussian linear regression with Huber contamination: resolving the open problem of whether there exists an algorithm with $O(\sigma \varepsilon)$ error in polynomial time and sample complexity. Applicability to streaming is also discussed.

Strengths

The strengths will read similarly to the summary, in that the obtained results are for fundamental problems that mostly speak for themselves. The tasks of Gaussian mean estimation and linear regression with Huber contamination are core to algorithmic robust statistics, and it is highly desirable to have algorithms with near-optimal error, sample complexity, and near-linear running time simultaneously. The main result of this paper is for Gaussian mean estimation with Huber contamination. Grossly oversimplifying, the result works by leveraging ideas related to [DKPP22] and [Dia+18]. [DKPP22] obtains near-linear time but suboptimal error guarantees. It obtains a fast running time by techniques with which it filters in random directions of large variance. [Dia+18] obtains near-optimal error with slower running time by employing a stronger filtering technique that deterministically filters with respect to the subspace for the k-largest eigenvalues. These techniques are not obvious how to use together, as trying to sample for random, strong filtering directions may just consistently produce the same directions, and deterministic filtering will naturally incur a slowdown. In summary, this work’s primary technical contribution is showing how to obtain the guarantees of strong filtering techniques without incurring the slower runtime that is naively associated with them.

Weaknesses

One could argue that the very high-level approach for the main result of mean estimation is not too surprising in how it blends the intuitions of [Dia+18] and [DKPP22]. Still, there are significant technical obstacles to this approach and it is perhaps even nicer to see how techniques from this general body of work are flexible enough to coalesce into a new, important result. Providing some discussion on the relationship to settings with non-identity covariance might be beneficial.

Questions

Could you provide discussion on implications for more general covariances? "reminder" -> "remainder" line 233

Rating

8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.

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.

Soundness

4 excellent

Presentation

4 excellent

Contribution

4 excellent

Limitations

The limitations are appropriately discussed.

Summary

This paper presents an algorithm to estimate the mean of a Huber contaminated d-dimensional Gaussian with sample complexity of n=O(d/\epsilon^2) and a run time that is near-linear. They also provide an algorithm for robust linear regression with sample complexity of n=O(d/\epsilon^2) and a run time that is again near-linear. The results improve upon the existing poly(d/\epsilon) algorithms that achieve \Theta(\epsilon) error.

Strengths

The paper is well-written and the flow is good. Although the paper is highly theoretical, the writing is friendly. The results of the paper seem to answer an important open question and the paper claims to achieve a sample complexity that is close the the mean estimation problem in the uncontaminated case, which is good.

Weaknesses

The paper seems to combine the techniques present in two existing papers to obtain their result. Although the authors clarify that such a combination is highly non-trivial, the math used in the proof section is very dense for a thorough verification of this claim.

Questions

In Appendix B (which forms the core of the proof for theorem 1.3), what is the core insight that helps obtain the final sample complexity? The paper claims that combining the techniques from [DKPP22] and [Dia+18] is highly non-trivial. However, The core proofs in sections B.4.1 do not contain any novel proof techniques apart from the ones already present in [DK19] and [Dia+16]. If you could offer more insight into this in the main paper, that would be good.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

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.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

This is a theoretical paper with no negative societal impact.

Summary

This paper solves an important problem in robust mean estimation and robust linear regression, that is, can we achieve optimal error rate with nearly linear sample size and runtime when the inliers are standard Gaussian. All the previous works that have linear runtime suffer from an additional $\sqrt{\log(1/\epsilon)}$ factor. To derive such results, they develop a new analysis for the classic filtering technique. Moreover, they develop a novel reduction for the Gaussian linear regression to mean estimation problem, which is also of independent interest.

Strengths

- This study solves a long-standing problem in the robust mean estimation and robust linear regression, that is, can we close the gap between the information-theoretic lower bound and the guarantees for algorithms that enjoy linear runtime. This problem, though is nearly the simplest setting, is very fundamental in this field, and I feel like the analysis developed in this paper can be adapted to other tasks. - The proof technique is very strong. The reduction for Gaussian linear regression is quite novel. - I like the intuition illustrated in Section 1.2.

Weaknesses

- In most of the literature listed in this paper, people consider the stronger outlier model, i.e., the strong contamination model. My question is, why the authors can only handle Huber's model? What is the main difficulty in extending to the strong contamination model? - Some notations are not consistent: the pdf function is denoted by both $P(x)$ (line 154) and $p(x)$ (line 173). - It would be great if there are some preliminary simulations to support the theory, like plotting the runtime v.s. dimension.

Questions

N/A

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.

Soundness

4 excellent

Presentation

2 fair

Contribution

3 good

Limitations

N/A