B0158
Title: Novel adaptive algorithms for prediction of individual sequences
Authors: Alexander Rakhlin - University of Pennsylvania (United States) [presenting]
Abstract: The focus is on online prediction with covariates (online supervised learning) with data-dependent regret bounds in terms of empirical Rademacher averages. Such performance measures are known to be optimal in batch learning with i.i.d. data. Surprisingly, we are able to achieve these results for individual sequences. The development relies on a fundamental result about equivalence of decoupling inequalities for martingales and existence of certain special functions. Our algorithms are efficient whenever these special functions can be computed.