On the rademacher complexity of weighted automata

Borja Balle, Mehryar Mohri

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


Weighted automata (WFAs) provide a general framework for the representation of functions mapping strings to real numbers. They include as special instances deterministic finite automata (DFAs), hidden Markov models (HMMs), and predictive states representations (PSRs). In recent years, there has been a renewed interest in weighted automata in machine learning due to the development of efficient and provably correct spectral algorithms for learning weighted automata. Despite the effectiveness reported for spectral techniques in real-world problems, almost all existing statistical guarantees for spectral learning of weighted automata rely on a strong realizability assumption. In this paper, we initiate a systematic study of the learning guarantees for broad classes of weighted automata in an agnostic setting. Our results include bounds on the Rademacher complexity of three general classes of weighted automata, each described in terms of different natural quantities. Interestingly, these bounds underline the key role of different data-dependent parameters in the convergence rates.

Original languageEnglish (US)
Title of host publicationAlgorithmic Learning Theory - 26th International Conference, ALT 2015
EditorsClaudio Gentile, Sandra Zilles, Kamalika Chaudhuri
PublisherSpringer Verlag
Number of pages15
ISBN (Print)9783319244853
StatePublished - 2015
Event26th International Conference on Algorithmic Learning Theory, ALT 2015 - Banff, Canada
Duration: Oct 4 2015Oct 6 2015

Publication series

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


Other26th International Conference on Algorithmic Learning Theory, ALT 2015

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'On the rademacher complexity of weighted automata'. Together they form a unique fingerprint.

Cite this