Computational Learning Theory: 14th Annual Conference on Computational Learning Theory, COLT 2001 and 5th European Conference on Computational Learning Theory, EuroCOLT 2001, Amst(2111 Lecture Notes in Computer Science)

This book constitutes the refereed proceedings of the 14th Annual and 5th European Conferences on Computational Learning Theory, COLT/EuroCOLT 2001, held in Amsterdam, The Netherlands, in July 2001. The 40 revised full papers presented together with one invited paper were carefully reviewed and selected from a total of 69 submissions. All current aspects of computational learning and its applications in a variety of fields are addressed.

Table of Contents:
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.