Learning Linear Dynamical Systems via Spectral Filtering

2017/11/02 by Elad Hazan, Karan Singh, Hazan, Elad +3 · 3 citations
Computer Science · Decision Sciences · Engineering · #Advanced Bandit Algorithms Research #FOS: Computer and information sciences #FOS: Electrical engineering #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques #Systems and Control (eess.SY) #electronic engineering #information engineering

paper · pdf · doi:10.48550/arxiv.1711.00946

openalex publication_date 2017/11/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We present an efficient and practical algorithm for the online prediction of discrete-time linear dynamical systems with a symmetric transition matrix. We circumvent the non-convex optimization problem using improper learning: carefully overparameterize the class of LDSs by a polylogarithmic factor, in exchange for convexity of the loss functions. From this arises a polynomial-time algorithm with a near-optimal regret guarantee, with an analogous sample complexity bound for agnostic learning. Our algorithm is based on a novel filtering technique, which may be of independent interest: we convolve the time series with the eigenvectors of a certain Hankel matrix.

Cited by

• Research Program: Theory of Learning in Dynamical Systems
• Logarithmic Regret and Polynomial Scaling in Online Multi-step-ahead Prediction
• Transductive and Learning-Augmented Online Regression

Related

• Spectral Filtering for General Linear Dynamical Systems
• Universal Learning of Nonlinear Dynamics
• SLIP: Learning to Predict in Unknown Dynamical Systems with Long-Term\n Memory
• SpectraLDS: Provable Distillation for Linear Dynamical Systems
• No-Regret Prediction in Marginally Stable Systems