Learning subgaussian classes : Upper and minimax bounds

Abstract

We obtain sharp oracle inequalities for the empirical risk minimization procedure in the regression model under the assumption that the target Y and the model F are subgaussian. The bound we obtain is sharp in the minimax sense if F is convex. Moreover, under mild assumptions on F, the error rate of ERM remains optimal even if the procedure is allowed to perform with constant probability. A part of our analysis is a new proof of minimax results for the gaussian regression model.

learning theory, empirical process, minimax rates, Topics in Learning Theory - Societe Mathematique de France, (S. Boucheron and N. Vayatis Eds.). 2016

References in corpus (4)

• A probabilistic approach to the geometry of the \ell_p^n-ball
• Matrix Completion via Max-Norm Constrained Optimization
• Concentration via chaining method and its applications
• Upper bounds on product and multiplier empirical processes

Cited by in corpus (18)

• High-dimensional estimation with geometric constraints
• Concentration in unbounded metric spaces and algorithmic stability
• Geometric Inference for General High-Dimensional Linear Inverse Problems
• High-Dimensional Estimation of Structured Signals from Non-Linear Observations with General Convex Loss Functions
• Learning with Square Loss: Localization through Offset Rademacher Complexity
• Performance of empirical risk minimization in linear aggregation
• The generalized Lasso with non-linear observations
• Regularization and the small-ball method II: complexity dependent error rates
• Estimation bounds and sharp oracle inequalities of regularized procedures with Lipschitz loss functions
• Fast learning rates with heavy-tailed losses
• Learning from MOM's principles: Le Cam's approach
• Minimax rate of convergence and the performance of ERM in phase recovery
• Optimal learning via local entropies and sample compression
• Empirical Risk Minimization under Random Censorship: Theory and Practice
• A spectral algorithm for robust regression with subgaussian rates
• Sum-of-squares meets square loss: Fast rates for agnostic tensor completion
• On the benefits of maximum likelihood estimation for Regression and Forecasting
• Learning with Semi-Definite Programming: new statistical bounds based on fixed point analysis and excess risk curvature