Learning Theory and Kernel Machines

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 Equilibriä 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 Datä 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.