Generalization bounds for learning weighted automata

Borja Balle, Mehryar Mohri

Research output: Contribution to journalArticlepeer-review


This paper studies the problem of learning weighted automata from a finite sample of strings with real-valued labels. We consider several hypothesis classes of weighted automata defined in terms of three different measures: the norm of an automaton's weights, the norm of the function computed by an automaton, and the norm of the corresponding Hankel matrix. We present new data-dependent generalization guarantees for learning weighted automata expressed in terms of the Rademacher complexity of these classes. We further present upper bounds on these Rademacher complexities, which reveal key new data-dependent terms related to the complexity of learning weighted automata.

Original languageEnglish (US)
Pages (from-to)89-106
Number of pages18
JournalTheoretical Computer Science
StatePublished - Mar 15 2018


  • Generalization bounds
  • Learning theory
  • Rademacher complexity
  • Weighted automata

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Generalization bounds for learning weighted automata'. Together they form a unique fingerprint.

Cite this