(Ab)Use of Bounds

NIPS 2004, Whistler, BC, Canada, December 18

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

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

Afternoon Session: New (Ab)Uses of bounds