General nonexact oracle inequalities for classes with a subexponential envelope
From MaRDI portal
(Redirected from Publication:447832)
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 and nuclear norms regularization functions satisfy oracle inequalities with a residual term that decreases like for every -loss functions (), 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.
Recommendations
- Oracle inequalities in empirical risk minimization and sparse recovery problems. École d'Été de Probabilités de Saint-Flour XXXVIII-2008.
- Estimation bounds and sharp oracle inequalities of regularized procedures with Lipschitz loss functions
- Oracle inequalities for local and global empirical risk minimizers
- Oracle inequalities for convex loss functions with nonlinear targets
- \(\ell _{1}\)-regularized linear regression: persistence and oracle inequalities
Cites work
- \(\ell _{1}\)-regularized linear regression: persistence and oracle inequalities
- A tail inequality for suprema of unbounded empirical processes with applications to Markov chains
- Aggregation via empirical risk minimization
- Compressed sensing
- Concentration inequalities and model selection. Ecole d'Eté de Probabilités de Saint-Flour XXXIII -- 2003.
- Empirical minimization
- Empirical processes with a bounded \(\psi_1\) diameter
- Estimation of dependences based on empirical data. Transl. from the Russian by Samuel Kotz
- General nonexact oracle inequalities for classes with a subexponential envelope
- High-dimensional generalized linear models and the lasso
- High-dimensional graphs and variable selection with the Lasso
- scientific article; zbMATH DE number 3772326 (Why is no real title available?)
- scientific article; zbMATH DE number 49190 (Why is no real title available?)
- scientific article; zbMATH DE number 1552476 (Why is no real title available?)
- scientific article; zbMATH DE number 1552503 (Why is no real title available?)
- scientific article; zbMATH DE number 845714 (Why is no real title available?)
- Inequalities of Bernstein-Jackson-type and the degree of compactness of operators in Banach spaces
- Lasso-type recovery of sparse representations for high-dimensional data
- Local Rademacher complexities and oracle inequalities in risk minimization. (2004 IMS Medallion Lecture). (With discussions and rejoinder)
- Lower Bounds for the Empirical Minimization Algorithm
- Obtaining fast error rates in nonconvex situations
- On generic chaining and the smallest singular value of random matrices with heavy tails
- On the optimality of the aggregate with exponential weights for low temperatures
- Reconstruction and subgaussian operators in asymptotic geometric analysis
- Regularization in kernel learning
- Risk bounds for model selection via penalization
- Risk bounds for statistical learning
- Sharper bounds for Gaussian and empirical processes
- Sharper lower bounds on the performance of the empirical risk minimization algorithm
- Simultaneous analysis of Lasso and Dantzig selector
- Some sharp performance bounds for least squares regression with L₁ regularization
- Sparse Approximate Solutions to Linear Systems
- Sparse recovery in convex hulls via entropy penalization
- Sparsity in penalized empirical risk minimization
- Sparsity oracle inequalities for the Lasso
- Sup-norm convergence rate and sign concentration property of Lasso and Dantzig estimators
- Support Vector Machines
- The Adaptive Lasso and Its Oracle Properties
- The Dantzig selector and sparsity oracle inequalities
- The Dantzig selector: statistical estimation when \(p\) is much larger than \(n\). (With discussions and rejoinder).
- The Generic Chaining
- The importance of convexity in learning with squared loss
- Weak convergence and empirical processes. With applications to statistics
Cited in
(15)- \(\ell _{1}\)-regularized linear regression: persistence and oracle inequalities
- On the optimality of the empirical risk minimization procedure for the convex aggregation problem
- Empirical variance minimization with applications in variance reduction and optimal control
- Estimation bounds and sharp oracle inequalities of regularized procedures with Lipschitz loss functions
- Aggregation of affine estimators
- Posterior concentration and fast convergence rates for generalized Bayesian learning
- Oracle inequalities for local and global empirical risk minimizers
- Inverse statistical learning
- General nonexact oracle inequalities for classes with a subexponential envelope
- Oracle inequalities in empirical risk minimization and sparse recovery problems. École d'Été de Probabilités de Saint-Flour XXXVIII-2008.
- Sharp oracle bounds for monotone and convex regression through aggregation
- Sample average approximation with heavier tails II: localization in stochastic convex optimization and persistence results for the Lasso
- Nonexact oracle inequalities, r-learnability, and fast rates
- A quadratic sample complexity reduction for agnostic learning via quantum algorithms
- Exponentially weighted averaging of varying-coefficient partially linear models
This page was built for publication: General nonexact oracle inequalities for classes with a subexponential envelope
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q447832)
