"From Statistical Learning to Game-Theoretic Learning" (Next Week at the Statistics Seminar)
Our usual assumption in statistics is that the world is capricious and
haphazard, but is not trying fooling us. When we are fooled, and fall
into error, it is due to fluctuations and our own
intemperance, not to malice. We carry this attitude over to machine learning;
when our models over-fit, we think it an excess of optimism (essentially,
the winner's
curse). Theologically, we think of evil as an absence (the lack of
infinite data), rather than an independent and active force. Theoretical
computer scientists, however, are traditionally rather more Manichean. They
have developed a school of machine learning which tries to devise algorithms
which are guaranteed to do well no matter what data the Adversary throws at
them, somewhat misleadingly known as "online learning". (A fine introduction
to this is Prediction, Learning,
and Games.) There turn out to be important connections between
online and statistical learning, and one of the leading explorers of those
connections is
- Alexander Rakhlin, "From Statistical Learning to Game-Theoretic Learning" (arxiv:1006.1138)
- Abstract: Statistical Learning Theory studies the problem of
estimating (learning) an unknown function given a class of hypotheses and an
i.i.d. sample of data. Classical results show that combinatorial parameters
(such as Vapnik-Chervonenkis and scale-sensitive dimensions) and complexity
measures (such as covering numbers, Rademacher averages) govern learnability
and rates of convergence. Further, it is known that learnability is closely
related to the uniform Law of Large Numbers for function classes.
- In contrast to the i.i.d. case, in the online learning framework the
learner is faced with a sequence of data appearing at discrete time intervals,
where the data is chosen by the adversary. Unlike statistical learning, where
the focus has been on complexity measures, the online learning research has
been predominantly algorithm-based. That is, an algorithm with a non-trivial
guarantee provides a certificate of learnability.
- We develop tools for analyzing learnability in the game-theoretic setting
of online learning without necessarily providing a computationally feasible
algorithm. We define complexity measures which capture the difficulty of
learning in a sequential manner. Among these measures are analogues of
Rademacher complexity, covering numbers and fat shattering dimension from
statistical learning theory. These can be seen as temporal generalizations of
classical results. The complexities we define also ensure uniform convergence
for non-i.i.d. data, extending the Glivenko-Cantelli type results. A further
generalization beyond external regret covers a vast array of known frameworks,
such as internal and Phi-regret, Blackwell's Approachability, calibration of
forecasters, global non-additive notions of cumulative loss, and more.
- This is joint work with Karthik Sridharan and Ambuj Tewari.
- Time and place: 4--5 pm on Monday, 11 October 2010, in Doherty Hall A310
As always, the seminar is free and open to the public.
(I know I got the Augustinian vs. Manichean learning bit from Norbert
Wiener, but I cannot now find the passage.)
Enigmas of Chance
Posted at October 05, 2010 17:35 | permanent link