Deviation optimal learning using greedy

Given a finite family of functions, the goal of model selection aggrega-tion 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 be-tween functions by the mean squared error at the design points. While proce-dures based on exponential weights are known to solve the problem of model selection aggregation in expectation, they are, surprisingly, sub-optimal in de-viation. 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 de-sign greedy Q-aggregation procedures that produce sparse aggregation mod-els achieving the optimal rate. The convergence and performance of these greedy procedures are illustrated and compared with other standard methods on simulated examples. 1. Introduction. Mode