October 05, 2010

"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

Three-Toed Sloth