Front matter
1-13
How Many Queries Are Needed to Learn One Bit of Information?
Hans Ulrich Simon
14-30
Radial Basis Function Neural Networks Have Superlinear VC Dimension
Michael Schmitt
31-47
Tracking a Small Set of Experts by Mixing Past Posteriors
Olivier Bousquet and Manfred K. Warmuth
48-64
Potential-Based Algorithms in Online Prediction and Game Theory
Nicolò Cesa-Bianchi and Gábor Lugosi
65-81
A Sequential Approximation Bound for Some Sample-Dependent Convex Optimization Problems with Applications in Learning
Tong Zhang
82-98
Efficiently Approximating Weighted Sums with Exponentially Many Terms
Deepak Chawla, Lin Li and Stephen Scott
99-115
Ultraconservative Online Algorithms for Multiclass Problems
Koby Crammer and Yoram Singer
116-127
Estimating a Boolean Perceptron from Its Average Satisfying Assignment: A Bound on the Precision Required
Paul W. Goldberg
128-142
Adaptive Strategies and Regret Minimization in Arbitrarily Varying Markov Environments
Shie Mannor and Nahum Shimkin
143-159
Robust Learning — Rich and Poor
John Case, Sanjay Jain, Frank Stephan and Rolf Wiehagen
160-176
On the Synthesis of Strategies Identifying Recursive Functions
Sandra Zilles
177-193
Intrinsic Complexity of Learning Geometrical Concepts from Positive Data
Sanjay Jain and Efim Kinber
194-207
Toward a Computational Theory of Data Acquisition and Truthing
David G. Stork
208-223
Discrete Prediction Games with Arbitrary Feedback and Loss (Extended Abstract)
Antonio Piccolboni and Christian Schindelhauer
224-240
Rademacher and Gaussian Complexities: Risk Bounds and Structural Results
Peter L. Bartlett and Shahar Mendelson
241-255
Further Explanation of the Effectiveness of Voting Methods: The Game between Margins and Weights
Vladimir Koltchinskii, Dmitriy Panchenko and Fernando Lozano
256-272
Geometric Methods in the Analysis of Glivenko-Cantelli Classes
Shahar Mendelson
273-288
Learning Relatively Small Classes
Shahar Mendelson
289-302
On Agnostic Learning with {0, *, 1}-Valued and Real-Valued Hypotheses
Philip M. Long
303-319
When Can Two Unsupervised Learners Achieve PAC Separation?
Paul W. Goldberg
320-336
Strong Entropy Concentration, Game Theory, and Algorithmic Randomness
Peter Grünwald
337-353
Pattern Recognition and Density Estimation under the General i.i.d. Assumption
Ilia Nouretdinov, Volodya Vovk, Michael Vyugin and Alex Gammerman
354-367
A General Dimension for Exact Learning
José L. Balcázar, Jorge Castro and David Guijarro
368-384
Data-Dependent Margin-Based Generalization Bounds for Classification
Balázs Kégl, Tamás Linder and Gábor Lugosi
385-401
Limitations of Learning via Embeddings in Euclidean Half-Spaces
Shai Ben-David, Nadav Eiron and Hans Ulrich Simon
402-415
Estimating the Optimal Margins of Embeddings in Euclidean Half Spaces
Jürgen Forster, Niels Schmitt and Hans Ulrich Simon
416-426
A Generalized Representer Theorem
Bernhard Schölkopf, Ralf Herbrich and Alex J. Smola
427-443
A Leave-One-out Cross Validation Bound for Kernel Methods with Applications in Learning
Tong Zhang
444-460
Learning Additive Models Online with Fast Evaluating Kernels
Mark Herbster
461-472
Geometric Bounds for Generalization in Boosting
Shie Mannor and Ron Meir
473-489
Smooth Boosting and Learning with Malicious Noise
Rocco A. Servedio
490-506
On Boosting with Optimal Poly-Bounded Distributions
Nader H. Bshouty and Dmitry Gavinsky
507-516
Agnostic Boosting
Shai Ben-David, Philip M. Long and Yishay Mansour
517-528
A Theoretical Analysis of Query Selection for Collaborative Filtering
Wee Sun Lee and Philip M. Long
529-545
On Using Extended Statistical Queries to Avoid Membership Queries
Nader H. Bshouty and Vitaly Feldman
546-557
Learning Monotone DNF from a Teacher That Almost Does Not Answer Membership Queries
Nader H. Bshouty and Nadav Eiron
558-573
On Learning Monotone DNF under Product Distributions
Rocco A. Servedio
574-588
Learning Regular Sets with an Incomplete Membership Oracle
Nader Bshouty and Avi Owshanko
589-604
Learning Rates for Q-Learning
Eyal Even-Dar and Yishay Mansour
605-615
Optimizing Average Reward Using Discounted Rewards
Sham Kakade
616-629
Bounds on Sample Size for Policy Evaluation in Markov Environments
Leonid Peshkin and Sayan Mukherjee
Back matter