Computational Learning Theory

This volume contains papers presented at the joint 14th Annual Conference on Computational Learning Theory and 5th European Conference on Computat- nal Learning Theory, held at the Trippenhuis in Amsterdam, The Netherlands from July 16 to 19, 2001. The technical program contained 40 papers selected from 69 submissions. In addition, David Stork (Ricoh California Research Center) was invited to give an invited lecture and make a written contribution to the proceedings. The Mark Fulk Award is presented annually for the best paper co-authored by a student. This year s award was won by Olivier Bousquet for the paper Tracking a Small Set of Modes by Mixing Past Posteriors (co-authored with Manfred K. Warmuth). We gratefully thank all of the individuals and organizations responsible for the success of the conference. We are especially grateful to the program c- mittee: Dana Angluin (Yale), Peter Auer (Univ. of Technology, Graz), Nello Christianini (Royal Holloway), Claudio Gentile (Universit`a di Milano), Lisa H- lerstein (Polytechnic Univ.), Jyrki Kivinen (Univ. of Helsinki), Phil Long (- tional Univ. of Singapore), Manfred Opper (Aston Univ.), John Shawe-Taylor (Royal Holloway), Yoram Singer (Hebrew Univ.), Bob Sloan (Univ. of Illinois at Chicago), Carl Smith (Univ. of Maryland), Alex Smola (Australian National Univ.), and Frank Stephan (Univ. of Heidelberg), for their e?orts in reviewing and selecting the papers in this volume.

Includes supplementary material: sn.pub/extras

Inhalt
How Many Queries Are Needed to Learn One Bit of Information?.- Radial Basis Function Neural Networks Have Superlinear VC Dimension.- Tracking a Small Set of Experts by Mixing Past Posteriors.- Potential-Based Algorithms in Online Prediction and Game Theory.- A Sequential Approximation Bound for Some Sample-Dependent Convex Optimization Problems with Applications in Learning.- Efficiently Approximating Weighted Sums with Exponentially Many Terms.- Ultraconservative Online Algorithms for Multiclass Problems.- Estimating a Boolean Perceptron from Its Average Satisfying Assignment: A Bound on the Precision Required.- Adaptive Strategies and Regret Minimization in Arbitrarily Varying Markov Environments.- Robust Learning Rich and Poor.- On the Synthesis of Strategies Identifying Recursive Functions.- Intrinsic Complexity of Learning Geometrical Concepts from Positive Data.- Toward a Computational Theory of Data Acquisition and Truthing.- Discrete Prediction Games with Arbitrary Feedback and Loss (Extended Abstract).- Rademacher and Gaussian Complexities: Risk Bounds and Structural Results.- Further Explanation of the Effectiveness of Voting Methods: The Game between Margins and Weights.- Geometric Methods in the Analysis of Glivenko-Cantelli Classes.- Learning Relatively Small Classes.- On Agnostic Learning with {0, *, 1}-Valued and Real-Valued Hypotheses.- When Can Two Unsupervised Learners Achieve PAC Separation?.- Strong Entropy Concentration, Game Theory, and Algorithmic Randomness.- Pattern Recognition and Density Estimation under the General i.i.d. Assumption.- A General Dimension for Exact Learning.- Data-Dependent Margin-Based Generalization Bounds for Classification.- Limitations of Learning via Embeddings in Euclidean Half-Spaces.- Estimating the OptimalMargins of Embeddings in Euclidean Half Spaces.- A Generalized Representer Theorem.- A Leave-One-out Cross Validation Bound for Kernel Methods with Applications in Learning.- Learning Additive Models Online with Fast Evaluating Kernels.- Geometric Bounds for Generalization in Boosting.- Smooth Boosting and Learning with Malicious Noise.- On Boosting with Optimal Poly-Bounded Distributions.- Agnostic Boosting.- A Theoretical Analysis of Query Selection for Collaborative Filtering.- On Using Extended Statistical Queries to Avoid Membership Queries.- Learning Monotone DNF from a Teacher That Almost Does Not Answer Membership Queries.- On Learning Monotone DNF under Product Distributions.- Learning Regular Sets with an Incomplete Membership Oracle.- Learning Rates for Q-Learning.- Optimizing Average Reward Using Discounted Rewards.- Bounds on Sample Size for Policy Evaluation in Markov Environments.