Learning Theory: 20th Annual Conference on Learning Theory, COLT 2007, San Diego, CA, USA, June 13-15, 2007, Proceedings (Lecture Notes in Computer Science, 4539)

This book constitutes the refereed proceedings of the 20th Annual Conference on Learning Theory, COLT 2007, held in San Diego, CA, USA in June 2007. The 41 revised full papers presented together with 5 articles on open problems and 2 invited lectures were carefully reviewed and selected from a total of 92 submissions. The papers cover a wide range of topics and are organized in topical sections on unsupervised, semisupervised and active learning, statistical learning theory, inductive inference, regularized learning, kernel methods, SVM, online and reinforcement learning, learning algorithms and limitations on learning, dimensionality reduction, other approaches, and open problems. Front Matter....Pages - Property Testing: A Learning Theory Perspective....Pages 1-2 Spectral Algorithms for Learning and Clustering....Pages 3-4 Minimax Bounds for Active Learning....Pages 5-19 Stability of k -Means Clustering....Pages 20-34 Margin Based Active Learning....Pages 35-50 Learning Large-Alphabet and Analog Circuits with Value Injection Queries....Pages 51-65 Teaching Dimension and the Complexity of Active Learning....Pages 66-81 Multi-view Regression Via Canonical Correlation Analysis....Pages 82-96 Aggregation by Exponential Weighting and Sharp Oracle Inequalities....Pages 97-111 Occam’s Hammer....Pages 112-126 Resampling-Based Confidence Regions and Multiple Tests for a Correlated Random Vector....Pages 127-141 Suboptimality of Penalized Empirical Risk Minimization in Classification....Pages 142-156 Transductive Rademacher Complexity and Its Applications....Pages 157-171 U-Shaped, Iterative, and Iterative-with-Counter Learning....Pages 172-186 Mind Change Optimal Learning of Bayes Net Structure....Pages 187-202 Learning Correction Grammars ....Pages 203-217 Mitotic Classes....Pages 218-232 Regret to the Best vs. Regret to the Average....Pages 233-247 Strategies for Prediction Under Imperfect Monitoring....Pages 248-262 Bounded Parameter Markov Decision Processes with Average Reward Criterion....Pages 263-277 On-Line Estimation with the Multivariate Gaussian Distribution....Pages 278-292 Generalised Entropy and Asymptotic Complexities of Languages....Pages 293-307 Q -Learning with Linear Function Approximation....Pages 308-322 How Good Is a Kernel When Used as a Similarity Measure?....Pages 323-335 Gaps in Support Vector Optimization....Pages 336-348 Learning Languages with Rational Kernels....Pages 349-364 Generalized SMO-Style Decomposition Algorithms....Pages 365-377 Learning Nested Halfspaces and Uphill Decision Trees....Pages 378-392 An Efficient Re-scaled Perceptron Algorithm for Conic Systems....Pages 393-408 A Lower Bound for Agnostically Learning Disjunctions....Pages 409-423 Sketching Information Divergences....Pages 424-438 Competing with Stationary Prediction Strategies....Pages 439-453 Improved Rates for the Stochastic Continuum-Armed Bandit Problem....Pages 454-468 Learning Permutations with Exponential Weights....Pages 469-483 Multitask Learning with Expert Advice....Pages 484-498 Online Learning with Prior Knowledge....Pages 499-513 Nonlinear Estimators and Tail Bounds for Dimension Reduction in l 1 Using Cauchy Random Projections....Pages 514-529 Sparse Density Estimation with l 1 Penalties....Pages 530-543 l 1 Regularization in Infinite Dimensional Feature Spaces....Pages 544-558 Prediction by Categorical Features: Generalization Properties and Application to Feature Ranking....Pages 559-573 Observational Learning in Random Networks....Pages 574-588 The Loss Rank Principle for Model Selection....Pages 589-603 Robust Reductions from Ranking to Classification....Pages 604-619 Rademacher Margin Complexity....Pages 620-621 Open Problems in Efficient Semi-supervised PAC Learning....Pages 622-624 Resource-Bounded Information Gathering for Correlation Clustering....Pages 625-627 Are There Local Maxima in the Infinite-Sample Likelihood of Gaussian Mixture Estimation?....Pages 628-629 When Is There a Free Matrix Lunch?....Pages 630-632 Back Matter....Pages -

This book constitutes the refereed proceedings of the 20th Annual Conference on Learning Theory, COLT 2007, held in San Diego, CA, USA in June 2007. It covers unsupervised, semisupervised and active learning, statistical learning theory, inductive inference, regularized learning, kernel methods, SVM, online and reinforcement learning, learning algorithms and limitations on learning, dimensionality reduction, as well as open problems.