## Learning Theory and Kernel Machines: 16th Annual Conference on Computational Learning Theory and 7th Kernel Workshop, COLT/Kernel 2003, Washington, DC, USA, August 24-27, 2003, ProceedingsBernhard Schoelkopf, Manfred K. Warmuth This volume contains papers presented at the joint 16th Annual Conference on Learning Theory (COLT) and the 7th Annual Workshop on Kernel Machines, heldinWashington,DC,USA,duringAugust24–27,2003.COLT,whichrecently merged with EuroCOLT, has traditionally been a meeting place for learning theorists. We hope that COLT will bene?t from the collocation with the annual workshoponkernelmachines,formerlyheldasaNIPSpostconferenceworkshop. The technical program contained 47 papers selected from 92 submissions. All 47paperswerepresentedasposters;22ofthepaperswereadditionallypresented astalks.Therewerealsotwotargetareaswithinvitedcontributions.Incompu- tional game theory,atutorialentitled“LearningTopicsinGame-TheoreticDe- sionMaking”wasgivenbyMichaelLittman,andaninvitedpaperon“AGeneral Class of No-Regret Learning Algorithms and Game-Theoretic Equilibria” was contributed by Amy Greenwald. In natural language processing, a tutorial on “Machine Learning Methods in Natural Language Processing” was presented by Michael Collins, followed by two invited talks, “Learning from Uncertain Data” by Mehryar Mohri and “Learning and Parsing Stochastic Uni?cation- Based Grammars” by Mark Johnson. In addition to the accepted papers and invited presentations, we solicited short open problems that were reviewed and included in the proceedings. We hope that reviewed open problems might become a new tradition for COLT. Our goal was to select simple signature problems whose solutions are likely to inspire further research. For some of the problems the authors o?ered monetary rewards. Yoav Freund acted as the open problem area chair. The open problems were presented as posters at the conference. |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

A General Class of NoRegret Learning Algorithms and GameTheoretic Equilibria | 2 |

Preference Elicitation and Query Learning | 13 |

Efficient Algorithms for Online Decision Problems | 26 |

Positive Definite Rational Kernels | 41 |

Bhattacharyya and Expected Likelihood Kernels | 57 |

Maximal Margin Classification for Metric Spaces | 72 |

Maximum Margin Algorithms with Boolean Kernels | 87 |

KnowledgeBased Nonlinear Kernel Classifiers | 102 |

On Finding Large Conjunctive Clusters | 448 |

Learning Arithmetic Circuits via Partial Derivatives | 463 |

Using a Linear Fit to Determine Monotonicity Directions | 477 |

Generalization Bounds for Voting Classifiers Based on Sparsity and Clustering | 492 |

Sequence Prediction Based on Monotone Complexity | 506 |

How Many Strings Are Easy to Predict? | 522 |

Polynomial Certificates for Propositional Classes | 537 |

OnLine Learning with Imperfect Monitoring | 552 |

Fast Kernels for Inexact String Matching | 114 |

Hardness Results and Efficient Alternatives | 129 |

Kernels and Regularization on Graphs | 144 |

DataDependent Bounds for Multicategory Classification Based on Convex Losses | 159 |

Comparing Clusterings by the Variation of Information | 173 |

Multiplicative Updates for Large Margin Classifiers | 188 |

Simplified PACBayesian Margin Bounds | 203 |

Sparse Kernel Partial Least Squares Regression | 216 |

Sparse Probability Regression by Label Partitioning | 231 |

Learning with Rigorous Support Vector Machines | 243 |

Robust Regression by Boosting the Median | 258 |

Boosting with Diverse Base Classifiers | 273 |

Reducing Kernel Matrix Diagonal Dominance Using Semidefinite Programming | 288 |

Optimal Rates of Aggregation | 303 |

DistanceBased Classification with Lipschitz Functions | 314 |

Random Subclass Bounds | 329 |

PACMDL Bounds | 344 |

Universal WellCalibrated Algorithm for OnLine Classification | 358 |

Learning Probabilistic LinearThreshold Classifiers via Selective Sampling | 373 |

Learning Algorithms for Enclosing Points in Bregmanian Spheres | 388 |

Internal Regret in OnLine Portfolio Selection | 403 |

Lower Bounds on the Sample Complexity of Exploration in the Multiarmed Bandit Problem | 418 |

Smooth εInsensitive Regression by Loss Symmetrization | 433 |

Exploiting Task Relatedness for Multiple Task Learning | 567 |

Approximate Equivalence of Markov Decision Processes | 581 |

An Information Theoretic Tradeoff between Complexity and Accuracy | 595 |

Learning Random LogDepth Decision Trees under the Uniform Distribution | 610 |

Projective DNF Formulae and Their Revision | 625 |

Learning with Equivalence Constraints and the Relation to Multiclass Learning | 640 |

Machine Learning Methods in Natural Language Processing | 655 |

Learning from Uncertain Data | 656 |

Learning and Parsing Stochastic UnificationBased Grammars | 671 |

Inescapable Deficiencies in MachineLearned Programs | 684 |

Random Bits Help Insightful Normal Forms and Competency Isomorphisms | 699 |

Learning All Subfunctions of a Function | 714 |

When Is Small Beautiful? | 729 |

Learning a Function of r Relevant Variables | 731 |

A Robust Statistics Formulation | 734 |

How Fast Is kMeans? | 735 |

Universal Coding of Zipf Distributions | 736 |

An Open Problem Regarding the Convergence of Universal A Priori Probability | 738 |

Entropy Bounds for Restricted Convex Hulls | 741 |

Compressing to VC Dimension Many Points | 743 |

745 | |

### Other editions - View all

### Common terms and phrases

AdaBoost assume biclique binary boosting certiﬁcate classiﬁers cluster COLT/Kernel complexity computable Computational Learning Theory consider constant constraints convergence convex coordinate Corollary dataset decision trees define deﬁned deﬁnition denote diﬀerent distribution eﬀective eﬃcient equivalent error example exponential feature space ﬁnd ﬁnding ﬁnite ﬁrst ﬁxed function given graph hypothesis implies inequality input internal regret k-mer label learnable learning algorithm Learning Theory Lemma linear loss loss function lower bound M.K. Warmuth Eds Machine Learning metric space minimal monotone obtained optimal output pair parameter parses partition players points polynomial prediction preference elicitation problem programming Proof properties queries random variables rational kernels recursive regression regressor RSVM sample satisﬁes Sch¨olkopf and M.K. sequence solution speciﬁc strategy string subset support vector machines Theorem update upper bound VC dimension weighted transducer