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

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 -