I present a new online learning algorithm that extends the exponentiated gradient framework to infinite dimensional spaces. My analysis shows that the algorithm is implicitly able to estimate the L_2 norm of the unknown competitor, U, achieving a regret bound of the order of (O)(U log(U T + 1))T~(1/2)), instead of the standard (O)((U~2 + 1)T~(1/2)), achievable without knowing U. For this analysis, I introduce novel tools for algorithms with time-varying regularizes, through the use of local smoothness. Through a lower bound, I also show that the algorithm is optimal up to log(UT)~(1/2) term for linear and Lipschitz losses.
展开▼
