21. COLT 2008: Helsinki, Finland

Invited Presentations

• Peter Grunwald:
  The Catch-Up Phenomenon in Bayesian Inference. 1-2
  
• Robin Hanson:
  Combinatorial Prediction Markets. 3-4
  
• Dan Klein:
  Unsupervised Learning for Natural Language Processing. 5-6
  
• Gábor Lugosi:
  Concentration Inequalities. 7-8
  

Unsupervised, Semi-Supervised and Active Learning

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

On-Line Learning

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

Other Directions

• Nir Ailon, Mehryar Mohri:
  An Efficient Reduction of Ranking to Classification. 87-98
  
• Michael Kearns, Jennifer Wortman:
  Learning from Collective Behavior. 99-110
  
• Bharath K. Sriperumbudur, Arthur Gretton, Kenji Fukumizu, Gert R. G. Lanckriet, Bernhard Shoelkopf:
  Injective Hilbert Space Embeddings of Probability Measures. 111-122
  

Complexity and Boolean Functions

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

Complexity and Boolean Functions

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

Generalization and Statistics

• Alon Zakai, Yaacov Ritov:
  How Local Should a Learning Method Be?. 205-216
  
• Yiming Ying, Colin Campbell:
  Learning Coordinate Gradients with Multi-Task Kernels. 217-228
  
• Vladimir Koltchinskii, Ming Yuan:
  Sparse Recovery in Large Ensembles of Kernel Machines On-Line Learning and Bandits. 229-238
  
• Amy R. Greenwald, Zheng Li, Warren Schudy:
  More Efficient Internal-Regret-Minimizing Algorithms. 239-250
  
• Giovanni Cavallanti, Nicolò Cesa-Bianchi, Claudio Gentile:
  Linear Algorithms for Online Multitask Classification. 251-262
  
• Jacob Abernethy, Elad Hazan, Alexander Rakhlin:
  Competing in the Dark: An Efficient Algorithm for Bandit Linear Optimization. 263-274
  

Other Directions

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

Bandits and Reinforcement Learning

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

Unsupervised and Semi-Supervised Learning

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

Online Learning

• Jacob Abernethy, Peter L. Bartlett, Alexander Rakhlin, Ambuj Tewari:
  Optimal Stragies and Minimax Lower Bounds for Online Convex Games. 415-424
  
• Robert D. Kleinberg, Alexandru Niculescu-Mizil, Yogeshwer Sharma:
  Regret Bounds for Sleeping Experts and Bandits. 425-436
  
• Jacob Abernethy, Manfred K. Warmuth, Joel Yellin:
  When Random Play is Optimal Against an Adversary. 437-446
  
• András György, Gábor Lugosi, György Ottucsák:
  On-line Sequential Bin Packing. 447-454
  

Generalization and Statistics

• Shuheng Zhou, John D. Lafferty, Larry A. Wasserman:
  Time Varying Undirected Graphs. 455-466
  
• Constantine Caramanis, Shie Mannor:
  Learning in the Limit with Adversarial Disturbances. 467-478
  
• Liwei Wang, Masashi Sugiyama, Cheng Yang, Zhi-Hua Zhou, Jufu Feng:
  On the Margin Explanation of Boosting Algorithms. 479-490
  
• Aarti Singh, Robert Nowak, Clayton Scott:
  Adaptive Hausdorff Estimation of Density Level Sets. 491-502
  
• Satyaki Mahalanabis, Daniel Stefankovic:
  Density Estimation in Linear Time. 503-512
  

Open Problems

• Vitaly Feldman, Leslie G. Valiant:
  The Learning Power of Evolution. 513-514
  
• Parikshit Gopalan, Adam Kalai, Adam R. Klivans:
  A Query Algorithm for Agnostically Learning DNF?. 515-516
  
• Adam M. Smith, Manfred K. Warmuth:
  Learning Rotations. 517