Timezone: »
Talk
Spectral Learning from a Single Trajectory under Finite-State Policies
Borja de Balle Pigem · Odalric Maillard
We present spectral methods of moments for learning sequential models from a single trajectory, in stark contrast with the classical literature that assumes the availability of multiple i.i.d. trajectories. Our approach leverages an efficient SVD-based learning algorithm for weighted automata and provides the first rigorous analysis for learning many important models using dependent data. We state and analyze the algorithm under three increasingly difficult scenarios: probabilistic automata, stochastic weighted automata, and reactive predictive state representations controlled by a finite-state policy. Our proofs include novel tools for studying mixing properties of stochastic weighted automata.
Summary/NotesAuthor Information
Borja de Balle Pigem (Amazon Research Cambridge)
Odalric Maillard
Related Events (a corresponding poster, oral, or spotlight)
-
2017 Poster: Spectral Learning from a Single Trajectory under Finite-State Policies »
Tue. Aug 8th 08:30 AM -- 12:00 PM Room Gallery #52
More from the Same Authors
-
2020 Poster: Private Reinforcement Learning with PAC and Regret Guarantees »
Giuseppe Vietri · Borja de Balle Pigem · Akshay Krishnamurthy · Steven Wu -
2018 Poster: Improving the Gaussian Mechanism for Differential Privacy: Analytical Calibration and Optimal Denoising »
Borja de Balle Pigem · Yu-Xiang Wang -
2018 Oral: Improving the Gaussian Mechanism for Differential Privacy: Analytical Calibration and Optimal Denoising »
Borja de Balle Pigem · Yu-Xiang Wang