Computational Learning Theory

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 On-Line 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
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 Optimal Margins of Embeddinzs in Euclidean Half Spaces
A Generalized Representer Theorem
A Leave-One-0ut 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 Almst Does Not Answer Membership Queries
On Learning Monotone DNF under Product Distributions
Learning Regular Sets with an Incomplete Membership Oracle
Learing Rates for Q-Learning
Optimizing Average Reward Using Discounted Rewards
Bounds on Sample Size for Policy Evaluation in Markow Environments
Author Index