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. Lecture Notes in Artif

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. 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. How Many Queries Are Needed To Learn One Bit Of Information? / Hans Ulrich Simon -- Radial Basis Function Neural Networks Have Superlinear Vc Dimension / Michael Schmitt -- Tracking A Small Set Of Experts By Mixing Past Posteriors / Oliver Bousquet And Manfred K. Warmuth -- Potential-based Algorithms In On-line Prediction And Game Theory / Nicolo Cesa-bianchi And Gabor Lugosi -- A Sequential Approximation Bound For Some Sample-dependent Convex Optimization Problems With Applications In Learning / Tong Zhang -- Efficiently Approximating Weighted Sums With Exponentially Many Terms / Deepak Chawla, Lin Li And Stephen Scott -- Ultraconservative Online Algorithms For Multiclass Problems / Koby Crammer And Yoram Singer -- Estimating A Boolean Perceptron From Its Average Satisfying Assignment: A Bound On The Precision Required / Paul W. Goldberg -- Adaptive Strategies And Regret Minimization In Arbitrarily Varying Markov Environments / Shie Mannor And Nahum Shimkin -- Robust Learning --^ Rich And Poor / John Case, Sanjay Jain And Frank Stephan / [et Al.] -- On The Synthesis Of Strategies Identifying Recursive Functions / Sandra Zilles -- Intrinsic Complexity Of Learning Geometrical Concepts From Positive Data / Sanjay Jain And Efim Kinber -- Toward A Computational Theory Of Data Acquisition And Truthing / David G. Stork -- Discrete Prediction Games With Arbitrary Feedback And Loss / Antonio Piccolboni And Christian Schindelhauer -- Rademacher And Gaussian Complexities: Risk Bounds And Structural Results / Peter L. Bartlett And Shahar Mendelson -- Further Explanation Of The Effectiveness Of Voting Methods: The Game Between Margins And Weights / Vladimir Koltchinskii, Dmitriy Panchenko And Fernando Lozano -- Geometric Methods In The Analysis Of Glivenko-cantelli Classes / Shahar Mendelson -- Learning Relatively Small Classes / Shahar Mendelson -- On Agnostic Learning With {0, *, 1}-valued And Real-valued Hypotheses / Philip M. Long --^ When Can Two Unsupervised Learners Achieve Pac Separation? / Paul W. Goldberg -- Strong Entropy Concentration, Game Theory And Algorithmic Randomness / Peter Grunwald -- Pattern Recognition And Density Estimation Under The General I.i.d. Assumption / Ilia Nouretdinov, Volodya Vovk And Michael Vyugin / [et Al.] -- A General Dimension For Exact Learning / Jose L. Balcazar, Jorge Castro And David Guijarro -- Data-dependent Margin-based Generalization Bounds For Classification / Balazs Kegl, Tamas Linder And Gabor Lugosi -- Limitations Of Learning Via Embeddings In Euclidean Half-spaces / Shai Ben-david, Nadav Eiron And Hans Ulrich Simon -- Estimating The Optimal Margins Of Embeddings In Euclidean Half Spaces / Jurgen Forster, Niels Schmitt And Hans Ulrich Simon -- A Generalized Representer Theorem / Bernhard Scholkopf, Ralf Herbrich And Alex J. Smola -- A Leave-one Out Cross Validation Bound For Kernel Methods With Applications In Learning / Tong Zhang --^ Learning Additive Models Online With Fast Evaluating Kernels / Mark Herbster -- Geometric Bounds For Generalization In Boosting / Shie Mannor And Ron Meir -- Smooth Boosting And Learning With Malicious Noise / Rocco A. Servedio -- On Boosting With Optimal Poly-bounded Distributions / Nader H. Bshouty And Dmitry Gavinsky -- Agnostic Boosting / Shai Ben-david, Philip M. Long And Yishay Mansour -- A Theoretical Analysis Of Query Selection For Collaborative Filtering / Wee Sun Lee And Philip M. Long -- On Using Extended Statistical Queries To Avoid Membership Queries / Nader H. Bshouty And Vitaly Feldman -- Learning Monotone Dnf From A Teacher That Almost Does Not Answer Membership Queries / Nader H. Bshouty And Nadav Eiron -- On Learning Montone Dnf Under Product Distributions / Rocco A. Servedio -- Learning Regular Sets With An Incomplete Membership Oracle / Nader Bshouty And Avi Owshanko -- Learning Rates For Q-learning / Eyal Even-dar And Yishay Mansour --^ Optimizing Average Reward Using Discounted Rewards / Sham Kakade -- Bounds On Sample Size For Policy Evaluation In Markov Environments / Leonid Peshkin And Sayan Mukherjee. David Helmbold, Bob Williamson, Eds. Includes Bibliographical References And Index. 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 This volume constitutes the refereed proceedings of the 14th Annual and 5th European Conferences on Computational Learning Theory, COLT/EuroCOLT 2001. All current aspects of computational learning and its applications in a variety of fields are addressed.