Algorithmic Learning Theory

1. Front Matter

   PDF

2. Editors’ Introduction

   • Sanjay Jain, Rémi Munos, Frank Stephan, Thomas Zeugmann

   Pages 1-12

3. Full Invited Papers

   1. Learning and Optimizing with Preferences

      • Nir Ailon

      Pages 13-21

   2. Efficient Algorithms for Combinatorial Online Prediction

      • Eiji Takimoto, Kohei Hatano

      Pages 22-32

   3. Exact Learning from Membership Queries: Some Techniques, Results and New Directions

      • Nader H. Bshouty

      Pages 33-52

4. Regular Contributions

   1. Online Learning

      1. Universal Algorithm for Trading in Stock Market Based on the Method of Calibration

         • Vladimir V’yugin

         Pages 53-67

      2. Combinatorial Online Prediction via Metarounding

         • Takahiro Fujita, Kohei Hatano, Eiji Takimoto

         Pages 68-82

      3. On Competitive Recommendations

         • Jara Uitto, Roger Wattenhofer

         Pages 83-97

      4. Online PCA with Optimal Regrets

         • Jiazhong Nie, Wojciech Kotłowski, Manfred K. Warmuth

         Pages 98-112

   2. Inductive Inference and Grammatical Inference

      1. Partial Learning of Recursively Enumerable Languages

         • Ziyuan Gao, Frank Stephan, Sandra Zilles

         Pages 113-127

      2. Topological Separations in Inductive Inference

         • John Case, Timo Kötzing

         Pages 128-142

      3. PAC Learning of Some Subclasses of Context-Free Grammars with Basic Distributional Properties from Positive Data

         • Chihiro Shibata, Ryo Yoshinaka

         Pages 143-157

      4. Universal Knowledge-Seeking Agents for Stochastic Environments

         • Laurent Orseau, Tor Lattimore, Marcus Hutter

         Pages 158-172

   3. Teaching and Learning from Queries

      1. Order Compression Schemes

         • Malte Darnstädt, Thorsten Doliwa, Hans Ulrich Simon, Sandra Zilles

         Pages 173-187

      2. Learning a Bounded-Degree Tree Using Separator Queries

         • M. Jagadish, Anindya Sen

         Pages 188-202

   4. Bandit Theory

      1. Faster Hoeffding Racing: Bernstein Races via Jackknife Estimates

         • Po-Ling Loh, Sebastian Nowozin

         Pages 203-217

      2. Robust Risk-Averse Stochastic Multi-armed Bandits

         • Odalric-Ambrym Maillard

         Pages 218-233

      3. An Efficient Algorithm for Learning with Semi-bandit Feedback

         • Gergely Neu, Gábor Bartók

         Pages 234-248

   5. Statistical Learning Theory

      1. Differentially-Private Learning of Low Dimensional Manifolds

         • Anna Choromanska, Krzysztof Choromanski, Geetha Jagannathan, Claire Monteleoni

         Pages 249-263

      2. Generalization and Robustness of Batched Weighted Average Algorithm with V-Geometrically Ergodic Markov Data

         • Nguyen Viet Cuong, Lam Si Tung Ho, Vu Dinh

         Pages 264-278

This book constitutes the proceedings of the 24th International Conference on Algorithmic Learning Theory, ALT 2013, held in Singapore in October 2013, and co-located with the 16th International Conference on Discovery Science, DS 2013. The 23 papers presented in this volume were carefully reviewed and selected from 39 submissions. In addition the book contains 3 full papers of invited talks. The papers are organized in topical sections named: online learning, inductive inference and grammatical inference, teaching and learning from queries, bandit theory, statistical learning theory, Bayesian/stochastic learning, and unsupervised/semi-supervised learning.

• combinatorial optimization
• gradient algorithms
• online learning
• reinforcement learning
• universal artificial intelligence
• algorithm analysis and problem complexity

• National University of Singapore, Republic of Singapore

  Sanjay Jain, Frank Stephan

• Inria Lille - Nord Europe, Villeneuve d’Ascq, France

  Rémi Munos

• Hokkaido University, Sapporo, Japan

  Thomas Zeugmann

Policies and ethics