Learning Theory: 18th Annual Conference on Learning Theory, COLT 2005, Bertinoro, Italy, June 27-30, 2005. Proceedings

Stéphan Clémençon, Gábor Lugosi, Nicolas Vayatis (auth.), Peter Auer, Ron Meir (eds.)3540265562, 9783540265566

This volume contains papers presented at the Eighteenth Annual Conference on Learning Theory (previously known as the Conference on Computational Learning Theory) held in Bertinoro, Italy from June 27 to 30, 2005. The technical program contained 45 papers selected from 120 submissions, 3 open problems selected from among 5 contributed, and 2 invited lectures. The invited lectures were given by Sergiu Hart on “Uncoupled Dynamics and Nash Equilibrium”, and by Satinder Singh on “Rethinking State, Action, and Reward in Reinforcement Learning”. These papers were not included in this volume. The Mark Fulk Award is presented annually for the best paper co-authored by a student. The student selected this year was Hadi Salmasian for the paper titled “The Spectral Method for General Mixture Models” co-authored with Ravindran Kannan and Santosh Vempala. The number of papers submitted to COLT this year was exceptionally high. In addition to the classical COLT topics, we found an increase in the number of submissions related to novel classi?cation scenarios such as ranking. This – crease re?ects a healthy shift towards more structured classi?cation problems, which are becoming increasingly relevant to practitioners.

---

Table of contents :
Front Matter….Pages –
Ranking and Scoring Using Empirical Risk Minimization….Pages 1-15
Learnability of Bipartite Ranking Functions….Pages 16-31
Stability and Generalization of Bipartite Ranking Algorithms….Pages 32-47
Loss Bounds for Online Category Ranking….Pages 48-62
Margin-Based Ranking Meets Boosting in the Middle….Pages 63-78
Martingale Boosting….Pages 79-94
The Value of Agreement, a New Boosting Algorithm….Pages 95-110
A PAC-Style Model for Learning from Labeled and Unlabeled Data….Pages 111-126
Generalization Error Bounds Using Unlabeled Data….Pages 127-142
On the Consistency of Multiclass Classification Methods….Pages 143-157
Sensitive Error Correcting Output Codes….Pages 158-172
Data Dependent Concentration Bounds for Sequential Prediction Algorithms….Pages 173-187
The Weak Aggregating Algorithm and Weak Mixability….Pages 188-203
Tracking the Best of Many Experts….Pages 204-216
Improved Second-Order Bounds for Prediction with Expert Advice….Pages 217-232
Competitive Collaborative Learning….Pages 233-248
Analysis of Perceptron-Based Active Learning….Pages 249-263
A New Perspective on an Old Perceptron Algorithm….Pages 264-278
Fast Rates for Support Vector Machines….Pages 279-294
Exponential Convergence Rates in Classification….Pages 295-307
General Polynomial Time Decomposition Algorithms….Pages 308-322
Approximating a Gram Matrix for Improved Kernel-Based Learning….Pages 323-337
Learning Convex Combinations of Continuously Parameterized Basic Kernels….Pages 338-352
On the Limitations of Embedding Methods….Pages 353-365
Leaving the Span….Pages 366-381
Variations on U-Shaped Learning….Pages 382-397
Mind Change Efficient Learning….Pages 398-412
On a Syntactic Characterization of Classification with a Mind Change Bound….Pages 413-428
Ellipsoid Approximation Using Random Vectors….Pages 429-443
The Spectral Method for General Mixture Models….Pages 444-457
On Spectral Learning of Mixtures of Distributions….Pages 458-469
From Graphs to Manifolds – Weak and Strong Pointwise Consistency of Graph Laplacians….Pages 470-485
Towards a Theoretical Foundation for Laplacian-Based Manifold Methods….Pages 486-500
Permutation Tests for Classification….Pages 501-515
Localized Upper and Lower Bounds for Some Estimation Problems….Pages 516-530
Improved Minimax Bounds on the Test and Training Distortion of Empirically Designed Vector Quantizers….Pages 531-544
Rank, Trace-Norm and Max-Norm….Pages 545-560
Learning a Hidden Hypergraph….Pages 561-575
On Attribute Efficient and Non-adaptive Learning of Parities and DNF Expressions….Pages 576-590
Unlabeled Compression Schemes for Maximum Classes….Pages 591-605
Trading in Markovian Price Models….Pages 606-620
From External to Internal Regret….Pages 621-636
Separating Models of Learning from Correlated and Uncorrelated Data….Pages 637-651
Asymptotic Log-Loss of Prequential Maximum Likelihood Codes….Pages 652-667
Teaching Classes with High Teaching Dimension Using Few Examples….Pages 668-683
Optimum Follow the Leader Algorithm….Pages 684-686
The Cross Validation Problem….Pages 687-688
Compute Inclusion Depth of a Pattern….Pages 689-690
Back Matter….Pages –