Regularization and the small-ball method. II: Complexity dependent error rates

MaRDI QIDQ4637079zbMATH OpenFDO

Authors Guillaume Lecué, Shahar Mendelson

Publication date 17 April 2018

Full work available at URL https://arxiv.org/abs/1608.07681, http://jmlr.csail.mit.edu/papers/v18/16-422.html

zbMATH Keywords

empirical processes theoryhigh-dimensional statisticslearning theoryminimax ratesregularization

Mathematics Subject Classification ID

Interacting random processes; statistical mechanics type models; percolation theory (60K35) Nonparametric regression and quantile regression (62G08) Learning and adaptive systems in artificial intelligence (68T05)

Abstract: For a convex class of functions $F$, a regularization functions $Psi(cdot)$ and given the random data $(X_i,Y_i{)}_{i=1}^N$, we study estimation properties of regularization procedures of the form �egin{equation*} hat f in { m argmin}_{fin F}Big(frac{1}{N}sum_{i=1}^N�ig(Y_i-f(X_i)�ig)^2+lambda Psi(f)Big) end{equation*} for some well chosen regularization parameter $lambda$. We obtain bounds on the $L_2$ estimation error rate that depend on the complexity of the "true model" $F^{\ast }:=finF:Psi(f)leqPsi(f^{\ast })$, where $f^{\ast }in{margmin}_{finF}mathbbE(Y-f(X){)}^2$ and the $(X_i,Y_i)$'s are independent and distributed as $(X,Y)$. Our estimate holds under weak stochastic assumptions -- one of which being a small-ball condition satisfied by $F$ -- and for rather flexible choices of regularization functions $Psi(cdot)$. Moreover, the result holds in the learning theory framework: we do not assume any a-priori connection between the output $Y$ and the input $X$. As a proof of concept, we apply our general estimation bound to various choices of $Psi$, for example, the $el{l}_p$ and $S_p$-norms (for $pgeq1$), weak-$el{l}_p$, atomic norms, max-norm and SLOPE. In many cases, the estimation rate almost coincides with the minimax rate in the class $F^{\ast }$.

Recommendations

• Regularization and the small-ball method. I: Sparse recovery
• Estimation bounds and sharp oracle inequalities of regularized procedures with Lipschitz loss functions
• Learning rates for least square regressions with coefficient regularization
• Complexity control in statistical learning
• Local Rademacher complexities

Cites work

• \(\ell _{1}\)-regularized linear regression: persistence and oracle inequalities
• A remark on the diameter of random sections of convex bodies
• Adapting to unknown sparsity by controlling the false discovery rate
• Adaptive Minimax Estimation over Sparse \ell_q-Hulls
• Bounding the smallest singular value of a random matrix without concentration
• Estimation of high-dimensional low-rank matrices
• Exact matrix completion via convex optimization
• Exponential screening and optimal rates of sparse estimation
• Gaussian averages of interpolated bodies and applications to approximate reconstruction
• Generalized Cross-Validation as a Method for Choosing a Good Ridge Parameter
• scientific article; zbMATH DE number 6388313 (Why is no real title available?)
• scientific article; zbMATH DE number 49190 (Why is no real title available?)
• scientific article; zbMATH DE number 50401 (Why is no real title available?)
• scientific article; zbMATH DE number 845714 (Why is no real title available?)
• scientific article; zbMATH DE number 962825 (Why is no real title available?)
• scientific article; zbMATH DE number 3100841 (Why is no real title available?)
• Interactions between compressed sensing random matrices and high dimensional geometry
• Learning Theory
• Learning without concentration
• Matrix completion via max-norm constrained optimization
• Minimax Rates of Estimation for High-Dimensional Linear Regression Over \ell_q-Balls
• Minimax risk over \(l_ p\)-balls for \(l_ q\)-error
• Minimax risks for sparse regressions: ultra-high dimensional phenomenons
• Noisy low-rank matrix completion with general sampling distribution
• Nuclear-norm penalization and optimal rates for noisy low-rank matrix completion
• On the Gap Between Restricted Isometry Properties and Sparse Recovery Conditions
• Oracle inequalities in empirical risk minimization and sparse recovery problems. École d'Été de Probabilités de Saint-Flour XXXVIII-2008.
• Performance of empirical risk minimization in linear aggregation
• Recovering Low-Rank Matrices From Few Coefficients in Any Basis
• Regularization and the small-ball method. I: Sparse recovery
• Restricted strong convexity and weighted matrix completion: optimal bounds with noise
• Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
• Sharp Oracle Inequalities for High-Dimensional Matrix Prediction
• Simultaneous analysis of Lasso and Dantzig selector
• SLOPE is adaptive to unknown sparsity and asymptotically minimax
• SLOPE-adaptive variable selection via convex optimization
• Small ball probabilities for linear images of high-dimensional distributions
• Some limit theorems for empirical processes (with discussion)
• Sparse recovery under weak moment assumptions
• Statistics for high-dimensional data. Methods, theory and applications.
• Structured sparsity and generalization
• The convex geometry of linear inverse problems
• The Generic Chaining
• The Lasso as an \(\ell _{1}\)-ball model selection procedure
• The Power of Convex Relaxation: Near-Optimal Matrix Completion
• The Supremum of Some Canonical Processes
• Tight Oracle Inequalities for Low-Rank Matrix Recovery From a Minimal Number of Noisy Random Measurements
• Upper bounds on product and multiplier empirical processes
• Weak convergence and empirical processes. With applications to statistics

Cited in

(13)

• Regularization and the small-ball method. I: Sparse recovery
• On the robustness of minimum norm interpolators and regularized empirical risk minimizers
• Robust machine learning by median-of-means: theory and practice
• Estimation bounds and sharp oracle inequalities of regularized procedures with Lipschitz loss functions
• Solving equations of random convex functions via anchored regression
• Generic error bounds for the generalized Lasso with sub-exponential data
• Extending the scope of the small-ball method
• Robust high dimensional learning for Lipschitz and convex losses
• Simultaneous phase retrieval and blind deconvolution via convex programming
• Local convergence rates of the nonparametric least squares estimator with applications to transfer learning
• Performance of empirical risk minimization for linear regression with dependent data
• Generalization bounds: perspectives from information theory and PAC-Bayes
• Adversarial Estimation of Riesz Representers

Describes a project that uses

Uses Software

• ElemStatLearn

This page was built for publication: Regularization and the small-ball method. II: Complexity dependent error rates

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4637079)