Learning Theory

Table of Contents......Page 8
Towards a Characterization of Polynomial Preference Elicitation with Value Queries in Combinatorial Auctions......Page 12
Graphical Economics......Page 28
Deterministic Calibration and Nash Equilibrium......Page 44
Reinforcement Learning for Average Reward Zero-Sum Games......Page 60
Polynomial Time Prediction Strategy with Almost Optimal Mistake Probability......Page 75
Minimizing Regret with Label Efficient Prediction......Page 88
Regret Bounds for Hierarchical Classification with Linear-Threshold Functions......Page 104
Online Geometric Optimization in the Bandit Setting Against an Adaptive Adversary......Page 120
Learning Classes of Probabilistic Automata......Page 135
On the Learnability of E-pattern Languages over Small Alphabets......Page 151
Replacing Limit Learners with Equally Powerful One-Shot Query Learners......Page 166
Concentration Bounds for Unigrams Language Model......Page 181
Inferring Mixtures of Markov Chains......Page 197
PExact = Exact Learning......Page 211
Learning a Hidden Graph Using O(log n) Queries Per Edge......Page 221
Toward Attribute Efficient Learning of Decision Lists and Parities......Page 235
Learning Over Compact Metric Spaces......Page 250
A Function Representation for Learning in Banach Spaces......Page 266
Local Complexities for Empirical Risk Minimization......Page 281
Model Selection by Bootstrap Penalization for Classification......Page 296
Convergence of Discrete MDL for Sequential Prediction......Page 311
On the Convergence of MDL Density Estimation......Page 326
Suboptimal Behavior of Bayes and MDL in Classification Under Misspecification......Page 342
Learning Intersections of Halfspaces with a Margin......Page 359
A General Convergence Theorem for the Decomposition Method......Page 374
Oracle Bounds and Exact Algorithm for Dyadic Classification Trees......Page 389
An Improved VC Dimension Bound for Sparse Polynomials......Page 404
A New PAC Bound for Intersection-Closed Concept Classes......Page 419
A Framework for Statistical Clustering with a Constant Time Approximation Algorithms for K-Median Clustering......Page 426
Data Dependent Risk Bounds for Hierarchical Mixture of Experts Classifiers......Page 438
Consistency in Models for Communication Constrained Distributed Learning......Page 453
On the Convergence of Spectral Clustering on Random Samples: The Normalized Case......Page 468
Performance Guarantees for Regularized Maximum Entropy Density Estimation......Page 483
Learning Monotonic Linear Functions......Page 498
Boosting Based on a Smooth Margin......Page 513
Bayesian Networks and Inner Product Spaces......Page 529
An Inequality for Nearly Log-Concave Distributions with Applications to Learning......Page 545
Bayes and Tukey Meet at the Center Point......Page 560
Sparseness Versus Estimating Conditional Probabilities: Some Asymptotic Results......Page 575
A Statistical Mechanics Analysis of Gram Matrix Eigenvalue Spectra......Page 590
Statistical Properties of Kernel Principal Component Analysis......Page 605
Kernelizing Sorting, Permutation, and Alignment for Minimum Volume PCA......Page 620
Regularization and Semi-supervised Learning on Large Graphs......Page 635
Perceptron-Like Performance for Intersections of Halfspaces......Page 650
The Optimal PAC Algorithm......Page 652
The Budgeted Multi-armed Bandit Problem......Page 654
Author Index......Page 658