Robust regression with covariate filtering: Heavy tails and adversarial contamination

Ankit Pensia; Po-Ling Loh; Varun Jog

REVIEW 2 major objections 4 minor 1 cited by

Robust regression with covariate filtering: Heavy tails and adversarial contamination

T0 review · 2 major / 4 minor · reviewed 2026-08-27 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Covariate filtering before Huber regression achieves near-optimal error under heavy-tailed, adversarially contaminated data.

desk verdict Genuinely useful paper showing that simple filtered classical estimators match near-optimal robust rates, but Theorem 3.8 as stated has a filter-parameter gap that the proof silently corrects. read the letter →

arxiv 2009.12976 v2 pith:3XB7LXLL submitted 2020-09-27 math.ST cs.LGstat.MLstat.TH

Ankit Pensia , Varun Jog , Po-Ling Loh This is my paper · ORCID

classification math.STcs.LGstat.MLstat.TH MSC 62F3562J05

keywords robustlinearregressionadversarialcontaminationheavy-taileddistributionsHuberestimatorcovariatefilteringstabilityconditionleasttrimmedsquaresabsolutedeviation

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper shows that a simple preprocessing step, running an iterative filter over the covariate vectors to remove points that make the empirical covariance far from isotropic, restores the robustness of classical regression estimators when both covariates and responses are heavy-tailed and a small fraction may be adversarially corrupted. With this filter in place, the Huber regression estimator achieves error $O(\sigma(\sqrt{p\log p/n} + \sqrt{\log(1/\tau)/n} + \epsilon^{1-1/k}))$ under $(k,2)$-hypercontractive covariates with identity covariance and independent additive noise, provided $n = \Omega(p\log p)$ and $\epsilon$ is a small constant. The paper also claims that this is the first polynomial-time estimator that is near-optimal in all the parameters $\epsilon$, $p$, $\tau$, and $n$ together for isotropic covariates and independent noise. A sympathetic reader would care because this moves heavy-tailed and adversarially contaminated linear regression into the same near-optimal regime previously available only for sub-Gaussian covariates, and it does so with a convex objective rather than a more exotic hierarchy.

What carries the argument

The load-bearing object is the $(\epsilon,\delta)$-stability of the filtered covariate set: for every subset retaining at least $(1-\epsilon)n$ points, the empirical mean is within $\delta$ of zero and the empirical covariance is within $\delta^2/\epsilon$ of the identity in spectral norm. The iterative filtering algorithm enforces this condition by repeatedly projecting the remaining covariates onto the top eigenvector of their empirical covariance and removing the points that contribute most to its variance. The paper then shows that this stability implies the weak-stability eigenvalue bounds under which the Huber, least trimmed squares, and least absolute deviation analyses go through; for Huber regression the mechanism is two lemmas, a small gradient at $\beta^*$ and strong convexity on a radius around $\beta^*$, which together force the convex minimizer to be close to $\beta^*$.

What would settle it

Simulate heavy-tailed isotropic covariates with $n = \Theta(p\log p)$, a fixed small $\epsilon$, and noise whose distribution or variance depends on a covariate coordinate, for example $z_i = x_{i,1}\eta_i$ with $\eta_i$ centered and heavy-tailed, then run the filtered Huber estimator and compare its $\ell_2$ error to the claimed $O(\sigma(\sqrt{p\log p/n} + \sqrt{\log(1/\tau)/n} + \epsilon^{1-1/k}))$ rate; a systematic degradation growing with the covariate-noisedependence would show that the independence assumption, rather than the filter alone, carries the result.

Watch

Extended reading notes

Core claim

The central claim is that approximate isotropy of the covariate sample, expressed as the same "stability" condition used in robust mean estimation, is a sufficient condition for classical robust regression estimators to succeed under adversarial contamination of both covariates and responses. After the filter produces a large stable subset whose empirical covariance is close to the identity, the gradient of the Huber loss at the true parameter $\beta^*$ is small and the loss is strongly convex in a ball around $\beta^*$; convexity then forces the minimizer to lie within the claimed error radius. The same filter makes the least trimmed squares and least absolute deviation estimators work under weaker but still useful guarantees, and a postprocessing step improves their dependence on $p$ and $\tau$. The paper further establishes that with Gaussian covariates the error improves to $O(\sigma(\sqrt{p/n} + \sqrt{\log(1/\tau)/n} + \epsilon\sqrt{\log(1/\epsilon)}))$, while the $\epsilon$-dependence of the main heavy-tailed bound matches the lower bound of Bakshi and Prasad, and the $\sqrt{\epsilon}$ dependence for unknown bounded covariance is essentially optimal under statistical-query lower bounds.

Load-bearing premise

The argument depends on the additive noise being independent of the covariates, so that noise terms for the filtered indices remain i.i.d. and mean-zero after conditioning on the filter's output; if noise were correlated with covariates, the proof's symmetrization and strong convexity steps would break down.

Editorial extensions

If this is right

The filtered Huber estimator achieves the near-optimal rate $O(\sigma(\sqrt{p\log p/n} + \sqrt{\log(1/\tau)/n} + \epsilon^{1-1/k}))$ when $n = \Omega(p\log p)$ and $\epsilon$ is a sufficiently small constant, and is the first polynomial-time estimator that is near-optimal in $\epsilon$, $p$, $\tau$, and $n$ simultaneously for isotropic covariates and independent noise.
When the covariate covariance is unknown but bounded between $(1/2)I$ and $2I$, the filtered Huber estimator achieves $O(\sigma(\sqrt{p\log p/n} + \sqrt{\log(1/\tau)/n} + \sqrt{\epsilon}))$, and the paper argues this $\sqrt{\epsilon}$ dependence is essentially optimal for computationally efficient estimators when $n = o(p^2)$.
For Gaussian covariates the error improves to $O(\sigma(\sqrt{p/n} + \sqrt{\log(1/\tau)/n} + \epsilon\sqrt{\log(1/\epsilon)}))$, shaving a logarithmic factor in $\epsilon$ compared with prior algorithms.
Careful application of the same filter makes least trimmed squares and least absolute deviation estimation robust to heavy tails and contamination, and a postprocessing step based on robust mean estimation converts their guarantees into near-optimal dependence on $p$ and $\tau$.
Because the filtering step is computationally efficient and the Huber objective is convex, the whole procedure runs in polynomial time and does not depend on solving a semidefinite program.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

A natural extension, which the paper leaves open, is that the same filter-then-fit recipe could give sparse or otherwise structured regression estimators if the filter could guarantee a restricted eigenvalue condition after removing outliers; that would be a testable follow-up beyond the dense setting considered here.
The separation between a filter that enforces stability and a loss that exploits it suggests that any future algorithm producing a stable subset, including weighted or soft-filtering variants, could be plugged into the same proof template; this is an editorial extrapolation, not a claim of the paper.
Because the main adversarial result depends on the noise being independent of the covariates, an experiment with feature-dependent noise would likely show degradation; whether the rate becomes a function of the covariance of the conditional noise is an open question that the paper does not address.
The paper treats $\epsilon$ as a small constant; how the error and the filter's success probability degrade as the corruption fraction grows toward the breakdown regime is not covered by the theorems and would be a useful stress test of the method.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Request a human review

A listed scientist reviews the paper for a fee and the review publishes here regardless of verdict. See the reviewers or get listed.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

You should know two things about this paper before reading further. First, it is a real step forward: the authors show that a simple covariate-filtering step lets classical Huber, LTS, and LAD regression estimators achieve near-optimal error rates under heavy tails and adversarial contamination, where previously only SOS or spectral methods were known to work. Second, the main advertised theorem, Theorem 3.8, has a mismatch between the theorem statement and the proof. The statement sets the filter parameter ε' = Θ(ε + log(1/τ)/n), but the proof in Appendix D.2 actually uses ε'₁ = C(p log p/n + 2ε + log(1/τ)/n). When n = C·p log p and ε is small, these differ by a constant factor in the (p log p)/n term. Stability needs δ²/ε' = O(1); with the stated ε', the term (p log p)/n is not controlled, so the filtered set need not be stable and the claimed rate does not follow. The fix is easy — state ε' with the (p log p)/n term included, which is exactly what the proof assumes — but the theorem as printed is technically wrong. This is the one load-bearing issue I found, and it is fixable, not fatal.

The genuinely new part is conceptual: stability of the covariates, not just their mean, is enough to make Huber regression work under strong contamination. The proofs are detailed and worth reading; they carefully separate weak and strong stability, and the noise independence assumption is explicitly flagged as restrictive. The LTS and LAD results are secondary but honest, and the simulations, though simple, support the qualitative claims. The heavy reliance on Diakonikolas–Kane–Pensia is fine: it is an external theorem about stability of iid heavy-tailed samples, and one of the authors of this paper is also on that theorem, but the result itself is legitimate.

The main limitation beyond the theorem-statement gap is Assumption 2: independence of noise and covariates. The paper acknowledges this and partially relaxes it for some results, but not for the central adversarial-contamination result. That is a real limitation, not a hidden flaw.

Who is this for? Researchers in robust statistics and algorithmic high-dimensional statistics. It deserves a serious referee: the high-level approach is likely to be influential, and the proof of Theorem 3.8 needs only a localized correction. I would bring it to a reading group and would cite it in future work, provided the final version fixes the parameter statement.

Referee Report

2 major / 4 minor

Summary. The paper studies linear regression in the strong contamination model when both covariates and responses may be heavy-tailed and adversarially corrupted. The authors propose a two-step approach: first run an iterative filtering algorithm on the covariates to obtain a stable (approximately isotropic) subset, then apply a classical estimator—Huber regression, least trimmed squares, or least absolute deviation—to the filtered data. The main result (Theorem 3.8) states that the filtered Huber estimator achieves l2-error O(γ(√(p log p)/n + √(log(1/τ))/n + ε^{1-1/k})) under (k,2)-hypercontractive isotropic covariates and independent additive noise, with n=Ω(p log p) and ε a small constant. The paper also analyzes the LTS and LAD estimators under weaker moment assumptions, provides a postprocessing step that improves their error rates, and reports simulations. The proofs are detailed and follow the stability-based framework from robust mean estimation.

Significance. If the results hold, they constitute a meaningful contribution to robust regression: they show that simple filtering plus classical convex/nonconvex estimators can match or nearly match the error rates of more complex sum-of-squares or spectral algorithms while remaining computationally efficient. The paper is careful in stating assumptions and limitations, provides complete proofs in the appendices, and connects the rates to known lower bounds. The main proof structure—establishing weak stability of the filtered covariate set and then applying strong-convexity and gradient bounds for the Huber loss—is transparent and reproducible. However, one theorem statement does not match its proof, and this must be fixed before the results can be accepted as stated.

major comments (2)

[Section 3.3, Theorem 3.8; Section 3.4, Theorem 3.13; Appendix D.2] The theorem statements specify the filter parameter as ε′ = Θ(ε + log(1/τ)/n), but the proof of Lemma D.2 in Appendix D.2 uses ε′_1 = C(p log p/n + 2ε + log(1/τ)/n) as the filter input. These parameters are not equivalent when n = Ω(p log p) is achieved with p log p/n not absorbed into ε; for example, with n = C p log p and ε, log(1/τ)/n small relative to p log p/n, the stated ε′ does not permit the filter to remove the O(p log p) heavy-tail fluctuations that cause the spectral deviation. In that regime, stability theory (Theorem 2.5 and Proposition C.2) only guarantees δ ≳ √(p log p/n), so δ^2/ε′ can be made arbitrarily large, and the filtered set need not satisfy the weak-stability condition (δ^2/ε = O(1)) on which the strong-convexity and gradient bounds rely. The theorem as stated therefore does not follow from the proof. The fix is to state ε′ = Θ(p log p/n + ε + log(1/τ)/n) in both theorems, which is what the proof actually uses; this does not change the high-level approach or the claimed error rate.
[Appendix D.3, proof of Lemma D.2(i)] The proof of the weak-stability part (i) chooses ε5 and ε′_1 so that 4ε < 4ε′_1 ≤ ε5/10, but with ε′_1 defined as C(p log p/n + 2ε + log(1/τ)/n), the condition ε′_1 = O(ε5) requires p log p/n to be smaller than a constant depending on ε5; the theorem statement does not make this explicit. In the current statement, n = Ω(p log p) without a sufficiently large constant could violate the smallness of ε′_1. This is a secondary consequence of the same mismatch and should be clarified by stating the required lower bound on n relative to p log p explicitly.

minor comments (4)

[Section 3, Algorithms 1 and 5] The notation ε′ is used in three different roles: as a small constant filter parameter (Theorem 3.6), as the corruption-level-dependent parameter in Theorems 3.8 and 3.13, and as the input to FilteredCovariates in Algorithm 1. It would improve readability to rename the filter input in Algorithm 1 (e.g., ε_filter) to avoid confusion with the theoretical parameter stated in the theorems.
[Theorem 4.3] The phrase 'provided J ≳ log2(‖y′‖2+‖X′‖2‖β∗‖2/α)' refers to α before it is defined; reorder the sentence or define α earlier so that the bound on the number of iterations is self-contained.
[Lemma 3.4] The step from the sub-Gaussian norm of the linear projections to the Euclidean norm bound ‖W‖2 = O(γ√(U/n)(√p + √log(1/τ))) uses a standard covering argument over the sphere, but no specific reference or one-line justification is given; adding a citation to a standard uniform-bound result would make the proof easier to verify.
[Section 7] The symbol T is used both for the corrupted data set in the theoretical sections and for the number of simulation trials (T = 50,000) in Section 7; renaming one of them would avoid ambiguity for readers who cross-reference the experiments and the theory.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the filtered-Huber analysis is a genuinely derived result built on external stability theorems.

full rationale

The paper's central claim is that applying an iterative covariate filter and then fitting a Huber (or LTS/LAD) estimator gives near-optimal error under heavy-tailed and adversarially contaminated data. I walked the derivation chain: the statistical analysis is carried out in the paper's own appendices, starting from strong stability (Definition 4), converting it to weak stability (Lemma 2.2), and then proving gradient and strong-convexity bounds for the Huber loss (Lemmas 3.4, 3.5, and their corrupted-data analogues in Lemma D.2). The regression error bound is obtained by combining these lemmas, not by assuming the conclusion. The only self-citation that is load-bearing is Theorem 2.5 from Diakonikolas, Kane, and Pensia [23], a paper co-authored by one of the present authors. That theorem is used to guarantee that i.i.d. (k,2)-hypercontractive covariates contain a large stable subset. It is parameter-free, states its own assumptions (mean zero, identity covariance, hypercontractivity), and does not assume anything about the regression target, the Huber loss, or the behavior of the estimators under study. It is therefore real evidence under the review rules, not a circular premise. The filtering theorem (Theorem 2.3) is likewise an external algorithmic result, and the paper's contribution is the reduction from stability of the filtered covariates to guarantees for Huber, LTS, and LAD estimators—a reduction that is then proved directly. No fitted parameter is renamed as a prediction; no quantity is defined in terms of the quantity it is purported to predict; and the claimed optimality comparison to Bakshi and Prasad [1] is an external lower-bound citation, not an input to the derivation. I also considered the skeptical observation that Theorem 3.8's stated filter parameter epsilon' omits the (p log p)/n term used in Appendix D.2. That is a potential theorem-statement/proof mismatch about correctness of the stated parameter regime, not a circularity: the proof does not assume the theorem's conclusion, and the issue would be fixed by restating epsilon' = Theta((p log p)/n + epsilon + log(1/tau)/n) without changing the structure of the argument. Because the central derivation is self-contained once the external stability results are granted, and those results do not include the target claim, the circularity score is 0.

Assumptions & free parameters 4 free parameters · 9 assumptions · 0 invented entities

The central claims rest on two families of inputs: (1) distributional assumptions on covariates and noise, including zero mean, identity or bounded covariance, hypercontractivity, independence, and finite moments; and (2) external algorithmic results that guarantee the iterative filter returns a stable subset and that iid heavy-tailed samples have such stable subsets. None of these are fitted to the target results; they are standard in the robust statistics literature. The main tuning parameters such as gamma, epsilon', m, and J are set by theory or by data-driven rules with guarantees, not by minimizing the reported error.

free parameters (4)

Huber truncation parameter gamma = Chosen such that P(|z1-z2| >= gamma/sqrt(2)) <= c*; data-driven estimator via residual quantiles in Section 3.2
The error bounds scale with gamma, so the theory specifies a tail condition rather than fitting gamma to the target result. In practice, gamma is set from the data using sample splitting.
Filtering parameter epsilon' = Theta(epsilon + log(1/tau)/n)
The filtering algorithm requires an input level of contamination or an upper bound on it. This is a theory-specified parameter, not fitted to minimize error.
LTS trimming parameter m = Theta(p log p + epsilon n + log(1/tau))
The trimming parameter for the least trimmed squares estimator is set according to dimension, contamination level, and confidence, as specified in Theorem 4.3.
Number of iterations J for LTS alternating minimization = Set via data-driven stopping criterion based on successive iterate differences
The paper provides a stopping rule based on iterate changes; the theoretical iteration bound depends on log2(||b*||/alpha), with alpha the target error.

assumptions (9)

domain assumption Covariates have zero mean and identity covariance, and satisfy (4,2)-hypercontractivity with a known bound C (Assumption 1).
The main theorems in Sections 3, 4, and 5 assume this distributional model for the clean covariates. The identity covariance is normalized, and hypercontractivity provides moment bounds needed for stability.
domain assumption The noise variables are independent of the covariates and have zero mean (Assumption 2).
Independence is used throughout the proofs to argue that noise remains i.i.d. after filtering based on covariates. The paper notes this is restrictive and only partially relaxes it.
domain assumption For the unknown covariance setting, the covariate covariance satisfies (1/2)I <= Sigma <= 2I (Assumption 3).
This replaces the identity covariance assumption for Theorem 3.13 and related results, enabling a bound with sqrt(epsilon) dependence.
domain assumption The strong contamination model allows an adversary to replace an arbitrary epsilon fraction of the data (Definition 3).
The adversarial contamination model is the threat model for all corrupted-data theorems. It is standard in the literature and is stated explicitly.
standard math The iterative filtering algorithm of Diakonikolas and Kane returns a stable subset with the guarantees of Theorem 2.3.
This is an external algorithmic result from the robust mean estimation literature, cited and used as a black box for the preprocessing step.
standard math Iid heavy-tailed samples with hypercontractivity contain a large stable subset with the guarantees of Theorem 2.5 (Diakonikolas, Kane, and Pensia).
This stability theorem is needed to certify that the filtering precondition is satisfied with high probability. It is a prior result, co-authored by one of the present authors, but independent of the regression target.
standard math The deterministic guarantee for alternating minimization for LTS holds under the SSC and SSS conditions (Lemma 4.1, adapted from Bhatia et al.).
This lemma is imported from prior work and provides the convergence analysis for the LTS algorithm.
standard math The LAD estimator succeeds when the covariates satisfy l1-stability (Lemma 5.1, from Karmalkar and Price).
This deterministic lemma is cited from prior work and is used to translate stability of the filtered covariates into an error bound for LAD.
standard math The median-of-means preprocessing theorem of Diakonikolas et al. (Theorem 6.1) holds for the postprocessing step.
This external result is used to prove the sub-Gaussian postprocessing guarantees in Section 6.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Robust regression with covariate filtering: Heavy tails and adversarial contamination." pith.science (2026). https://pith.science/paper/3XB7LXLL

@misc{pith2026200912976,
  author       = {Pith},
  title        = {Pith review of: Robust regression with covariate filtering: Heavy tails and adversarial contamination},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/3XB7LXLL}},
  note         = {Machine review of arXiv:2009.12976}
}

read the original abstract

We study the problem of linear regression where both covariates and responses are potentially (i) heavy-tailed and (ii) adversarially contaminated. Several computationally efficient estimators have been proposed for the simpler setting where the covariates are sub-Gaussian and uncontaminated; however, these estimators may fail when the covariates are either heavy-tailed or contain outliers. In this work, we show how to modify the Huber regression, least trimmed squares, and least absolute deviation estimators to obtain estimators which are simultaneously computationally and statistically efficient in the stronger contamination model. Our approach is quite simple, and consists of applying a filtering algorithm to the covariates, and then applying the classical robust regression estimators to the remaining data. We show that the Huber regression estimator achieves near-optimal error rates in this setting, whereas the least trimmed squares and least absolute deviation estimators can be made to achieve near-optimal error after applying a postprocessing step.

Figures

Figures reproduced from arXiv: 2009.12976 by the authors.

**Figure 2.** Plot showing the effect of covariate filtering on Huber regression and LTS when the data are [PITH_FULL_IMAGE:figures/full_fig_p028_2.png] view at source ↗

**Figure 3.** Plot showing the effect of covariate filtering on Huber regression [PITH_FULL_IMAGE:figures/full_fig_p062_3.png] view at source ↗

Figures from the paper (1 more)

**Figure 4.** Figure 4: Plot showing the effect of covariate filtering on LTS regression [PITH_FULL_IMAGE:figures/full_fig_p063_4.png]

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Active Learning on Adversarially Corrupted Graphs
cs.LG 2026-07 accept novelty 7.0 of 10

A poly-time active learning algorithm approximately recovers adversarially corrupted vertices with query complexity polynomial in the adversary's neighborhood budget and the clean graph's vertex expansion.

Reference graph

Works this paper leans on

91 extracted references · 80 canonical work pages · cited by 1 Pith paper

[1]

Robust Linear Regression: Optimal Rates in Polynomial Time

A. Bakshi and A. Prasad. Robust linear regression: Optimal rates in polynomial time.CoRR, abs/2007.01394, 2020

work page Pith review arXiv 2007
[2]

Balakrishnan, S

S. Balakrishnan, S. S. Du, J. Li, and A. Singh. Computationally eﬃcient robust sparse estimation in high dimensions. InProceedings of the 30th Conference on Learning Theory, COLT 2017, volume 65 ofProceedings of Machine Learning Research, pages 169–212. PMLR, 2017

2017
[3]

Bhatia, P

K. Bhatia, P. Jain, P. Kamalaruban, and P. Kar. Consistent robust regression. InAdvances in Neural Information Processing Systems 30, NeurIPS 2017, pages 2110–2119, 2017

2017
[4]

Bhatia, P

K. Bhatia, P. Jain, and P. Kar. Robust regression via hard thresholding. InAdvances in Neural Information Processing Systems 28, NeurIPS 2015, pages 721–729, 2015

2015
[5]

L. Birgé. An alternative point of view on Lepski’s method.Lecture Notes-Monograph Series, pages 113–133, 2001

2001
[6]

Boucheron, G

S. Boucheron, G. Lugosi, and P. Massart.Concentration Inequalities: A Nonasymptotic Theory of Independence. Oxford University Press, 2013

2013
[7]

S. P. Boyd and L. Vandenberghe.Convex Optimization. Cambridge University Press, Cambridge, UK ; New York, 2004

2004
[8]

S. Bubeck. Convex Optimization: Algorithms and Complexity.Foundations and Trends® in Machine Learning, 8(3-4):231–357, 2015

2015

Show all 91 references

[9]

O. Catoni. Challenging the empirical mean and empirical variance: A deviation study.Annales de l’Institut Henri Poincaré, Probabilités et Statistiques, 48(4):1148–1185, 2012

2012
[10]

M. Chen, C. Gao, and Z. Ren. A general decision theory for Huber’s $\epsilon$-contamination model. Electronic Journal of Statistics, 10(2):3752–3774, 2016

2016
[11]

Cheng, I

Y. Cheng, I. Diakonikolas, and R. Ge. High-dimensional robust mean estimation in nearly-linear time. InProceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, pages 2755–2771. SIAM, 2019. 29

2019
[12]

Cheng, I

Y. Cheng, I. Diakonikolas, R. Ge, and M. Soltanolkotabi. High-dimensional robust mean estimation via gradient descent.CoRR, abs/2005.01378, 2020

2005 arXiv
[13]

Cherapanamjeri, E

Y. Cherapanamjeri, E. Aras, N. Tripuraneni, M. I. Jordan, N. Flammarion, and P. L. Bartlett. Optimal robust linear regression in nearly linear time.arXiv preprint arXiv:2007.08137, 2020

2007 arXiv
[14]

Cherapanamjeri, S

Y. Cherapanamjeri, S. B. Hopkins, T. Kathuria, P. Raghavendra, and N. Tripuraneni. Algorithms for heavy-tailed statistics: Regression, covariance estimation, and beyond. InProccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, pages 601–609. ACM, 2020

2020
[15]

R. D. Cook and S. Weisberg.Residuals and Inﬂuence in Regression. New York: Chapman and Hall, 1982

1982
[16]

P. L. Davies. Aspects of robust linear regression.The Annals of Statistics, pages 1843–1899, 1993

1993
[17]

Depersin

J. Depersin. A spectral algorithm for robust regression with subgaussian rates. CoRR, abs/2007.06072, 2020

2007 arXiv
[18]

Depersin and G

J. Depersin and G. Lecué. Robust subgaussian estimation of a mean vector in nearly linear time. CoRR, abs/1906.03058, 2019

1906 arXiv
[19]

Diakonikolas, G

I. Diakonikolas, G. Kamath, D. M. Kane, J. Li, A. Moitra, and A. Stewart. Robust estimators in high dimensions without the computational intractability. InIEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, pages 655–664. IEEE Computer Society, 2016

2016
[20]

Diakonikolas, G

I. Diakonikolas, G. Kamath, D. M. Kane, J. Li, A. Moitra, and A. Stewart. Being Robust (in High Dimensions) Can Be Practical. InProceedings of the 34th International Conference on Machine Learning, ICML 2017, volume 70 ofProceedings of Machine Learning Research, pages 999–1008...

2017
[21]

Diakonikolas, G

I. Diakonikolas, G. Kamath, D. M. Kane, J. Li, J. Steinhardt, and A. Stewart. Sever: A robust meta-algorithm for stochastic optimization. InProceedings of the 36th International Conference on Machine Learning, ICML 2019, volume 97 ofProceedings of Machine Learning Research, pa...

2019
[22]

Diakonikolas and D

I. Diakonikolas and D. M. Kane. Recent advances in algorithmic high-dimensional robust statistics. CoRR, abs/1911.05911, 2019

1911 arXiv
[23]

Diakonikolas, D

I. Diakonikolas, D. M. Kane, and A. Pensia. Outlier robust mean estimation with subgaussian rates via stability.CoRR, abs/2007.15618, July 2020

2007 arXiv
[24]

Diakonikolas, W

I. Diakonikolas, W. Kong, and A. Stewart. Eﬃcient algorithms and lower bounds for robust linear regression. In Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, pages 2745–2754. SIAM, 2019

2019
[25]

Y. Dong, S. B. Hopkins, and J. Li. Quantum entropy scoring for fast robust mean estimation and improved outlier detection. InAdvances in Neural Information Processing Systems 32, NeurIPS 2019, pages 6065–6075, 2019. 30

2019
[26]

Dwork, F

C. Dwork, F. McSherry, and K. Talwar. The price of privacy and the limits of LP decoding. In Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing, STOC ’07, pages 85–94. Association for Computing Machinery, 2007

2007
[27]

J. Fan, Q. Li, and Y. Wang. Estimation of high dimensional mean regression in the absence of symmetry and light tail assumptions.Journal of the Royal Statistical Society: Series B (Statistical Methodology), 79(1):247–265, 2017

2017
[28]

F. R. Hampel, E. M. Ronchetti, P. J. Rousseeuw, and W. A. Stahel.Robust Statistics: The Approach Based on Inﬂuence Functions, volume 196. John Wiley & Sons, 2011

2011
[29]

Harris, K

Charles R. Harris, K. Jarrod Millman, St’efan J. van der Walt, Ralf Gommers, Pauli Virtanen, David Cournapeau, Eric Wieser, Julian Taylor, Sebastian Berg, Nathaniel J. Smith, Robert Kern, Matti Picus, Stephan Hoyer, Marten H. van Kerkwijk, Matthew Brett, Allan Haldane, Jaime F...

2020
[30]

S. B. Hopkins. Mean estimation with sub-Gaussian rates in polynomial time.Annals of Statistics, 48(2):1193–1213, 2020

2020
[31]

Hsu and S

D. Hsu and S. Sabato. Loss minimization and parameter estimation with heavy tails.Journal of Machine Learning Research, 17(18):1–40, 2016

2016
[32]

P. J. Huber. Robust estimation of a location parameter.The Annals of Mathematical Statistics, 35(1):73–101, March 1964

1964
[33]

P. J. Huber. Robust regression: Asymptotics, conjectures and Monte Carlo.The Annals of Statistics, 1(5):799–821, 1973

1973
[34]

P. J. Huber and E. M. Ronchetti.Robust Statistics. Wiley Series in Probability and Statistics. Wiley, 2011

2011
[35]

Jain and P

P. Jain and P. Kar. Non-convex Optimization for Machine Learning.Foundations and Trends in Machine Learning, 10(3-4):142–336, 2017

2017
[36]

P. Jain, A. Tewari, and P. Kar. On iterative hard thresholding methods for high-dimensional m-estimation. In Advances in Neural Information Processing Systems, pages 685–693, 2014

2014
[37]

Karmalkar and E

S. Karmalkar and E. Price. Compressed sensing with adversarial sparse noise via L1 regression. In 2nd Symposium on Simplicity in Algorithms, SOSA@SODA, volume 69 ofOASICS, pages 19:1–19:19, 2019

2019
[38]

Klivans, P

A. Klivans, P. K. Kothari, and R. Meka. Eﬃcient algorithms for outlier-robust regression. In Conference On Learning Theory, COLT 2018, volume 75 ofProceedings of Machine Learning Research, pages 1420–1430. PMLR, 2018

2018
[39]

Koltchinskii and S

V. Koltchinskii and S. Mendelson. Bounding the smallest singular value of a random matrix without concentration. International Mathematics Research Notices, 2015(23):12991–13008, March 2015

2015
[40]

P. K. Kothari and J. Steinhardt. Better agnostic clustering via relaxed tensor norms.arXiv preprint arXiv:1711.07465, 2017. 31

2017 arXiv
[41]

P. K. Kothari and D. Steurer. Outlier-robust moment-estimation via sum-of-squares.arXiv preprint arXiv:1711.11581, 2017

2017 arXiv
[42]

K. A. Lai, A. B. Rao, and S. Vempala. Agnostic estimation of mean and covariance. InIEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, pages 665–674. IEEE Computer Society, 2016

2016
[43]

J. N. Laska, M. A. Davenport, and R. G. Baraniuk. Exact signal recovery from sparsely corrupted measurements through the Pursuit of Justice. In2009 Conference Record of the Forty-Third Asilomar Conference on Signals, Systems and Computers, pages 1556–1560. IEEE, 2009

2009
[44]

Lecué and M

G. Lecué and M. Lerasle. Robust machine learning by median-of-means: Theory and practice. Annals of Statistics, 48(2):906–931, 2020

2020
[45]

Ledoux and M

M. Ledoux and M. Talagrand.Probability in Banach Spaces. Springer Berlin Heidelberg, Berlin, Heidelberg, 1991

1991
[46]

O. V. Lepskii. On a problem of adaptive estimation in Gaussian white noise. Theory of Probability & Its Applications, 35(3):454–466, 1991

1991
[47]

J. Li. Principled Approaches to Robust Machine Learning and Beyond. PhD Thesis, Mas- sachusetts Institute of Technology, Cambridge, USA, 2018

2018
[48]

Lugosi and S

G. Lugosi and S. Mendelson. Mean estimation and regression under heavy-tailed distributions: A survey.Foundations of Computational Mathematics, 19(5):1145–1190, 2019

2019
[49]

Lugosi and S

G. Lugosi and S. Mendelson. Risk minimization by median-of-means tournaments.Journal of the European Mathematical Society, 22(3):925–965, 2019

2019
[50]

Lugosi and S

G. Lugosi and S. Mendelson. Robust multivariate mean estimation: The optimality of trimmed mean. CoRR, abs/1907.11391, 2019

1907 arXiv
[51]

C. L. Mallows. On some topics in robustness. Unpublished Memorandum, Bell Telephone Laboratories, Murray Hill, NJ, 37, 1975

1975
[52]

R. A. Maronna, R. D. Martin, V. J. Yohai, and M. Salibián-Barrera.Robust Statistics: Theory and Methods (With R). John Wiley & Sons, 2019

2019
[53]

P. Massart. The tight constant in the Dvoretzky-Kiefer-Wolfowitz inequality.The Annals of Probability, 18(3):1269–1283, July 1990

1990
[54]

Mendelson

S. Mendelson. Learning without concentration.Journal of the ACM, 62(3):1–25, 2015

2015
[55]

Mendelson and N

S. Mendelson and N. Zhivotovskiy. Robust covariance estimation underL4-L2 norm equivalence. Annals of Statistics, 48(3):1648–1664, June 2020

2020
[56]

S. Minsker. Uniform bounds for robust mean estimators.CoRR, abs/1812.03523, 2019

2019 arXiv
[57]

Mukhoty, G

B. Mukhoty, G. Gopakumar, P. Jain, and P. Kar. Globally-convergent iteratively reweighted least squares for robust regression problems. InThe 22nd International Conference on Artiﬁcial Intelligence and Statistics, AISTATS 2019, volume 89 ofProceedings of Machine Learning Resea...

2019
[58]

N. M. Nasrabadi, T. D. Tran, and N. H. Nguyen. Robust Lasso with missing and grossly corrupted observations. InAdvances in Neural Information Processing Systems 24, NeurIPS 2011, pages 1881–1889. Curran Associates, Inc., 2011

2011
[59]

Nesterov.Introductory Lectures on Convex Optimization, volume 87 ofApplied Optimization

Y. Nesterov.Introductory Lectures on Convex Optimization, volume 87 ofApplied Optimization. Springer US, Boston, MA, 2004

2004
[60]

N. H. Nguyen and T. D. Tran. Exact recoverability from dense corrupted observations via 𝓁1-minimization. IEEE Transactions on Information Theory, 59(4):2017–2035, 2013

2017
[61]

Prasad, A

A. Prasad, A. S. Suggala, S. Balakrishnan, and P. Ravikumar. Robust estimation via robust gradient estimation. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 82(3):601–627, July 2020

2020
[62]

A Uniﬁed Approach to Robust Mean Estimation.CoRR, abs/1907.00927, 2019

Adarsh Prasad, Sivaraman Balakrishnan, and Pradeep Ravikumar. A Uniﬁed Approach to Robust Mean Estimation.CoRR, abs/1907.00927, 2019

1907 arXiv
[63]

Rousseeuw and V

P. Rousseeuw and V. Yohai. Robust regression by means of S-estimators. In Jürgen Franke, Wolfgang Härdle, and Douglas Martin, editors,Robust and Nonlinear Time Series Analysis, volume 26, pages 256–272. Springer US, New York, NY, 1984

1984
[64]

P. J. Rousseeuw. Least median of squares regression. Journal of the American Statistical Association, 79(388):871–880, 1984

1984
[65]

P. J. Rousseeuw and K. Van Driessen. Computing LTS regression for large data sets.Data Mining and Knowledge Discovery, 12(1):29–45, 2006

2006
[66]

Sasai and H

T. Sasai and H. Fujisawa. Robust estimation with Lasso when outputs are adversarially contaminated. CoRR, abs/2004.05990, 2020

2004 arXiv
[67]

She and A

Y. She and A. B. Owen. Outlier detection using nonconvex penalized regression.Journal of the American Statistical Association, 106(494):626–639, 2011

2011
[68]

Steinhardt, M

J. Steinhardt, M. Charikar, and G. Valiant. Resilience: A criterion for learning in the presence of arbitrary outliers. In9th Innovations in Theoretical Computer Science Conference, ITCS 2018, volume 94 ofLIPIcs, pages 45:1–45:21. Schloss Dagstuhl - Leibniz-Zentrum für Informa...

2018
[69]

Q. Sun, W. Zhou, and J. Fan. Adaptive Huber regression.Journal of the American Statistical Association, 115(529):254–265, 2020

2020
[70]

Talagrand

M. Talagrand. New concentration inequalities in product spaces.Inventiones Mathematicae, 126(3):505–563, November 1996

1996
[71]

J. A. Tropp. An Introduction to Matrix Concentration Inequalities.Foundations and Trends® in Machine Learning, 8(1-2):1–230, 2015

2015
[72]

Vershynin.High-Dimensional Probability: An Introduction with Applications in Data Science

R. Vershynin.High-Dimensional Probability: An Introduction with Applications in Data Science. Number 47 in Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, Cambridge ; New York, NY, 2018

2018
[73]

H. Wang, G. Li, and G. Jiang. Robust regression shrinkage and consistent variable selection through the LAD-Lasso.Journal of Business & Economic Statistics, 25(3):347–355, 2007. 33

2007
[74]

V. J. Yohai. High breakdown-point and high eﬃciency robust estimates for regression.The Annals of Statistics, 15(2):642–656, 1987

1987
[75]

B. Zhu, J. Jiao, and J. Steinhardt. Robust estimation via generalized quasi-gradients.CoRR, abs/2005.14073, 2020. A Auxiliary results We recall the Chernoﬀ bound below [72, 6]: Lemma A.1. LetX1,...,X n be independent{0, 1}-valued random variables. Letˆµ = 1 n ∑n i=1Xi be the e...

2005 arXiv
[76]

If f is α-strongly convex and continuously diﬀerentiable, then for any two pointsx,y∈X , we have ⟨∇f(y)−∇f(x),y−x⟩≥ α‖y−x‖2 2
[77]

If f is twice continuously diﬀerentiable, then∇2f≽αI
[78]

If f is α1-strongly convex andg is α2-strongly convex, thenf +g is (α1 +α2)-strongly convex. 35 B Lower bounds for OLS and multivariate sample mean In this appendix, we derive a lower bound on the𝓁2-error of the OLS estimator by ﬁrst proving a lower bound on the estimation err...
[79]

Moreover, the bound is satisﬁed when the distribution of the covariates is uniform on{−1, 1}p, and the distribution of the noise is deﬁned as in Proposition B.1. Proof. Suppose the covariates and noise are sampled according to the stated distributions; we will show that the lo...
[80]

κlI≼ Σ≼κuI, whereκl∈ (0, 1] and κu≥ 1 are constants
[81]

Let ϵ < c∗, where c∗ is a small enough constant depending onσx,4 and κl κu

The distributionP satisﬁes(4, 2)-hypercontractivity with parameterσx,4. Let ϵ < c∗, where c∗ is a small enough constant depending onσx,4 and κl κu. Suppose n & κ2 u κ2 l · (p logp)σ2 x,4√ϵ + κu κl · p ϵ. Then with probability at least1−O(exp(−Ω(nϵ))), for every subsetS′⊆S such...
[82]

We now show that|ˆγ|≤ 8E|w′| ϵ on the eventE

(18) Furthermore, since bothz′ and (x′)Tβ1 are symmetric random variables, Lemma A.7 applied to the linear model (17) gives us P ( |z′|≥ ˆγ 2 ) ≤ 2P ( |w′|≥ ˆγ 2 ) ≤ 3ϵ 4 <ϵ, which is part (i). We now show that|ˆγ|≤ 8E|w′| ϵ on the eventE. Suppose the contrary. By Markov’s ine...
[83]

Both δ2 2 ϵ2 =O(1) and δ2 3 ϵ3 =O(1): note that δ2 2 ϵ2 ≲ p logp n +σ2 x,kϵ2−2/k 1 +σ2 x,4 log(1/τ) n ϵ1 + log(1/τ) n ≲ 1
[84]

The cardinality ofS2 satisﬁes|S2|≥ (1−ϵ′ 1)n≥ ( 1− ϵ5 20 ) n≥ n 2
[85]

The cardinality ofT2 satisﬁes|T2|≥ (1−c2ϵ′ 1)n≥ ( 1− ϵ5 20 ) n≥ n 2
[86]

We now show that the covariates inT2 satisfy weak stability withϵ6 = ϵ5 3 = Ω(1), L = Ω(1), and U =O(1)

The inequality 4ϵ< 4ϵ′ 1≤ ϵ5 10 holds. We now show that the covariates inT2 satisfy weak stability withϵ6 = ϵ5 3 = Ω(1), L = Ω(1), and U =O(1). SupposeT′ 2⊆T2 is such that|T′ 2|≥ (1−ϵ6)|T2|. Then 1 |T2|λmin   ∑ (x,y)∈T′ 2 xxT  ≤ 1 |T2|λmin   ∑ (x,y)∈T2 xxT  ≤ 1 +δ2 3 ϵ...
[87]

Now letW := supβ:‖β−β∗‖2≤r 1 |T2| ∑ (x,y)∈T2 ∑n i=1 1 ( |y−xTβ|≥ γ )

(20) 47 Crucially, we use the fact that conditioned on the eventE (which is entirely deﬁned in terms of the covariates), the noise random variables{zi =yi−xT i β∗ : (xi,yi)∈S2} remain i.i.d. Now letW := supβ:‖β−β∗‖2≤r 1 |T2| ∑ (x,y)∈T2 ∑n i=1 1 ( |y−xTβ|≥ γ ) . Note that W≤|T2...
[88]

To bound the ﬁnal error betweenβj and β∗, we note thatβj−β∗ = (XXT )−1X(W +b∗−bj)

Iterating the bound, we see that‖bj−b∗‖≤ 3e0 wheneverj≥ log2 ( ‖b0−b∗‖2 e0 ) . To bound the ﬁnal error betweenβj and β∗, we note thatβj−β∗ = (XXT )−1X(W +b∗−bj). Using the deﬁnitions ofG and H, we have ‖βj−β∗‖2 =‖(XXT )−1X(W +b∗−bj)‖2≤‖X(W + (b∗−bj))‖2 λn ≤‖XW‖2 +‖X(b∗−bj)‖2 λ...
[89]

Thus, the eigenvalue conditions of Lemma 4.1 are indeed satisﬁed

Since Λn1≤n1 ( 1 +δ2 2 ϵ2 ) ≤ 1.05n1, we also haveΛn1 =O(λn1). Thus, the eigenvalue conditions of Lemma 4.1 are indeed satisﬁed. We now turn to the deﬁnition ofT2 and show that with this deﬁnition,b∗ is m-sparse. Let S2⊆S be the set ofn− m 4 uncontaminated data points with the...
[90]

Lemma F.3

Therefore,a≤ 4EXi ϵ , completing the proof. Lemma F.3. Suppose the covariatesx1,...,x n are sampled i.i.d. from a distribution satisfying Assumption 1. With probability1− 2 exp(−cnϵ), we have that for any unit vectorv and anyS⊆ [n] with|S|≥ (1−ϵ)n, the following holds: 1 n ∑ i...
[91]

(29) Let T2⊆T1 be a set such that|T2|≥ (1−ϵ2)|T1|

Therefore, for anyT′⊆T1 such that |T′|≤ ϵ2|T1|, Proposition C.4 states that for all unit vectorsv, 1 n1 ∑ x′ i∈T′ |vTx′ i|≤ 2δ2. (29) Let T2⊆T1 be a set such that|T2|≥ (1−ϵ2)|T1|. Since|T1| =n1≥ n 2, we have |T2∩S| =|S|−| S\T|−| T\T1|−| T1\T2|≥ n−ϵ1n−c1ϵ′n−ϵ2n1≥ (1−ϵ1−c1ϵ′−ϵ2)...

Pith tools

Reviewed August 27, 2026 · model on record in the stance chip above.

[1] [1]

Robust Linear Regression: Optimal Rates in Polynomial Time

A. Bakshi and A. Prasad. Robust linear regression: Optimal rates in polynomial time.CoRR, abs/2007.01394, 2020

work page Pith review arXiv 2007

[2] [2]

Balakrishnan, S

S. Balakrishnan, S. S. Du, J. Li, and A. Singh. Computationally eﬃcient robust sparse estimation in high dimensions. InProceedings of the 30th Conference on Learning Theory, COLT 2017, volume 65 ofProceedings of Machine Learning Research, pages 169–212. PMLR, 2017

2017

[3] [3]

Bhatia, P

K. Bhatia, P. Jain, P. Kamalaruban, and P. Kar. Consistent robust regression. InAdvances in Neural Information Processing Systems 30, NeurIPS 2017, pages 2110–2119, 2017

2017

[4] [4]

Bhatia, P

K. Bhatia, P. Jain, and P. Kar. Robust regression via hard thresholding. InAdvances in Neural Information Processing Systems 28, NeurIPS 2015, pages 721–729, 2015

2015

[5] [5]

L. Birgé. An alternative point of view on Lepski’s method.Lecture Notes-Monograph Series, pages 113–133, 2001

2001

[6] [6]

Boucheron, G

S. Boucheron, G. Lugosi, and P. Massart.Concentration Inequalities: A Nonasymptotic Theory of Independence. Oxford University Press, 2013

2013

[7] [7]

S. P. Boyd and L. Vandenberghe.Convex Optimization. Cambridge University Press, Cambridge, UK ; New York, 2004

2004

[8] [8]

S. Bubeck. Convex Optimization: Algorithms and Complexity.Foundations and Trends® in Machine Learning, 8(3-4):231–357, 2015

2015