November 20, 2004

Convex Risk Exegesis

This semester, I have been going to the statistics department's reading group on learning theory, even though it meets at the unholy hour of 9 am on Thursdays. (Naturally, I learned about it from Kris.) Since the end of September, we've been reading a single paper, Peter Bartlett, Michael Jordan (no, no, the important one) and Jon McAuliffe's "Convexity, Classification and Risk Bounds" [abstract, pdf]. Moved by some perverse impulse, I volunteered to present Theorem 3 in this paper, and did so on October 9th.

This was most instructive. My explanation of what was going on in this theorem and its proof, which occupy two pages of large type, took me three days to write, ran to five densely-printed RevTeX pages, and went on for a full hour and a half. (I am told that this kind of compression ratio is typical of papers written for the Annals of Statistics.) In the (highly unlikely) that you, Dear Reader, would also like to understand that theorem, you can find my notes via the reading-group's web-page. (While there, you should really read Moulinath Banerjee's notes on covering numbers and VC dimension; these aren't involved in that theorem, but they're very important, and Mouli explains them well.)

I bring this up now because this week we had our final meeting on the paper, covering theorem 17, which is where they (at last!) get actual learning rates. We convinced ourselves that the proof was invalid, though the result may well be correct. (For want of a log, the bound was lost, etc.) This felt good, not because I like to see my betters stumble, but because I've finally become able to see what was happening in a proof like that, at least through the point where it went off the rails. I couldn't have done that a few years ago. It wasn't exactly a "your journey to the dark side is now complete" moment, but certainly it wasn't the kind of thing I was trained for by any means...

We're not sure what to read next; suggestions?

Enigmas of Chance

Posted by crshalizi at November 20, 2004 17:03 | permanent link

Three-Toed Sloth:   Hosted, but not endorsed, by the Center for the Study of Complex Systems