20. COLT 2007: San Diego, CA, USA

Invited Presentations

• Dana Ron:
  Property Testing: A Learning Theory Perspective. 1-2
  
• Santosh Vempala:
  Spectral Algorithms for Learning and Clustering. 3-4
  

Unsupervised, Semisupervised and Active Learning I

• Rui Castro, Robert D. Nowak:
  Minimax Bounds for Active Learning. 5-19
  
• Shai Ben-David, Dávid Pál, Hans-Ulrich Simon:
  Stability of k -Means Clustering. 20-34
  
• Maria-Florina Balcan, Andrei Z. Broder, Tong Zhang:
  Margin Based Active Learning. 35-50
  

Unsupervised, Semisupervised and Active Learning II

• Dana Angluin, James Aspnes, Jiang Chen, Lev Reyzin:
  Learning Large-Alphabet and Analog Circuits with Value Injection Queries. 51-65
  
• Steve Hanneke:
  Teaching Dimension and the Complexity of Active Learning. 66-81
  
• Sham M. Kakade, Dean P. Foster:
  Multi-view Regression Via Canonical Correlation Analysis. 82-96
  

Statistical Learning Theory

• Arnak S. Dalalyan, Alexandre B. Tsybakov:
  Aggregation by Exponential Weighting and Sharp Oracle Inequalities. 97-111
  
• Gilles Blanchard, François Fleuret:
  Occam's Hammer. 112-126
  
• Sylvain Arlot, Gilles Blanchard, Étienne Roquain:
  Resampling-Based Confidence Regions and Multiple Tests for a Correlated Random Vector. 127-141
  
• Guillaume Lecué:
  Suboptimality of Penalized Empirical Risk Minimization in Classification. 142-156
  
• Ran El-Yaniv, Dmitry Pechyony:
  Transductive Rademacher Complexity and Its Applications. 157-171
  

Inductive Inference

• John Case, Samuel E. Moelius:
  U-Shaped, Iterative, and Iterative-with-Counter Learning. 172-186
  
• Oliver Schulte, Wei Luo, Russell Greiner:
  Mind Change Optimal Learning of Bayes Net Structure. 187-202
  
• Lorenzo Carlucci, John Case, Sanjay Jain:
  Learning Correction Grammars. 203-217
  
• Sanjay Jain, Frank Stephan:
  Mitotic Classes. 218-232
  

Online and Reinforcement Learning I

• Eyal Even-Dar, Michael J. Kearns, Yishay Mansour, Jennifer Wortman:
  Regret to the Best vs. Regret to the Average. 233-247
  
• Gábor Lugosi, Shie Mannor, Gilles Stoltz:
  Strategies for Prediction Under Imperfect Monitoring. 248-262
  
• Ambuj Tewari, Peter L. Bartlett:
  Bounded Parameter Markov Decision Processes with Average Reward Criterion. 263-277
  

Online and Reinforcement Learning II

• Sanjoy Dasgupta, Daniel Hsu:
  On-Line Estimation with the Multivariate Gaussian Distribution. 278-292
  
• Yuri Kalnishkan, Vladimir Vovk, Michael V. Vyugin:
  Generalised Entropy and Asymptotic Complexities of Languages. 293-307
  
• Francisco S. Melo, M. Isabel Ribeiro:
  Q -Learning with Linear Function Approximation. 308-322
  

Regularized Learning, Kernel Methods, SVM

• Nathan Srebro:
  How Good Is a Kernel When Used as a Similarity Measure? 323-335
  
• Nikolas List, Don R. Hush, Clint Scovel, Ingo Steinwart:
  Gaps in Support Vector Optimization. 336-348
  
• Corinna Cortes, Leonid Kontorovich, Mehryar Mohri:
  Learning Languages with Rational Kernels. 349-364
  
• Nikolas List:
  Generalized SMO-Style Decomposition Algorithms. 365-377
  

Learning Algorithms and Limitations on Learning

• Adam Tauman Kalai:
  Learning Nested Halfspaces and Uphill Decision Trees. 378-392
  
• Alexandre Belloni, Robert M. Freund, Santosh Vempala:
  An Efficient Re-scaled Perceptron Algorithm for Conic Systems. 393-408
  
• Adam R. Klivans, Alexander A. Sherstov:
  A Lower Bound for Agnostically Learning Disjunctions. 409-423
  
• Sudipto Guha, Piotr Indyk, Andrew McGregor:
  Sketching Information Divergences. 424-438
  

Online and Reinforcement Learning III

• Vladimir Vovk:
  Competing with Stationary Prediction Strategies. 439-453
  
• Peter Auer, Ronald Ortner, Csaba Szepesvári:
  Improved Rates for the Stochastic Continuum-Armed Bandit Problem. 454-468
  
• David P. Helmbold, Manfred K. Warmuth:
  Learning Permutations with Exponential Weights. 469-483
  

Online and Reinforcement Learning IV

• Jacob Abernethy, Peter L. Bartlett, Alexander Rakhlin:
  Multitask Learning with Expert Advice. 484-498
  
• Elad Hazan, Nimrod Megiddo:
  Online Learning with Prior Knowledge. 499-513
  

Dimensionality Reduction

• Ping Li, Trevor Hastie, Kenneth Ward Church:
  Nonlinear Estimators and Tail Bounds for Dimension Reduction in l ₁ Using Cauchy Random Projections. 514-529
  
• Florentina Bunea, Alexandre B. Tsybakov, Marten H. Wegkamp:
  Sparse Density Estimation with l₁ Penalties. 530-543
  
• Saharon Rosset, Grzegorz Swirszcz, Nathan Srebro, Ji Zhu:
  l₁ Regularization in Infinite Dimensional Feature Spaces. 544-558
  
• Sivan Sabato, Shai Shalev-Shwartz:
  Prediction by Categorical Features: Generalization Properties and Application to Feature Ranking. 559-573
  

Other Approaches

• Julian Lorenz, Martin Marciniszyn, Angelika Steger:
  Observational Learning in Random Networks. 574-588
  
• Marcus Hutter:
  The Loss Rank Principle for Model Selection. 589-603
  
• Maria-Florina Balcan, Nikhil Bansal, Alina Beygelzimer, Don Coppersmith, John Langford, Gregory B. Sorkin:
  Robust Reductions from Ranking to Classification. 604-619
  

Open Problems

• Liwei Wang, Jufu Feng:
  Rademacher Margin Complexity. 620-621
  
• Avrim Blum, Maria-Florina Balcan:
  Open Problems in Efficient Semi-supervised PAC Learning. 622-624
  
• Pallika Kanani, Andrew McCallum:
  Resource-Bounded Information Gathering for Correlation Clustering. 625-627
  
• Nathan Srebro:
  Are There Local Maxima in the Infinite-Sample Likelihood of Gaussian Mixture Estimation? 628-629
  
• Manfred K. Warmuth:
  When Is There a Free Matrix Lunch? 630-632