21. COLT 2008: Helsinki, Finland

Rocco A. Servedio, Tong Zhang (Eds.): 21st Annual Conference on Learning Theory - COLT 2008, Helsinki, Finland, July 9-12, 2008. Omnipress 2008 BibTeX

Invited Presentations

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

Unsupervised, Semi-Supervised and Active Learning

Kamalika Chaudhuri, Satish Rao:
Learning Mixtures of Product Distributions Using Correlations and Independence. 9-20
Electronic Edition (link) BibTeX
Kamalika Chaudhuri, Satish Rao:
Beyond Gaussians: Spectral Methods for Learning Mixtures of Heavy-Tailed Distributions. 21-32
Electronic Edition (link) BibTeX
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
Electronic Edition (link) BibTeX
Maria-Florina Balcan, Steve Hanneke, Jennifer Wortman:
The True Sample Complexity of Active Learning. 45-56
Electronic Edition (link) BibTeX

On-Line Learning

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

Other Directions

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

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
Electronic Edition (link) BibTeX
Sandra Zilles, Steffen Lange, Robert Holte, Martin Zinkevich:
Teaching Dimensions based on Cooperative Learning. 135-146
Electronic Edition (link) BibTeX
Vitaly Feldman:
On the Power of Membership Queries in Agnostic Learning. 147-156
Electronic Edition (link) BibTeX

Complexity and Boolean Functions

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

Generalization and Statistics

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

Other Directions

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

Bandits and Reinforcement Learning

Andrey Bernstein, Nahum Shimkin:
Adaptive Aggregation for Reinforcement Learning with Efficient Exploration: Deterministic Domains. 323-334
Electronic Edition (link) BibTeX
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
Electronic Edition (link) BibTeX
Aleksandrs Slivkins, Eli Upfal:
Adapting to a Changing Environment: the Brownian Restless Bandits. 343-354
Electronic Edition (link) BibTeX
Varsha Dani, Thomas P. Hayes, Sham M. Kakade:
Stochastic Linear Optimization under Bandit Feedback. 355-366
Electronic Edition (link) BibTeX

Unsupervised and Semi-Supervised Learning

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

Online Learning

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

Generalization and Statistics

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

Open Problems

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