COLT 2000

The 13th Annual Conference on Computational Learning Theory (COLT 2000) took place June 28-July 1, 2000 in Palo Alto, California.

Archive of conference website

Session 1

• On the Convergence Rate of Good-Turing Estimators
  David McAllester and Robert E. Schapire
• On the Efficiency of Noise-Tolerant PAC Algorithms Derived from Statistical Queries
  Jeffrey Jackson
• Decision Tree Approximations of Boolean Functions
  Dinesh Mehta and Vijay Raghavan
• Computable Shell Decomposition Bounds
  John Langford and David McAllester

Session 2

• Continuous Drifting Games
  Yoav Freund and Manfred Opper
• Language Learning From Texts: Degrees of Instrinsic Complexity and Their Characterizations
  Sanjay Jain, Efim Kinber and Rolf Wiehagen
• Average-Case Complexity of Learning Polynomials
  Frank Stephan and Thomas Zeugmann

Session 3

• Generalization Bounds for Decision Trees
  Yishay Mansour and David McAllester
• The Role of Critical Sets in Vapnik-Chervonenkis Theory
  Nicolas Vayatis
• Statistical Sufficiency for Classes in Empirical L_2 Spaces
  Shahar Mendelson and Naftali Tishby

Session 4

• Relative Expected Instantaneous Loss Bounds
  Juergen Forster and Manfred Warmuth
• The Minimax Strategy for Gaussian Density Estimation
  Eiji Takimoto and Manfred Warmuth
• Adaptive and Self-Confident On-Line Learning Algorithms
  Peter Auer and Claudio Gentile
• An Improved On-line Algorithm for Learning Linear Evaluation Functions
  Peter Auer

Session 5

• On the Learnability and Design of Output Codes for Multiclass Problems
  Koby Crammer and Yoram Singer
• Estimation and Approximation Bounds for Gradient-Based Reinforcement Learning
  Peter L. Bartlett and Jonathan Baxter
• Bias-Variance Error Bounds for Temporal Difference Updates
  Michael Kearns and Satinder Singh

Session 6

• PAC Analogues of Perceptron and Winnow via Boosting the Margin
  Rocco A. Servedio
• Logistic Regression, AdaBoost and Bregman Distances
  Michael Collins, Robert E. Schapire and Yoram Singer
• Barrier Boosting
  G. Raetsch, M. Warmuth, S. Mika, T. Onoda, S. Lemm, and K.-R. Mueller
• MadaBoost: A Modification of AdaBoost
  Carlos Domingo and Osamu Watanabe

Session 7

• Localized Boosting
  Ron Meir and Ran El-Yaniv and Shai Ben-David
• Improving Algorithms for Boosting
  Javed A. Aslam
• Leveraging for Regression
  Nigel Duffy and David Helmbold
• Boosting Using Branching Programs
  Yishay Mansour and David McAllester

Session 8

• The Precision of Query Points as a Resource for Learning Convex Polytopes with Membership Queries
  Paul Goldberg and Stephen Kwek
• Improved Algorithms for Theory Revision with Queries
  Judy Goldsmith, Robert H. Sloan, Balazs Szorenyi, and Gyorgy Turan
• Abstract Combinatorial Characterizations of Exact Learning via Queries
  Jose Luis Balcazar, Jorge Castro, and David Guijarro

Session 9

• The Complexity of Densest Region Detection
  Shai Ben-David, Nadav Eiron, and Hans Simon
• On the Difficulty of Approximately Maximizing Agreements
  Shai Ben-David, Nadav Eiron, and Philip M. Long
• Hardness Results for General Two-Layer Neural Networks
  Christian Kuhlmann

Session 10

• Model Selection and Error Estimation
  Peter L. Bartlett, Stephane Boucheron, and Gabor Lugosi
• Generalisation Error Bounds for Sparse Linear Classifiers
  Thore Graepel, Ralf Herbrich, and John Shawe-Taylor
• Sparsity vs. Large Margins for Linear Classifiers
  Ralf Herbrich, Thore Graepel, and John Shawe-Taylor
• Entropy Numbers of Linear Function Classes
  Robert C. Williamson, Alex J. Smola, and Bernhard Scholkopf