General nonexact oracle inequalities for classes with a subexponential envelope

Abstract

We show that empirical risk minimization procedures and regularized empirical risk minimization procedures satisfy nonexact oracle inequalities in an unbounded framework, under the assumption that the class has a subexponential envelope function. The main novelty, in addition to the boundedness assumption free setup, is that those inequalities can yield fast rates even in situations in which exact oracle inequalities only hold with slower rates. We apply these results to show that procedures based on ${\ell }_1$ and nuclear norms regularization functions satisfy oracle inequalities with a residual term that decreases like $1/n$ for every $L_q$-loss functions ($q\ge 2$), while only assuming that the tail behavior of the input and output variables are well behaved. In particular, no RIP type of assumption or "incoherence condition" are needed to obtain fast residual terms in those setups. We also apply these results to the problems of convex aggregation and model selection.

Published in at http://dx.doi.org/10.1214/11-AOS965 the Annals of Statistics (http://www.imstat.org/aos/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (9)

• Lasso-type recovery of sparse representations for high-dimensional data
• High-dimensional generalized linear models and the lasso
• Sparsity oracle inequalities for the Lasso
• The Dantzig selector and sparsity oracle inequalities
• Sup-norm convergence rate and sign concentration property of Lasso and Dantzig estimators
• Some sharp performance bounds for least squares regression with $L_1$ regularization
• Sparse recovery in convex hulls via entropy penalization
• Sharper lower bounds on the performance of the empirical risk minimization algorithm
• No fast exponential deviation inequalities for the progressive mixture rule