COLT 2008

The 21st Annual Conference on Learning Theory (COLT 2008) took place on 9-12 July 2008 in Helsinki, Finland.

Conference website

Full proceedings

Invited Talks

• Peter Grünwald. The Catch-Up Phenomenon in Bayesian Inference
• Robin Hanson. Combinatorial Prediction Markets
• Gábor Lugosi. Concentration inequalities
• Dan Klein. Unsupervised Learning for Natural Language Processing

Unsupervised, Semi-Supervised and Active Learning

• Kamalika Chaudhuri and Satish Rao. Learning Mixtures of Product Distributions Using Correlations and Independence
• Kamalika Chaudhuri and Satish Rao. Beyond Gaussians: Spectral Methods for Learning Mixtures of Heavy-Tailed Distributions
• Shai Ben-David, Tyler Lu and Dávid Pál. Does Unlabeled Data Provably Help? Worst-case Analysis of the Sample Complexity of Semi-Supervised Learning
• Maria-Florina Balcan, Steve Hanneke and Jennifer Wortman. The True Sample Complexity of Active Learning (best student paper)

Online Learning (I)

• Elad Hazan and Satyen Kale. Extracting Certainty from Uncertainty: Regret Bounded by Variation in Costs
• Kosuke Ishibashi, Kohei Hatano and Masayuki Takeda. Online Learning of Maximum p-Norm Margin Classifiers with Bias
• Subhash Khot and Ashok Kumar Ponnuswami. Minimizing Wide Range Regret with Time Selection Functions

Other Directions (I)

• Nir Ailon and Mehryar Mohri. An Efficient Reduction of Ranking to Classification
• Michael Kearns and Jennifer Wortman. Learning from Collective Behavior
• Bharath Sriperumbudur, Arthur Gretton, Kenji Fukumizu, Gert Lanckriet and Bernhard Schölkopf. Injective Hilbert Space Embeddings of Probability Measures

Complexity and Boolean Functions (I)

• Sung-Soon Choi, Kyomin Jung and Jeong Han Kim. Almost Tight Upper Bound for Finding Fourier Coefficients of Bounded Pseudo-Boolean Functions
• Sandra Zilles, Steffen Lange, Robert Holte and Martin Zinkevich. Teaching Dimensions Based on Cooperative Learning
• Vitaly Feldman. On the Power of Membership Queries in Agnostic Learning

Complexity and Boolean Functions (II)

• Thorsten Doliwa, Michael Kallweit and Hans Ulrich Simon. Dimension and Margin Bounds for Reflection-invariant Kernels
• Dana Angluin, James Aspnes, Jiang Chen, David Eisenstat and Lev Reyzin. Learning Acyclic Probabilistic Circuits Using Test Paths
• Linda Sellie. Learning Random Monotone DNF Under the Uniform Distribution
• Eric Blais, Ryan O'Donnell and Karl Wimmer. Polynomial Regression under Arbitrary Product Distributions

Generalization and Statistics (I)

• Alon Zakai and Ya'acov Ritov. How Local Should a Learning Method Be?
• Yiming Ying and Colin Campbell. Learning Coordinate Gradients with Multi-Task Kernels
• Vladimir Koltchinskii and Ming Yuan. Sparse Recovery in Large Ensembles of Kernel Machines

Online Learning and Bandits

• Amy Greenwald, Zheng Li and Warren Schudy. More Efficient Internal-Regret-Minimizing Algorithms
• Giovanni Cavallanti, Nicolò Cesa-Bianchi and Claudio Gentile. Linear Algorithms for Online Multitask Classification
• Jacob Abernethy, Elad Hazan and Alexander Rakhlin. Competing in the Dark: An Efficient Algorithm for Bandit Linear Optimization (best student paper)

Other Directions (II)

• Wouter Koolen and Steven de Rooij. Combining Expert Advice Efficiently
• Maria-Florina Balcan, Avrim Blum and Nathan Srebo. Improved Guarantees for Learning via Similarity Functions
• Benjamin I. P. Rubinstein and J. Hyam Rubinstein. Geometric & Topological Representations of Maximum Classes with Applications to Sample Compression
• Shai Shalev-Shwartz and Yoram Singer. On the Equivalence of Weak Learnability and Linear Separability: New Relaxations and Efficient Boosting Algorithms

Bandits and Reinforcement Learning

• Andrey Bernstein and Nahum Shimkin. Adaptive Aggregation for Reinforcement Learning with Efficient Exploration: Deterministic Domains
• Peter Bartlett, Varsha Dani, Thomas Hayes, Sham Kakade, Alexander Rakhlin and Ambuj Tewari. High-Probability Regret Bounds for Bandit Online Linear Optimization
• Aleksandrs Slivkins and Eli Upfal. Adapting to a Changing Environment: the Brownian Restless Bandits
• Varsha Dani, Thomas Hayes and Sham Kakade. Stochastic Linear Optimization under Bandit Feedback

Unsupervised and Semi-Supervised Learning

• Ohad Shamir and Naftali Tishby. Model Selection and Stability in k-means Clustering
• Shai Ben-David and Ulrike von Luxburg. Relating Clustering Stability to Properties of Cluster Boundaries
• Kamalika Chaudhuri and Andrew McGregor. Finding Metric Structure in Information Theoretic Clustering
• Karthik Sridharan and Sham Kakade. An Information Theoretic Framework for Multi-view Learning

Online Learning (II)

• Jacob Abernethy, Peter Bartlett, Alexander Rakhlin and Ambuj Tewari. Optimal Stragies and Minimax Lower Bounds for Online Convex Games
• Robert Kleinberg, Alexandru Niculescu-Mizil and Yogeshwer Sharma. Regret Bounds for Sleeping Experts and Bandits (best student paper)
• Jacob Abernethy, Manfred Warmuth and Joel Yellin. Optimal Strategies for Random Walks
• András György, Gábor Lugosi and György Ottucsák. On-line Sequential Bin Packing

Generalization and Statistics (II)

• Shuheng Zhou, John Lafferty and Larry Wasserman. Time Varying Undirected Graphs
• Constantine Caramanis and Shie Mannor. Learning in the Limit with Adversarial Disturbances
• Liwei Wang, Masashi Sugiyama, Cheng Yang, Zhi-Hua Zhou and Jufu Feng. On the Margin Explanation of Boosting Algorithms
• Aarti Singh, Robert Nowack and Clayton Scott. Adaptive Hausdorff Estimation of Density Level Sets
• Satyaki Mahalanabis and Daniel Stefankovic. Density Estimation in Linear Time

Open Problems

• Vitaly Feldman and Leslie Valiant. The Learning Power of Evolution
• Parikshit Gopalan, Adam Kalai and Adam Klivans. A Query Algorithm for Agnostically Learning DNF?
• Adam Smith and Manfred Warmuth. Learning Rotations