Regularization and the small-ball method I: sparse recovery

2016/01/21 by Lecué, Guillaume, Mendelson, Shahar · 2 citations
#FOS: Mathematics #Statistics Theory (math.ST)

paper · doi:10.48550/arxiv.1601.05584

Abstract

We obtain bounds on estimation error rates for regularization procedures of the form f ∈ \rm argmin_{f∈ F}((1)/(N)∑_i=1^N(Y_i-f(X_i))²+λΨ(f)) when Ψ is a norm and F is convex. Our approach gives a common framework that may be used in the analysis of learning problems and regularization problems alike. In particular, it sheds some light on the role various notions of sparsity have in regularization and on their connection with the size of subdifferentials of Ψ in a neighbourhood of the true minimizer. As `proof of concept' we extend the known estimates for the LASSO, SLOPE and trace norm regularization.

Cited by

• Complexity Dependent Error Rates for Physics-informed Statistical Learning via the Small-ball Method
• Simple and Sharp Generalization Bounds via Lifting

Related

• Regularization and the small-ball method II: complexity dependent error rates
• Estimation bounds and sharp oracle inequalities of regularized\n procedures with Lipschitz loss functions
• Sparse recovery via nonconvex regularized M-estimators over ℓ_q-balls
• Convergence rates in ℓ¹-regularization when the basis is not smooth enough
• Sparse Recovery via Partial Regularization: Models, Theory and Algorithms