Robust and Sparse Estimation of Linear Regression Coefficients with Heavy-tailed Noises and Covariates

Robust and sparse estimation of linear regression coefficients is investigated. The situation addressed by the present paper is that covariates and noises are sampled from heavy-tailed distributions, and the covariates and noises are contaminated by malicious outliers. Our estimator can be computed efficiently. Further, the error bound of the estimator is nearly optimal.

• Publication year

  2022

• Venue

  arXiv.org

• Publication date

  2022-06-15

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.48550/arXiv.2206.07594arXiv 2206.07594
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Statistics For High Dimensional Data Methods Theory And

  2022cited by this paper
• Efficiently learning halfspaces with Tsybakov noise

  2021cited by this paper
• Optimal Robust Linear Regression in Nearly Linear Time

  2020cited by this paper
• Robust Regression with Covariate Filtering: Heavy Tails and Adversarial Contamination

  2020influential reference
• The Complexity of Adversarially Robust Proper Learning of Halfspaces with Agnostic Noise

  2020cited by this paper
• Outlier-robust sparse/low-rank least-squares regression and robust matrix completion

  2020cited by this paper
• Robust linear regression: optimal rates in polynomial time

  2020cited by this paper
• A Robust Univariate Mean Estimator is All You Need

  2020cited by this paper
• Learning Halfspaces with Massart Noise Under Structured Distributions

  2020cited by this paper
• Efficiently Learning Adversarially Robust Halfspaces with Noise

  2020cited by this paper
• All-in-one robust estimator of the Gaussian mean

  2020cited by this paper
• Outlier-robust estimation of a sparse linear model using 𝓁1-penalized Huber's M-estimator

  2019cited by this paper
• Robust sub-Gaussian estimation of a mean vector in nearly linear time

  2019cited by this paper
• Fast Mean Estimation with Sub-Gaussian Rates

  2019cited by this paper
• Robust inference via multiplier bootstrap

  2019cited by this paper
• Recent Advances in Algorithmic High-Dimensional Robust Statistics

  2019cited by this paper
• ERM and RERM are optimal estimators for regression problems when malicious outliers corrupt the labels

  2019cited by this paper
• Outlier-Robust High-Dimensional Sparse Estimation via Iterative Filtering

  2019cited by this paper
• A Fast Spectral Algorithm for Mean Estimation with Sub-Gaussian Rates

  2019cited by this paper
• Robust multivariate mean estimation: The optimality of trimmed mean

  2019cited by this paper
• Quantum Entropy Scoring for Fast Robust Mean Estimation and Improved Outlier Detection

  2019cited by this paper
• Distribution-Independent PAC Learning of Halfspaces with Massart Noise

  2019cited by this paper
• Faster Algorithms for High-Dimensional Robust Covariance Estimation

  2019cited by this paper
• High Dimensional Robust Sparse Regression

  2018cited by this paper
• Robust moment estimation and improved clustering via sum of squares

  2018cited by this paper
• Mean estimation with sub-Gaussian rates in polynomial time

  2018cited by this paper
• Robust estimation via robust gradient estimation

  2018cited by this paper
• Robust covariance estimation under $L_{4}-L_{2}$ norm equivalence

  2018cited by this paper
• High-Dimensional Robust Mean Estimation in Nearly-Linear Time

  2018cited by this paper
• Efficient Algorithms and Lower Bounds for Robust Linear Regression

  2018cited by this paper
• Robust regression via mutivariate regression depth

  2017cited by this paper
• Being Robust (in High Dimensions) Can Be Practical

  2017cited by this paper
• Robustly Learning a Gaussian: Getting Optimal Error, Efficiently

  2017cited by this paper
• Computationally Efficient Robust Sparse Estimation in High Dimensions

  2017influential reference
• Slope meets Lasso: Improved oracle bounds and optimality

  2016cited by this paper
• Agnostic Estimation of Mean and Covariance

  2016cited by this paper
• A SHRINKAGE PRINCIPLE FOR HEAVY-TAILED DATA: HIGH-DIMENSIONAL ROBUST LOW-RANK MATRIX RECOVERY.

  2016influential reference
• Robust Estimators in High Dimensions without the Computational Intractability

  2016cited by this paper
• I-LAMM FOR SPARSE LEARNING: SIMULTANEOUS CONTROL OF ALGORITHMIC COMPLEXITY AND STATISTICAL ERROR.

  2015cited by this paper
• Robust covariance and scatter matrix estimation under Huber’s contamination model

  2015cited by this paper
• SLOPE is Adaptive to Unknown Sparsity and Asymptotically Minimax

  2015cited by this paper
• Robust matrix completion

  2014cited by this paper
• Statistical and computational trade-offs in estimation of sparse principal components

  2014influential reference
• Sparse Representation of a Polytope and Recovery of Sparse Signals and Low-Rank Matrices

  2013cited by this paper
• Concentration Inequalities: A Nonasymptotic Theory of Independence

  2013cited by this paper
• Tail bounds via generic chaining

  2013influential reference
• Robust Sparse Regression under Adversarial Corruption

  2013cited by this paper
• Noisy low-rank matrix completion with general sampling distribution

  2012cited by this paper
• Compressed Sensing

  2012cited by this paper
• Robust Lasso With Missing and Grossly Corrupted Observations

  2011cited by this paper
• Restricted Eigenvalue Properties for Correlated Gaussian Designs

  2010cited by this paper
• Outlier Detection Using Nonconvex Penalized Regression

  2010cited by this paper
• Restricted strong convexity and weighted matrix completion: Optimal bounds with noise

  2010cited by this paper
• Nearly unbiased variable selection under minimax concave penalty

  2010cited by this paper
• Nuclear norm penalization and optimal rates for noisy low rank matrix completion

  2010cited by this paper
• Estimation of high-dimensional low-rank matrices

  2009cited by this paper
• Estimation of (near) low-rank matrices with noise and high-dimensional scaling

  2009cited by this paper
• Model selection and estimation in regression with grouped variables

  2006cited by this paper
• Smooth minimization of non-smooth functions

  2005cited by this paper
• The Dantzig selector: Statistical estimation when P is much larger than n

  2005cited by this paper
• Addendum: Regularization and variable selection via the elastic net

  2005cited by this paper
• Prox-Method with Rate of Convergence O(1/t) for Variational Inequalities with Lipschitz Continuous Monotone Operators and Smooth Convex-Concave Saddle Point Problems

  2004cited by this paper
• Variable Selection via Nonconcave Penalized Likelihood and its Oracle Properties

  2001cited by this paper
• About the constants in Talagrand's concentration inequalities for empirical processes

  2000cited by this paper
• Regression Shrinkage and Selection via the Lasso

  1996cited by this paper

• Tractable Gaussian Phase Retrieval with Heavy Tails and Adversarial Corruption with Near-Linear Sample Complexity

  2026cites this paper
• Robust Sparse Regression with Non-Isotropic Designs

  2024influential citation
• High-dimensional robust regression under heavy-tailed data: asymptotics and universality

  2023cites this paper
• Robust methods for high-dimensional linear learning

  2022cites this paper
• Outlier Robust and Sparse Estimation of Linear Regression Coefficients

  2022influential citation