Learning Theory

1. Front Matter

   PDF

2. Learning to Rank

   1. Ranking and Scoring Using Empirical Risk Minimization

      • Stéphan Clémençon, Gábor Lugosi, Nicolas Vayatis

      Pages 1-15

   2. Learnability of Bipartite Ranking Functions

      • Shivani Agarwal, Dan Roth

      Pages 16-31

   3. Stability and Generalization of Bipartite Ranking Algorithms

      • Shivani Agarwal, Partha Niyogi

      Pages 32-47

   4. Loss Bounds for Online Category Ranking

      • Koby Crammer, Yoram Singer

      Pages 48-62

3. Boosting

   1. Margin-Based Ranking Meets Boosting in the Middle

      • Cynthia Rudin, Corinna Cortes, Mehryar Mohri, Robert E. Schapire

      Pages 63-78

   2. Martingale Boosting

      • Philip M. Long, Rocco A. Servedio

      Pages 79-94

   3. The Value of Agreement, a New Boosting Algorithm

      • Boaz Leskes

      Pages 95-110

4. Unlabeled Data, Multiclass Classification

   1. A PAC-Style Model for Learning from Labeled and Unlabeled Data

      • Maria-Florina Balcan, Avrim Blum

      Pages 111-126

   2. Generalization Error Bounds Using Unlabeled Data

      • Matti Kääriäinen

      Pages 127-142

   3. On the Consistency of Multiclass Classification Methods

      • Ambuj Tewari, Peter L. Bartlett

      Pages 143-157

   4. Sensitive Error Correcting Output Codes

      • John Langford, Alina Beygelzimer

      Pages 158-172

5. Online Learning I

   1. Data Dependent Concentration Bounds for Sequential Prediction Algorithms

      • Tong Zhang

      Pages 173-187

   2. The Weak Aggregating Algorithm and Weak Mixability

      • Yuri Kalnishkan, Michael V. Vyugin

      Pages 188-203

   3. Tracking the Best of Many Experts

      • András György, Tamás Linder, Gábor Lugosi

      Pages 204-216

   4. Improved Second-Order Bounds for Prediction with Expert Advice

      • Nicolò Cesa-Bianchi, Yishay Mansour, Gilles Stoltz

      Pages 217-232

6. Online Learning II

   1. Competitive Collaborative Learning

      • Baruch Awerbuch, Robert D. Kleinberg

      Pages 233-248

   2. Analysis of Perceptron-Based Active Learning

      • Sanjoy Dasgupta, Adam Tauman Kalai, Claire Monteleoni

      Pages 249-263

   3. A New Perspective on an Old Perceptron Algorithm

      • Shai Shalev-Shwartz, Yoram Singer

      Pages 264-278

7. Support Vector Machines

   1. Fast Rates for Support Vector Machines

      • Ingo Steinwart, Clint Scovel

      Pages 279-294

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.

• Boosting
• Support Vector Machine
• classification
• game theory
• learning
• learning theory
• supervised learning
• unsupervised learning
• algorithm analysis and problem complexity

• University of Leoben, Leoben, Austria

  Peter Auer

• Department of Electrical Engineering, Technion, Haifa, Israel

  Ron Meir

Policies and ethics