## Learning Theory: 17th Annual Conference on Learning Theory, COLT 2004, Banff, Canada, July 1-4, 2004, ProceedingsThis volume contains papers presented at the 17th Annual Conference on Le- ning Theory (previously known as the Conference on Computational Learning Theory) held in Ban?, Canada from July 1 to 4, 2004. The technical program contained 43 papers selected from 107 submissions, 3 open problems selected from among 6 contributed, and 3 invited lectures. The invited lectures were given by Michael Kearns on 'Game Theory, Automated Trading and Social Networks', Moses Charikar on 'Algorithmic Aspects of - nite Metric Spaces', and Stephen Boyd on 'Convex Optimization, Semide?nite Programming, and Recent Applications'. These papers were not included in this volume. The Mark Fulk Award is presented annually for the best paper co-authored by a student. Thisyear theMark Fulk award wassupplemented with two further awards funded by the Machine Learning Journal and the National Information Communication Technology Centre, Australia (NICTA). We were therefore able toselectthreestudentpapersforprizes.ThestudentsselectedwereMagalieF- montforthesingle-authorpaper“ModelSelectionbyBootstrapPenalizationfor Classi?cation”, Daniel Reidenbach for the single-author paper “On the Lear- bility of E-Pattern Languages over Small Alphabets”, and Ran Gilad-Bachrach for the paper “Bayes and Tukey Meet at the Center Point” (co-authored with Amir Navot and Naftali Tishby). |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

Extended Abstract | 1 |

Graphical Economics | 17 |

Deterministic Calibration and Nash Equilibrium | 33 |

Reinforcement Learning for Average Reward ZeroSum Games | 49 |

Polynomial Time Prediction Strategy with Almost Optimal Mistake Probability | 64 |

Minimizing Regret with Label Efficient Prediction | 77 |

Regret Bounds for Hierarchical Classification with LinearThreshold Functions | 93 |

Online Geometric Optimization in the Bandit Setting Against an Adaptive Adversary | 109 |

A General Convergence Theorem for the Decomposition Method | 363 |

Oracle Bounds and Exact Algorithm for Dyadic Classiﬁcation Trees | 378 |

An Improved VC Dimension Bound for Sparse Polynomials | 393 |

A New PAC Bound for IntersectionClosed Concept Classes | 408 |

A Framework for Statistical Clustering with a Constant Time Approximation Algorithms for KMedian Clustering | 415 |

Data Dependent Risk Bounds for Hierarchical Mixture of Experts Classifiers | 427 |

Consistency in Models for Communication Constrained Distributed Learning | 442 |

The Normalized Case | 457 |

Learning Classes of Probabilistic Automata | 124 |

On the Learnability of Epattern Languages over Small Alphabets | 140 |

Replacing Limit Learners with Equally Powerful OneShot Query Learners | 155 |

Concentration Bounds for Unigrams Language Model | 170 |

Inferring Mixtures of Markov Chains | 186 |

PExact Exact Learning | 200 |

Learning a Hidden Graph Using Olog n Queries Per Edge | 210 |

Toward Attribute Efficient Learning of Decision Lists and Parities | 224 |

Learning Over Compact Metric Spaces | 239 |

A Function Representation for Learning in Banach Spaces | 255 |

Local Complexities for Empirical Risk Minimization | 270 |

Classiﬁcation | 285 |

Convergence of Discrete MDL for Sequential Prediction | 300 |

On the Convergence of MDL Density Estimation | 315 |

Suboptimal Behavior of Bayes and MDL in Classiﬁcation Under Misspeciﬁcation | 331 |

Learning Intersections of Halfspaces with a Margin | 348 |

Performance Guarantees for Regularized Maximum Entropy Density Estimation | 472 |

Learning Monotonic Linear Functions | 487 |

Boosting Based on a Smooth Margin | 502 |

Bayesian Networks and Inner Product Spaces | 518 |

An Inequality for Nearly LogConcave Distributions with Applications to Learning | 534 |

Bayes and Tukey Meet at the Center Point | 549 |

Some Asymptotic Results | 564 |

A Statistical Mechanics Analysis of Gram Matrix Eigenvalue Spectra | 579 |

Statistical Properties of Kernel Principal Component Analysis | 594 |

Kernelizing Sorting Permutation and Alignment for Minimum Volume PCA | 609 |

Regularization and Semisupervised Learning on Large Graphs | 624 |

The Optimal PAC Algorithm | 641 |

The Budgeted Multiarmed Bandit Problem | 643 |

646 | |

### Other editions - View all

Learning Theory: 17th Annual Conference on Learning Theory, COLT 2004, Banff ... John Shawe-Taylor,Yoram Singer No preview available - 2004 |

### Common terms and phrases

AdaBoost analysis approximation assume assumption asymptotically Bayes Bayesian network classifier clustering complexity Computer concept class consider constant convergence convex Corollary corresponding decision lists deﬁned deﬁnition denote eigenvalues elicitation empirical equilibrium error estimate examples exists finite ﬁrst forecaster function f given graph halfspaces Hilbert space hypothesis implies inequality input iteration kernel kernel PCA label learnable learner learning algorithm Lemma LimTxt linear Lipschitz loss function lower bound Machine Learning margin Markov chains matrix measure minimizing Nash equilibrium Neural node Note obtain optimal output parameters polynomial polynomial threshold function prediction probability at least probability distribution problem prove Q-learning queries random variables sample satisﬁes sequence Shawe-Taylor solution spectral clustering statistical support vector support vector machines uniformly upper bound valuation VC dimension weight