Robust linear regression: optimal rates in polynomial time

DOI10.1145/3406325.3451001MaRDI QIDQ6065174zbMATH OpenOpenAlexFDO

Authors Ainesh Bakshi, Adarsh Prasad

Publication date 14 November 2023

Published in Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2007.01394

zbMATH Keywords

heavy-tailed distributionsrobust linear regressionsum-of-squares

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Abstract: We obtain robust and computationally efficient estimators for learning several linear models that achieve statistically optimal convergence rate under minimal distributional assumptions. Concretely, we assume our data is drawn from a $k$-hypercontractive distribution and an $epsilon$-fraction is adversarially corrupted. We then describe an estimator that converges to the optimal least-squares minimizer for the true distribution at a rate proportional to $epsilo{n}^{2-2/k}$, when the noise is independent of the covariates. We note that no such estimator was known prior to our work, even with access to unbounded computation. The rate we achieve is information-theoretically optimal and thus we resolve the main open question in Klivans, Kothari and Meka [COLT'18]. Our key insight is to identify an analytic condition that serves as a polynomial relaxation of independence of random variables. In particular, we show that when the moments of the noise and covariates are negatively-correlated, we obtain the same rate as independent noise. Further, when the condition is not satisfied, we obtain a rate proportional to $epsilo{n}^{2-4/k}$, and again match the information-theoretic lower bound. Our central technical contribution is to algorithmically exploit independence of random variables in the "sum-of-squares" framework by formulating it as the aforementioned polynomial inequality.

Cited in

(11)

• Scale calibration for high-dimensional robust regression
• Generalized resilience and robust statistics
• Sum-of-squares lower bounds for densest k-subgraph
• Algorithms approaching the threshold for semi-random planted clique
• Distributed robust estimation and inference with contaminated data
• Sparse linear regression when noises and covariates are heavy-tailed and contaminated by outliers
• Outlier robust and sparse estimation of linear regression coefficients
• Robust Regression with Covariate Filtering: Heavy Tails and Adversarial Contamination
• Polynomial-time sum-of-squares can robustly estimate mean and covariance of Gaussians optimally
• Robustly learning mixtures of k arbitrary Gaussians
• Estimation beyond missing (completely) at random

This page was built for publication: Robust linear regression: optimal rates in polynomial time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6065174)