2018/10/07 by Antoine Dedieu, Dedieu, Antoine
Computer Science · Engineering · Mathematics · #FOS: Mathematics #Machine Learning and Algorithms #Sparse and Compressive Sensing Techniques #Statistical Methods and Inference #Statistics Theory (math.ST)
paper · pdf · doi:10.48550/arxiv.1810.03081
openalex publication_date 2018/10/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We prove an L2 recovery bound for a family of sparse estimators defined as minimizers of some empirical loss functions -- which include hinge loss and logistic loss. More precisely, we achieve an upper-bound for coefficients estimation scaling as (k*/n)log(p/k*): n,p is the size of the design matrix and k* the dimension of the theoretical loss minimizer. This is done under standard assumptions, for which we derive stronger versions of a cone condition and a restricted strong convexity. Our bound holds with high probability and in expectation and applies to an L1-regularized estimator and to a recently introduced Slope estimator, which we generalize for classification problems. Slope presents the advantage of adapting to unknown sparsity. Thus, we propose a tractable proximal algorithm to compute it and assess its empirical performance. Our results match the best existing bounds for classification and regression problems.