Computational Learning Theory: 14th Annual Conference on Computational Learning Theory, COLT 2001 and 5th European Conference on Computational Learning Theory, EuroCOLT 2001 Amsterdam, The Netherlands, July 16–19, 2001 Proceedings

Hans Ulrich Simon (auth.), David Helmbold, Bob Williamson (eds.)3540423435, 9783540423430

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?….Pages 1-13
Radial Basis Function Neural Networks Have Superlinear VC Dimension….Pages 14-30
Tracking a Small Set of Experts by Mixing Past Posteriors….Pages 31-47
Potential-Based Algorithms in Online Prediction and Game Theory….Pages 48-64
A Sequential Approximation Bound for Some Sample-Dependent Convex Optimization Problems with Applications in Learning….Pages 65-81
Efficiently Approximating Weighted Sums with Exponentially Many Terms….Pages 82-98
Ultraconservative Online Algorithms for Multiclass Problems….Pages 99-115
Estimating a Boolean Perceptron from Its Average Satisfying Assignment: A Bound on the Precision Required….Pages 116-127
Adaptive Strategies and Regret Minimization in Arbitrarily Varying Markov Environments….Pages 128-142
Robust Learning — Rich and Poor….Pages 143-159
On the Synthesis of Strategies Identifying Recursive Functions….Pages 160-176
Intrinsic Complexity of Learning Geometrical Concepts from Positive Data….Pages 177-193
Toward a Computational Theory of Data Acquisition and Truthing….Pages 194-207
Discrete Prediction Games with Arbitrary Feedback and Loss (Extended Abstract)….Pages 208-223
Rademacher and Gaussian Complexities: Risk Bounds and Structural Results….Pages 224-240
Further Explanation of the Effectiveness of Voting Methods: The Game between Margins and Weights….Pages 241-255
Geometric Methods in the Analysis of Glivenko-Cantelli Classes….Pages 256-272
Learning Relatively Small Classes….Pages 273-288
On Agnostic Learning with {0, *, 1}-Valued and Real-Valued Hypotheses….Pages 289-302
When Can Two Unsupervised Learners Achieve PAC Separation?….Pages 303-319
Strong Entropy Concentration, Game Theory, and Algorithmic Randomness….Pages 320-336
Pattern Recognition and Density Estimation under the General i.i.d. Assumption….Pages 337-353
A General Dimension for Exact Learning….Pages 354-367
Data-Dependent Margin-Based Generalization Bounds for Classification….Pages 368-384
Limitations of Learning via Embeddings in Euclidean Half-Spaces….Pages 385-401
Estimating the Optimal Margins of Embeddings in Euclidean Half Spaces….Pages 402-415
A Generalized Representer Theorem….Pages 416-426
A Leave-One-out Cross Validation Bound for Kernel Methods with Applications in Learning….Pages 427-443
Learning Additive Models Online with Fast Evaluating Kernels….Pages 444-460
Geometric Bounds for Generalization in Boosting….Pages 461-472
Smooth Boosting and Learning with Malicious Noise….Pages 473-489
On Boosting with Optimal Poly-Bounded Distributions….Pages 490-506
Agnostic Boosting….Pages 507-516
A Theoretical Analysis of Query Selection for Collaborative Filtering….Pages 517-528
On Using Extended Statistical Queries to Avoid Membership Queries….Pages 529-545
Learning Monotone DNF from a Teacher That Almost Does Not Answer Membership Queries….Pages 546-557
On Learning Monotone DNF under Product Distributions….Pages 558-573
Learning Regular Sets with an Incomplete Membership Oracle….Pages 574-588
Learning Rates for Q-Learning….Pages 589-604
Optimizing Average Reward Using Discounted Rewards….Pages 605-615
Bounds on Sample Size for Policy Evaluation in Markov Environments….Pages 616-629