# No-Regret Prediction in Marginally Stable Systems

arXiv: https://arxiv.org/abs/2002.02064 · HTML: https://mlsanity.com/paper/2002.02064/

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Feb 2020.

## Built on by (most cited first, 18 of 18)

- [Statistical Learning Theory for Control: A Finite Sample Perspective](https://mlsanity.com/paper/2209.05423/) (2022)
- [A New Approach to Learning Linear Dynamical Systems](https://mlsanity.com/paper/2301.09519/) (2023)
- [Spectral State Space Models](https://mlsanity.com/paper/2312.06837/) (2023)
- [Streaming Linear System Identification with Reverse Experience Replay](https://mlsanity.com/paper/2103.05896/) (2021)
- [Butterfly Effects of SGD Noise: Error Amplification in Behavior Cloning and Autoregression](https://mlsanity.com/paper/2310.11428/) (2023)
- [Online Linear Regression in Dynamic Environments via Discounting](https://mlsanity.com/paper/2405.19175/) (2024)
- [Learning from Censored and Dependent Data: The case of Linear Dynamics](https://mlsanity.com/paper/2104.05087/) (2021)
- [Universal Sequence Preconditioning](https://mlsanity.com/paper/2502.06545/) (2025)
- [Predictive Linear Online Tracking for Unknown Targets](https://mlsanity.com/paper/2402.10036/) (2024)
- [Universal Learning of Nonlinear Dynamics](https://mlsanity.com/paper/2508.11990/) (2025)
- [Robust Online Control with Model Misspecification](https://mlsanity.com/paper/2107.07732/) (2021)
- [Model-free Online Learning for the Kalman Filter: Forgetting Factor and Logarithmic Regret](https://mlsanity.com/paper/2505.08982/) (2025)
- [Spectral Filtering for Complex Linear Dynamical Systems](https://mlsanity.com/paper/2601.22400/) (2026)
- [The Complexity of Sequential Prediction in Dynamical Systems](https://mlsanity.com/paper/2402.06614/) (2024)
- [The Power of Second Order Methods for Sequence Preconditioning](https://mlsanity.com/paper/2605.08390/) (2026)
- [Online Nonstochastic Prediction: Logarithmic Regret via Predictive Online Least Squares](https://mlsanity.com/paper/2605.04364/) (2026)
- [Two-Layer Linear Auto-Regressive Models Estimate Latent States](https://mlsanity.com/paper/2606.12691/) (2026)
- [A Memory Efficient Unified Algorithm for Online Learning of Linear Dynamical Systems](https://mlsanity.com/paper/2607.02050/) (2026)

## Abstract (arXiv)

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.