Computational Learning Theory

Table of Contents

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