No-Regret Prediction in Marginally Stable Systems
arXiv:2002.02064
Abstract
We consider the problem of online prediction in a marginally stable linear dynamical system subject to bounded adversarial or (non-isotropic) stochastic perturbations. This poses two challenges. Firstly, the system is in general unidentifiable, so recent and classical results on parameter recovery do not apply. Secondly, because we allow the system to be marginally stable, the state can grow polynomially with time; this causes standard regret bounds in online convex optimization to be vacuous. In spite of these challenges, we show that the online least-squares algorithm achieves sublinear regret (improvable to polylogarithmic in the stochastic setting), with polynomial dependence on the system's parameters. This requires a refined regret analysis, including a structural lemma showing the current state of the system to be a small linear combination of past states, even if the state grows polynomially. By applying our techniques to learning an autoregressive filter, we also achieve logarithmic regret in the partially observed setting under Gaussian noise, with polynomial dependence on the memory of the associated Kalman filter.
arXiv comment43 pages. Appears in COLT 2020
References in corpus (10)
- Gradient Descent Learns Linear Dynamical Systems
- Optimization, Learning, and Games with Predictable Sequences
- On the Sample Complexity of the Linear Quadratic Regulator
- Near optimal finite time identification of arbitrary linear dynamical systems
- Online Learning for Time Series Prediction
- Non-Asymptotic Analysis of Robust Control from Coarse-Grained Identification
- Learning Without Mixing: Towards A Sharp Analysis of Linear System Identification
- Learning Linear Dynamical Systems with Semi-Parametric Least Squares
- Spectral Filtering for General Linear Dynamical Systems
- Robust guarantees for learning an autoregressive filter