Here are some papers from ICML 2008 that I found interesting.

- Risi Kondor and Karsten Borgwardt, The Skew Spectrum of Graphs. This paper is about a new family of functions on graphs which is invariant under node label permutation. They show that these quantities appear to yield good features for learning.
- Sanjoy Dasgupta and Daniel Hsu. Hierarchical sampling for active learning. This is the first published practical consistent active learning algorithm. The abstract is also pretty impressive.
- Lihong Li, Michael Littman, and Thomas Walsh Knows What It Knows: A Framework For Self-Aware Learning. This is an attempt to create learning algorithms that know when they err, (other work includes Vovk). It’s not yet clear to me what the right model for feature-dependent confidence intervals is.
- Novi Quadrianto, Alex Smola, TIberio Caetano, and Quoc Viet Le Estimating Labels from Label Proportions. This is an example of learning in a specialization of the offline contextual bandit setting.
- Filip Radlinski, Robert Kleinberg and Thorsten Joachims

Learning Diverse Rankings with Multi-Armed Bandits. Learning should be used to solve the diversity problem, and doing it in an online bandit-like setting is quite natural. I believe the setting can be generalized to a setting with features without too much work. - Rich Caruana, Nikos Karampatziakis, Ainur Yessenalina An Empirical Evaluation of Supervised Learning in High Dimensions. This paper doesn’t need an abstract given the title :). I hadn’t previously appreciated how well a random forest works in high dimensions.
- Sham M. Kakade, Shai Shalev-Shwartz, and Ambuj Tewari. Efficient Bandit Algorithms for Online Multiclass Prediction. A paper about an online contextual bandit setting specialized to a multiclass realizable yet otherwise adversarial setting that yields a practical algorithm.

I’d like to add that I thought the conference organization (and the colocation with COLT and UAI) are particularly well done, the best I’ve seen. The key seems to be tight integration of the colocating conference programs and hordes of local volunteers making sure everything is working. I was also happy to see a 10 years award for best paper 10 years ago.

Nice selection of papers! I hope #5 is getting decent circulation in the IR community–I would have missed it myself had you not cited it here. It is a great follow-up from the SIGIR ’06 papers it cites in the introduction.

Thanks for providing your shortlist of interesting papers!

The link for “The Skew Spectrum of Graphs” is incorrect.

Thanks, fixed.

You mention that Vovk has done work related to KWIK learning. Did you have a particular paper of his in mind?

Not a specific paper, but several here are related:

http://www.vovk.net/cp/index.html

The basic idea is that you can create learning algorithms which almost always predict a set containing the truth.

Thanks for pointing out the CP literature. I’m not familiar with it, but it seems that (almost) all of the results are developed for the IID model, instead of the adversarial online model that the KWIK framework has considered so far. I’m not sure how to remove the IID assumption.