Outlier-robust sparse/low-rank least-squares regression and robust matrix completion
This work addresses robust statistical learning for sparse and low-rank models, offering practical improvements for applications with noisy or corrupted data, though it is incremental in building on existing robust regression frameworks.
The paper tackles robust high-dimensional regression and matrix completion with adversarial label contamination, achieving near-optimal estimation rates that are independent of failure probability and corruption levels, with tractable estimators based on a sorted Huber loss.
We study high-dimensional least-squares regression within a subgaussian statistical learning framework with heterogeneous noise. It includes $s$-sparse and $r$-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 $r(n,d_{e})+\sqrt{\log(1/δ)/n}+ε\log(1/ε)$, valid with probability at least $1-δ$. Here, $r(n,d_{e})$ is the optimal uncontaminated rate as a function of the effective dimension $d_{e}$ 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 $a$. Our estimators are tractable and based on a new "sorted" Huber-type loss. No information on $(s,r,ε,a)$ 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.