Learning Theory: 17th Annual Conference on Learning Theory, COLT 2004, Banff, Canada, July 1-4, 2004, Proceedings

Front Cover
Springer Science & Business Media, Jun 17, 2004 - Computers - 645 pages
This 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 Classification 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
Classification
285
Convergence of Discrete MDL for Sequential Prediction
300
On the Convergence of MDL Density Estimation
315
Suboptimal Behavior of Bayes and MDL in Classification Under Misspecification
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
Author Index
646
Copyright

Other editions - View all

Common terms and phrases