Learning Theory: 20th Annual Conference on Learning Theory, COLT 2007, San Diego, CA, USA; June 13-15, 2007. Proceedings

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 ℓ 1 Penalties....Pages 530-543
ℓ 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 -