Learning Theory 20th Annual Conference on Learning Theory, COLT 2007, San Diego, CA, USA, June 13-15, 2007, Proceedings

This volumecontains paperspresentedatthe 20thAnnualConferenceonLea- ing Theory (previously known as the Conference on Computational Learning Theory) held in San Diego, USA, June 13-15, 2007, as part of the 2007 Fed- ated Computing Research Conference (FCRC). The Technical Program contained 41 papers selected from 92 submissions, 5 open problems selected from among 7 contributed, and 2 invited lectures. The invited lectures were givenby Dana Ron on “PropertyTesting: A Learning T- oryPerspective,”andbySantoshVempalaon“SpectralAlgorithmsforLearning and Clustering.” The abstracts of these lectures are 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 Samuel E. Moelius III for the paper “U-Shaped, Iterative, and Iterative-with-Counter Learning” co-authored with John Case. This year, student awards were also granted by the Machine LearningJournal.Wehavethereforebeenabletoselecttwomorestudentpapers forprizes.Thestudents selectedwereLev Reyzinforthe paper“LearningLarge- Alphabet and Analog Circuits with Value Injection Queries” (co-authored with Dana Angluin, James Aspnes, and Jiang Chen), and Jennifer Wortman for the paper “Regret to the Best vs. Regret to the Average” (co-authored with Eyal Even-Dar, Michael Kearns, and Yishay Mansour). The selected papers cover a wide range of topics, including unsupervised, semisupervisedand activelearning,statistical learningtheory, regularizedlea- ing, kernel methods and SVM, inductive inference, learning algorithms and l- itations on learning, on-line and reinforcement learning. The last topic is part- ularly well represented, covering alone more than one-fourth of the total.