Progressive mixture rules are deviation sub optimal

· (X1, Y1), . . . , (Xn, Yn) i.i.d.

XX

Y R

· g1, . . . , gd (prediction) functions from X to R
quadratic risk: R(g ) = E - g (X )

J.-Y. Audib ert Poster ID T14

· Problem: predict as wellYas the best function gi, i = 1, . . . , d for the 2 · Known solution: the progressive mixture rule, a.k.a. the exponentially
weighted average algorithm, which satisfies
g E R(^) - mini=1,...,d R(gi)  Cst lon d g

(A)

· Proposed solution: minimize the empirical risk among functions in the
star shap ed d=1[^ERM; gi], where ^ERM is the ERM among {g1, . . . , gd}. g g i Known solution 1/n exp ectation rate (A)  1/ n deviation rate Prop osed solution 1/n exp ectation rate 1/n deviation rate

!!!

New results in blue