Aggregated estimators and empirical complexity for least square regression

Numerous empirical results have shown that combining regression procedures can be a very efficient method. This work provides PAC bounds for the L-2 generalization error of such methods. The interest of these bounds are twofold. First, it gives for any aggregating procedure a bound for the expected risk depending on the empirical risk and the empirical complexity measured by the Kullback-Leibler divergence between the aggregating distribution rho and a prior distribution pi and by the empirical mean of the variance of the regression functions under the probability rho. Secondly, by structural risk minimization, we derive an aggregating procedure which takes advantage of the unknown properties of the best mixture f: when the best convex combination f of d regression functions belongs to the d initial functions (i.e. when combining does not make the bias decrease), the convergence rate is of order (logd)/N. In the worst case, our combining procedure achieves a convergence rate of order root(logd)/N which is known to be optimal in a uniform sense when d > rootN (see [A. Nemirovski, in: Probability Summer School, Saint Flour, 1998; Y. Yang, Aggregating regression procedures for a better performance, 2001]). As in AdaBoost, our aggregating distribution tends to favor functions which disagree with the mixture on mispredicted points. Our algorithm is tested on artificial classification data (which have been also used for testing other boosting methods, such as AdaBoost). (C) 2004 Elsevier SAS. All rights reserved.