Algorithmic Learning Theory

1. Front Matter

   PDF

2. Editors’ Introduction

   1. Editors’ Introduction

      • Nader H. Bshouty, Gilles Stoltz, Nicolas Vayatis, Thomas Zeugmann

      Pages 1-11

3. Invited Papers

   1. Declarative Modeling for Machine Learning and Data Mining

      • Luc De Raedt

      Pages 12-12

   2. Learnability beyond Uniform Convergence

      • Shai Shalev-Shwartz

      Pages 13-16

   3. Some Rates of Convergence for the Selected Lasso Estimator

      • Pascal Massart, Caroline Meynet

      Pages 17-33

   4. Recent Developments in Pattern Mining

      • Toon Calders

      Pages 34-34

   5. Exploring Sequential Data

      • Gilbert Ritschard

      Pages 35-35

4. Regular Contributions

   1. Inductive Inference

      1. Enlarging Learnable Classes

         • Sanjay Jain, Timo Kötzing, Frank Stephan

         Pages 36-50

      2. Confident and Consistent Partial Learning of Recursive Functions

         • Ziyuan Gao, Frank Stephan

         Pages 51-65

      3. Automatic Learning from Positive Data and Negative Counterexamples

         • Sanjay Jain, Efim Kinber

         Pages 66-80

      4. Regular Inference as Vertex Coloring

         • Christophe Costa Florêncio, Sicco Verwer

         Pages 81-95

   2. Teaching and PAC-Learning

      1. Sauer’s Bound for a Notion of Teaching Complexity

         • Rahim Samei, Pavel Semukhin, Boting Yang, Sandra Zilles

         Pages 96-110

      2. On the Learnability of Shuffle Ideals

         • Dana Angluin, James Aspnes, Aryeh Kontorovich

         Pages 111-123

   3. Statistical Learning Theory and Classification

      1. New Analysis and Algorithm for Learning with Drifting Distributions

         • Mehryar Mohri, Andres Muñoz Medina

         Pages 124-138

      2. On the Hardness of Domain Adaptation and the Utility of Unlabeled Target Samples

         • Shai Ben-David, Ruth Urner

         Pages 139-153

      3. Efficient Protocols for Distributed Classification and Optimization

         • Hal Daumé III, Jeff M. Phillips, Avishek Saha, Suresh Venkatasubramanian

         Pages 154-168

   4. Relations between Models and Data

      1. The Safe Bayesian

         • Peter Grünwald

         Pages 169-183

      2. Data Stability in Clustering: A Closer Look

         • Lev Reyzin

         Pages 184-198

   5. Bandit Problems

      1. Thompson Sampling: An Asymptotically Optimal Finite-Time Analysis

         • Emilie Kaufmann, Nathaniel Korda, Rémi Munos

         Pages 199-213

      2. Regret Bounds for Restless Markov Bandits

         • Ronald Ortner, Daniil Ryabko, Peter Auer, Rémi Munos

         Pages 214-228

This book constitutes the refereed proceedings of the 23rd International Conference on Algorithmic Learning Theory, ALT 2012, held in Lyon, France, in October 2012. The conference was co-located and held in parallel with the 15th International Conference on Discovery Science, DS 2012. The 23 full papers and 5 invited talks presented were carefully reviewed and selected from 47 submissions. The papers are organized in topical sections on inductive inference, teaching and PAC learning, statistical learning theory and classification, relations between models and data, bandit problems, online prediction of individual sequences, and other models of online learning.

• computational finance
• domain adaptation
• pattern mining
• reinforcement learning
• statistical learning theory
• algorithm analysis and problem complexity

• Department of Computer Science, Technion, Haifa, Israel

  Nader H. Bshouty

• Ecolre Normale Sup’erieure, CNRS, INRIA, Paris, France

  Gilles Stoltz

• Ecole Normale Supérieure de Cachan, Cachan cedex, France

  Nicolas Vayatis

• Division of Computer Science, Hokkaido University, Sapporo, Japan

  Thomas Zeugmann

Policies and ethics