Outlier-robust sparse/low-rank least-squares regression and robust matrix completion
arXiv:2012.06750
Abstract
We study high-dimensional least-squares regression within a subgaussian statistical learning framework with heterogeneous noise. It includes -sparse and -low-rank least-squares regression when a fraction of the labels are adversarially contaminated. We also present a novel theory of trace-regression with matrix decomposition based on a new application of the product process. For these problems, we show novel near-optimal "subgaussian" estimation rates of the form , valid with probability at least . Here, is the optimal uncontaminated rate as a function of the effective dimension but independent of the failure probability . These rates are valid uniformly on , i.e., the estimators' tuning do not depend on . Lastly, we consider noisy robust matrix completion with non-uniform sampling. If only the low-rank matrix is of interest, we present a novel near-optimal rate that is independent of the corruption level . Our estimators are tractable and based on a new "sorted" Huber-type loss. No information on are needed to tune these estimators. Our analysis makes use of novel -optimal concentration inequalities for the multiplier and product processes which could be useful elsewhere. For instance, they imply novel sharp oracle inequalities for Lasso and Slope with optimal dependence on . Numerical simulations confirm our theoretical predictions. In particular, "sorted" Huber regression can outperform classical Huber regression.
arXiv commentThis paper shares content with arXiv:2310.19136 but it is a particular version of it. It will not be further revised. Unlike mentioned in the previous version, (2018) Bellec et al DOES achieve the optimal rate for uncorrupted sparse linear regression (but, unlike this work, assuming noise independent of features)
References in corpus (13)
- Simultaneous analysis of Lasso and Dantzig selector
- On the conditions used to prove oracle results for the Lasso
- High-dimensional regression with noisy and missing data: Provable guarantees with nonconvexity
- Restricted strong convexity and weighted matrix completion: Optimal bounds with noise
- SLOPE - Adaptive variable selection via convex optimization
- Geometric median and robust estimation in Banach spaces
- Robust PCA via Outlier Pursuit
- Matrix Completion via Max-Norm Constrained Optimization
- The lower tail of random quadratic forms, with applications to ordinary least squares and restricted eigenvalue properties
- Compressed sensing with sparse corruptions: Fault-tolerant sparse collocation approximations
- Adaptive Hard Thresholding for Near-optimal Consistent Robust Regression
- Online Robust Regression via SGD on the l1 loss
- Out-of-sample error estimate for robust M-estimators with convex penalty