Timezone: »

 
Poster
Learning Linear Dynamical Systems via Spectral Filtering
Elad Hazan · Karan Singh · Cyril Zhang

Tue Dec 05 06:30 PM -- 10:30 PM (PST) @ Pacific Ballroom #7
in Posters Tue »

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.

Keywords: Online Learning · Time Series Analysis · Dynamical Systems · Decision and Control
[ Paper] 

Author Information

Elad Hazan (Princeton University)
Karan Singh (Princeton University)
Cyril Zhang (Princeton University)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors