Efficient Algorithms and Lower Bounds for Robust Linear Regression

DOI10.1137/1.9781611975482.170zbMath1432.68616arXiv1806.00040OpenAlexW2806473647MaRDI QIDQ5236361

Weihao Kong, Ilias Diakonikolas, Alistair Stewart

Publication date: 15 October 2019

Published in: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Linear regression; mixed models (62J05) Analysis of algorithms (68W40) Robustness and adaptive procedures (parametric inference) (62F35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (12)

Robust sub-Gaussian estimation of a mean vector in nearly linear time ⋮ Tensor clustering with planted structures: statistical optimality and computational limits ⋮ Unnamed Item ⋮ Statistical-computational trade-offs in tensor PCA and related problems via communication complexity ⋮ Robust supervised learning with coordinate gradient descent ⋮ Learning under \(p\)-tampering poisoning attacks ⋮ ERM and RERM are optimal estimators for regression problems when malicious outliers corrupt the labels ⋮ Robust regression via mutivariate regression depth ⋮ Finite sample properties of parametric MMD estimation: robustness to misspecification and dependence ⋮ Scale calibration for high-dimensional robust regression ⋮ Mean estimation and regression under heavy-tailed distributions: A survey ⋮ Generalized resilience and robust statistics

This page was built for publication: Efficient Algorithms and Lower Bounds for Robust Linear Regression