Robust Methods for High-Dimensional Linear Learning
Ibrahim Merad, Stéphane Gaïffas; 24(165):1−44, 2023.
Abstract
This paper presents statistically robust and computationally efficient linear learning methods for high-dimensional batch settings, where the number of features (d) may exceed the sample size (n). The authors propose two algorithms, depending on whether the loss function is gradient-Lipschitz or not, in a generic learning setting. They then apply this framework to various applications such as vanilla sparse, group-sparse, and low-rank matrix recovery. The resulting learning algorithms are efficient and robust, achieving near-optimal estimation rates under heavy-tailed distributions and the presence of outliers. For vanilla s-sparsity, the authors are able to achieve the s*log(d)/n rate under heavy-tails and eta-corruption, with a computational cost comparable to non-robust approaches. The authors provide an efficient implementation of their algorithms in an open-source Python library called linlearn, and present numerical experiments that confirm their theoretical findings and compare their approach to other recent methods proposed in the literature.
[abs]