ALT 12 Logo

This volume contains the papers presented at the 23rd International Conference on Algorithmic Learning Theory (ALT 2012), which was held in Lyon, France, October 29–31, 2012. The conference was co-located and held in parallel with the 15th International Conference on Discovery Science (DS 2012). The technical program of ALT 2012 contained 23 papers selected from 47 submissions, and five invited talks. The invited talks were presented in joint sessions of both conferences.

ALT 2012 was dedicated to the theoretical foundations of machine learning and took place in the historical building of the Université Lumière Lyon 2 (berges du Rhônes). ALT provides a forum for high-quality talks with a strong theoretical background and scientific interchange in areas such as inductive inference, universal prediction, teaching models, grammatical inference, complexity of learning, online learning, semi-supervised and unsupervised learning, clustering, statistical learning, regression, bandit problems, Vapnik-Chervonenkis dimension, probably approximately correct learning, information-based methods, and applications of algorithmic learning theory.

The present volume contains the texts of the 23 papers presented at ALT 2012, divided into groups of papers on inductive inference, teaching and PAC–learning, statistical learning theory and classification, relations between models and data, bandit problems, online learning of individual sequences, and on other models of online learning. The volume also contains the texts or abstracts of the invited talks:

Since 1999, ALT has been awarding the E. M. Gold Award for the most outstanding student contribution. This year, the award was given to Ziyuan Gao for his paper “Confident and Consistent Partial Learning of Recursive Functions” co-authored by Frank Stephan.

ALT 2012 was the 23rd in the ALT conference series, established in Japan in 1990. The ALT series is supervised by its Steering Committee: Naoki Abe (IBM Thomas J. Watson Research Center, Yorktown, USA), Shai Ben-David (University of Waterloo, Canada), Nader Bshouty (Technion - Israel Institute of Technology, Israel) Marcus Hutter (Australian National University, Canberra, Australia), Jyrki Kivinen (University of Helsinki, Finland), Philip M. Long (Google, Mountain View, USA), Akira Maruoka (Ishinomaki Senshu University, Japan), Takeshi Shinohara (Kyushu Institute of Technology, Iizuka, Japan), Frank Stephan (National University of Singapore, Republic of Singapore), Gilles Stoltz (Ecole Normale Supérieure, France), Einoshin Suzuki (Kyushu University, Fukuoka, Japan), Csaba Szepesvári (University of Alberta, Canada), Eiji Takimoto (Kyushu University, Fukuoka, Japan), György Turán (University of Illinois at Chicago, USA and University of Szeged, Hungary), Osamu Watanabe (Tokyo Institute of Technology, Japan), Thomas Zeugmann (Chair, Hokkaido University, Japan), and Sandra Zilles (Publicity Chair, University of Regina, Saskatchewan, Canada).

We would like to thank the many people and institutions who contributed to the success of the conference. In particular, we want to thank our authors for contributing to the conference and for coming to Lyon in October 2012. Without their efforts and their willingness to choose ALT 2012 as a forum to report on their research, this conference would not have been possible.

ALT 2012 and DS 2012 were organized by the Université Lumière Lyon 2, France. We are very grateful to the General Chair Djamel Abdelkader Zighed and the General Local Arrangements Chair Stéphane Lallich. We would like to thank them and their team for the tremendous amount of work they have dedicated to making ALT 2012 and DS 2012 a success. We are grateful for the continuous collaboration with the series Discovery Science. In particular, we would like to thank the Conference Chair Jean-Gabriel Ganascia and the Program Committee Chairs Philippe Lenca and Jean-Marc Petit of Discovery Science 2012.

We are also grateful that we could use the excellent conference management system EasyChair for putting together the program for ALT 2011; EasyChair was developed mainly by Andrei Voronkov and is hosted at the University of Manchester. The system is cost-free.

We are grateful to the members of the Program Committee for ALT 2012 and the subreferees for their hard work in selecting a good program for ALT 2012. Reviewing papers and checking the correctness of results is demanding in time and skills and we very much appreciate this contribution to the conference. Last but not least we thank Springer for their support in preparing and publishing this volume in the Lecture Notes in Artificial Intelligence series.

August 2012   Nader H. Bshouty
  Gilles Stoltz
  Nicolas Vayatis
  Thomas Zeugmann


General Chair (ALT 2012 and DS 2012)

Djamel Zighed Université Lumière Lyon 2, France

General Local Chair (ALT 2012 and DS 2012)

Stéphane Lallich Université Lumière Lyon 2, France

ALT 2012 Conference Chair

Nicolas Vayatis Ecole Normale Supérieure de Cachan, France

Program Committee

ALT 2012 Local Arrangements

Fabrice Muhlenbach Université Jean Monnet de Saint-Etienne, France


Mohammad Gheshlaghi AzarYuri Kalnishkan
Peter AntalNikos Karampatziakis
Frank J. BalbachAzadeh Khaleghi
Sébastien BubeckRoni Khardon
John CaseAryeh Kontorovich
Nicolò Cesa-BianchiNathaniel Korda
Karthekeyan ChandrasekaranLuigi Malagò
Archie ChapmanScott McQuade
François CosteSamuel E. Moelius III
Sanmay DasEdward Moroshko
John DuchiFrancesco Orabona
Rafael M. FrongilloRonald Ortner
András GyörgyVikas Sindhwani
Zaïd HarchaouiIstván Szita
Kohei HatanoMatus Telgarsky
David P. HelmboldNina Vaitz
Daniel HsuVladimir Vovk
Benjamin JourdainAndre Wibisono
Satyen KaleThomas Zeugmann

Sponsoring Institutions


©Copyright Notice:
The document of this page is subject to copyright. All rights are reserved, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation, broadcasting, reproduction on microfilms or in any other way, and storage in data banks. Duplication of this publication or parts thereof is permitted only under the provision of the German Copyright Law of September 9, 1965, in its current version, and permission for use must always be obtained from Springer-Verlag. Violations are liable for prosecution under German Copyright Law.

uparrowback to the ALT 2012 Proceedings Page

uparrowuparrow back to the ALT Archives

Valid HTML 4.0