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

(I know I got the Augustinian vs. Manichean learning bit from Norbert Wiener, but I cannot now find the passage.)

Posted at October 05, 2010 17:35 | permanent link