(Ab)Use of Bounds

NIPS 2004, Whistler, BC, Canada, December 18

Organizers: Shai Ben-David, John Langford, John Shawe-Taylor, and Bob Williamson

It's been over 30 years since the foundations of sample complexity based learning theory and now seems a good time to assess the program. Has this branch of learning theory been useful?

The purpose of this workshop is not merely progress assessment. The sample complexity bounds community has internal disagreements about what is (and is not) a useful bound, what is (and is not) a tight bound, how (and where) bounds might reasonably be used, and which bounds-related questions should be answered. One goal of this workshop is to debate the merits of these different issues in order to foster better understanding internally as well as externally.

It is not the purpose of the workshop to converge to the one right way to assess sample complexity or learning performance etc; rather we seek to understand the relative merits of diverse approaches and how they relate, recognising that it is very unlikely there is one true and best solution.

The workshop is generally focused on answers to the above questions. Some specific topics include:

  1. Quantitatively tight bounds. (What are they, how are they useful, etc...)
  2. Position statements and arguments about what bounds should deliver.
  3. Bounds for clustering and other "non-standard" learning problems
  4. The relationship between bounds and algorithms
  5. When are bounds useless?
  6. Issues in bound use (computational and informational complexities)
  7. What quantities should bounds depend on? (a priori knowledge of the task? Unlabeled training data? All training data?)

Morning Session: (Ab)Use of older bounds

7:30Introduction & OpeningJohn Langford and Bob Williamson
8:20 Using Unlabeled Data in Generalization Error BoundsMatti Kaariainen
8:55Learning the prior for the PAC-Bayes boundAmiran Ambroladze, Emilio Parrado-Hernandez, and John Shawe-Taylor
9:25Improved Risk-Tail Bounds for On-line AlgorithmsNicolo Cesa-Bianchi and Claudio GentilePaper
9:55Closing Debate

Afternoon Session: New (Ab)Uses of bounds

4:00Generalization Bounds for ClusteringShai Ben-Davidpresentation
4:10Generalization Bounds for Clustering - Discussion
4:40 An Objective Evaluation Criterion for ClusteringArindam Banerjee and John Langford
5:15A Sample-Complexity Analysis of Learning from Labeled and Unlabeled DataMaria Balcan and Avrim Blum
5:40Error Bounds for Correlation ClusteringThorsten Joachims and John Hopcroft
6:05Bounds which exploit a-priori knowledgePetra Philips
6:30closing debate