[Ml-stat-talks] Sasha Rakhlin speaks on statistical and game-theoretic learning on Apr. 2

Ramon van Handel rvan at Princeton.EDU
Fri Mar 30 09:09:46 EDT 2012

Dear all,
Sasha Rakhlin will speak at the stochastic analysis seminar next monday.
His talk should be of particular interest for those of you interested in 
machine learning or empirical processes.  Details are below.  Best,
    -- Ramon

=== ORFE *Stochastic Analysis Seminar* Announcement ===

DATE:  Monday, April 2, 2012
TIME:  12:30pm
LOCATION:  Bendheim Center 103
SPEAKER:  Alexander Rakhlin, University of Pennsylvania
TITLE:  From Statistical to Game-Theoretic Learning

ABSTRACT:  The study of prediction within the realm of Statistical 
Learning Theory is intertwined with the study of the supremum of an 
empirical process. The supremum can be analyzed with classical 
tools: Vapnik-Chervonenkis and scale-sensitive combinatorial dimensions, 
covering and packing numbers, and Rademacher averages. Consistency of 
empirical risk minimization is known to be closely related to the uniform 
Law of Large Numbers for function classes. In contrast to the i.i.d. 
scenario, in the sequential prediction framework we are faced with an 
individual sequence of data on which we place no probabilistic 
assumptions. The problem of universal prediction of such deterministic 
sequences has been studied within Statistics, Information Theory, Game 
Theory, and Computer Science. However, general tools for analysis have 
been lacking, and most results have been obtained on a case-by-case basis. 
In this talk, we show that the study of sequential prediction is closely 
related to the study of the supremum of a certain dyadic martingale 
process on trees. We develop analogues of the Rademacher complexity, 
covering numbers and scale-sensitive dimensions, which can be seen as 
temporal generalizations of the classical results. The complexities we 
define also ensure uniform convergence for non-i.i.d. data, extending the 
Glivenko-Cantelli type results. Analogues of local Rademacher complexities 
can be employed for obtaining fast rates and developing adaptive 
procedures. Our understanding of the inherent complexity of sequential 
prediction is complemented by a recipe that can be used for developing new 
algorithms. This is joint work with Karthik Sridharan and Ambuj Tewari.

More information about the Ml-stat-talks mailing list