Computational Learning Theory: 15th Annual Conference on Computational Learning Theory, COLT 2002 Sydney, Australia, July 8–10, 2002 Proceedings

Shahar Mendelson, Robert C. Williamson (auth.), Jyrki Kivinen, Robert H. Sloan (eds.)354043836X, 9783540438366

This book constitutes the refereed proceedings of the 15th Annual Conference on Computational Learning Theory, COLT 2002, held in Sydney, Australia, in July 2002.
The 26 revised full papers presented were carefully reviewed and selected from 55 submissions. The papers are organized in topical sections on statistical learning theory, online learning, inductive inference, PAC learning, boosting, and other learning paradigms.

---

Table of contents :
Agnostic Learning Nonconvex Function Classes….Pages 1-13
Entropy, Combinatorial Dimensions and Random Averages….Pages 14-28
Geometric Parameters of Kernel Machines….Pages 29-43
Localized Rademacher Complexities….Pages 44-58
Some Local Measures of Complexity of Convex Hulls and Generalization Bounds….Pages 59-73
Path Kernels and Multiplicative Updates….Pages 74-89
Predictive Complexity and Information….Pages 90-105
Mixability and the Existence of Weak Complexities….Pages 105-120
A Second-Order Perceptron Algorithm….Pages 121-137
Tracking Linear-Threshold Concepts with Winnow….Pages 138-153
Learning Tree Languages from Text….Pages 153-168
Polynomial Time Inductive Inference of Ordered Tree Patterns with Internal Structured Variables from Positive Data….Pages 169-184
Inferring Deterministic Linear Languages….Pages 185-200
Merging Uniform Inductive Learners….Pages 201-216
The Speed Prior: A New Simplicity Measure Yielding Near-Optimal Computable Predictions….Pages 216-228
New Lower Bounds for Statistical Query Learning….Pages 229-243
Exploring Learnability between Exact and PAC….Pages 244-254
PAC Bounds for Multi-armed Bandit and Markov Decision Processes….Pages 255-270
Bounds for the Minimum Disagreement Problem with Applications to Learning Theory….Pages 271-286
On the Proper Learning of Axis Parallel Concepts….Pages 287-302
A Consistent Strategy for Boosting Algorithms….Pages 303-319
The Consistency of Greedy Algorithms for Classification….Pages 319-333
Maximizing the Margin with Boosting….Pages 334-350
Performance Guarantees for Hierarchical Clustering….Pages 351-363
Self-Optimizing and Pareto-Optimal Policies in General Environments Based on Bayes-Mixtures….Pages 364-379
Prediction and Dimension….Pages 380-395
Learning the Internet….Pages 396-396