Fast learning rates in statistical inference through aggregation

Abstract

We develop minimax optimal risk bounds for the general learning task consisting in predicting as well as the best function in a reference set $\mathcal{G}$ up to the smallest possible additive term, called the convergence rate. When the reference set is finite and when $n$ denotes the size of the training data, we provide minimax convergence rates of the form $C(\frac{\log |\mathcal{G}|}{n}{)}^v$ with tight evaluation of the positive constant $C$ and with exact $0<v\le 1$, the latter value depending on the convexity of the loss function and on the level of noise in the output distribution. The risk upper bounds are based on a sequential randomized algorithm, which at each step concentrates on functions having both low risk and low variance with respect to the previous step prediction function. Our analysis puts forward the links between the probabilistic and worst-case viewpoints, and allows to obtain risk bounds unachievable with the standard statistical learning approach. One of the key ideas of this work is to use probabilistic inequalities with respect to appropriate (Gibbs) distributions on the prediction function space instead of using them with respect to the distribution generating the data. The risk lower bounds are based on refinements of the Assouad lemma taking particularly into account the properties of the loss function. Our key example to illustrate the upper and lower bounds is to consider the $L_q$-regression setting for which an exhaustive analysis of the convergence rates is given while $q$ ranges in $[1;+\infty [$.

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

References in corpus (8)

• 2004 IMS Medallion Lecture: Local Rademacher complexities and oracle inequalities in risk minimization
• Fast learning rates for plug-in classifiers
• Fast learning rates in statistical inference through aggregation
• Learning by mirror averaging
• Simultaneous adaptation to the margin and to complexity in classification
• Fast learning rates for plug-in classifiers under the margin condition
• Optimal rates of aggregation in classification under low noise assumption
• Iterative Feature Selection In Least Square Regression Estimation

Cited by in corpus (37)

• Sparse Regression Learning by Aggregation and Langevin Monte-Carlo
• Fast learning rates in statistical inference through aggregation
• User-friendly introduction to PAC-Bayes bounds
• A Primer on PAC-Bayesian Learning
• Simpler PAC-Bayesian Bounds for Hostile Data
• Mirror averaging with sparsity priors
• Optimal Quantum Sample Complexity of Learning Algorithms
• PAC-Bayesian Estimation and Prediction in Sparse Additive Models
• Optimal learning with $Q$-aggregation
• Sparsity regret bounds for individual sequences in online linear regression
• Aggregation of predictors for nonstationary sub-linear processes and online adaptive forecasting of time varying autoregressive processes
• Empirical risk minimization is optimal for the convex aggregation problem
• PAC-Bayesian aggregation and multi-armed bandits
• A Generalization Bound for Online Variational Inference
• Active Nearest-Neighbor Learning in Metric Spaces
• Distribution-Free Robust Linear Regression
• On the optimality of the aggregate with exponential weights for low temperatures
• Adaptive Minimax Estimation over Sparse ${\ell }_q$-Hulls
• Linear regression through PAC-Bayesian truncation
• Fast rates with high probability in exp-concave statistical learning
• Hyper-sparse optimal aggregation
• Online Nonparametric Regression with General Loss Functions
• Risk bounds in linear regression through PAC-Bayesian truncation
• A Tight Excess Risk Bound via a Unified PAC-Bayesian-Rademacher-Shtarkov-MDL Complexity
• Exponential Savings in Agnostic Active Learning through Abstention
• Fast Rates for Online Prediction with Abstention
• No fast exponential deviation inequalities for the progressive mixture rule
• Strength from Weakness: Fast Learning Using Weak Supervision
• A Quasi-Bayesian Perspective to Online Clustering
• Fast rates in statistical and online learning
• Sequential Learning of Principal Curves: Summarizing Data Streams on the Fly
• On the Exponentially Weighted Aggregate with the Laplace Prior
• From Stochastic Mixability to Fast Rates
• Non-exponentially weighted aggregation: regret bounds for unbounded loss functions
• The exponentially weighted average forecaster in geodesic spaces of non-positive curvature
• Localization, Convexity, and Star Aggregation
• Learning and adaptive estimation for marker-dependent counting processes