Structural online learning

Mehryar Mohri, Scott Yang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We study the problem of learning ensembles in the online setting, when the hypotheses are selected out of a base family that may be a union of possibly very complex sub-families. We prove new theoretical guarantees for the online learning of such ensembles in terms of the sequential Rademacher complexities of these sub-families. We also describe an algorithm that benefits from such guarantees. We further extend our framework by proving new structural estimation error guarantees for ensembles in the batch setting through a new data-dependent online-to-batch conversion technique, thereby also devising an effective algorithm for the batch setting which does not require the estimation of the Rademacher complexities of base sub-families.

Original languageEnglish (US)
Title of host publicationAlgorithmic Learning Theory - 27th International Conference, ALT 2016, Proceedings
EditorsHans Ulrich Simon, Sandra Zilles, Ronald Ortner
PublisherSpringer Verlag
Pages223-237
Number of pages15
ISBN (Print)9783319463780
DOIs
StatePublished - 2016
Event27th International Conference on Algorithmic Learning Theory, ALT 2016 - Bari, Italy
Duration: Oct 19 2016Oct 21 2016

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9925 LNAI
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other27th International Conference on Algorithmic Learning Theory, ALT 2016
CountryItaly
CityBari
Period10/19/1610/21/16

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Structural online learning'. Together they form a unique fingerprint.

  • Cite this

    Mohri, M., & Yang, S. (2016). Structural online learning. In H. U. Simon, S. Zilles, & R. Ortner (Eds.), Algorithmic Learning Theory - 27th International Conference, ALT 2016, Proceedings (pp. 223-237). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9925 LNAI). Springer Verlag. https://doi.org/10.1007/978-3-319-46379-7_15