Deviation optimal learning using greedy Q-aggregation

Abstract

Given a finite family of functions, the goal of model selection aggregation is to construct a procedure that mimics the function from this family that is the closest to an unknown regression function. More precisely, we consider a general regression model with fixed design and measure the distance between functions by the mean squared error at the design points. While procedures based on exponential weights are known to solve the problem of model selection aggregation in expectation, they are, surprisingly, sub-optimal in deviation. We propose a new formulation called Q-aggregation that addresses this limitation; namely, its solution leads to sharp oracle inequalities that are optimal in a minimax sense. Moreover, based on the new formulation, we design greedy Q-aggregation procedures that produce sparse aggregation models achieving the optimal rate. The convergence and performance of these greedy procedures are illustrated and compared with other standard methods on simulated examples.

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

References in corpus (7)

• Aggregation by exponential weighting, sharp PAC-Bayesian bounds and sparsity
• Learning by mirror averaging
• Kullback-Leibler aggregation and misspecified generalized linear models
• Convex Optimization without Projection Steps
• On the optimality of the aggregate with exponential weights for low temperatures
• Sharper lower bounds on the performance of the empirical risk minimization algorithm
• Hyper-sparse optimal aggregation

Cited by in corpus (13)

• Empirical entropy, minimax regret and minimax risk
• Sharp Oracle Inequalities for Aggregation of Affine Estimators
• Learning with Square Loss: Localization through Offset Rademacher Complexity
• Optimal learning with $Q$-aggregation
• Optimal bounds for aggregation of affine estimators
• Sharp oracle bounds for monotone and convex regression through aggregation
• Second order Stein: SURE for SURE and other applications in high-dimensional inference
• Optimal exponential bounds for aggregation of density estimators
• The cost-free nature of optimally tuning Tikhonov regularizers and other ordered smoothers
• Aggregation of supports along the Lasso path
• An adaptive multiclass nearest neighbor classifier
• Aggregation of Affine Estimators
• Bayesian Model Averaging with Exponentiated Least Square Loss