No-Regret Prediction in Marginally Stable Systems

Udaya Ghai, Holden Lee, Karan Singh, Cyril Zhang, Yi Zhang
Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:1714-1757, 2020.

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v125-ghai20a, title = {No-Regret Prediction in Marginally Stable Systems}, author = {Ghai, Udaya and Lee, Holden and Singh, Karan and Zhang, Cyril and Zhang, Yi}, booktitle = {Proceedings of Thirty Third Conference on Learning Theory}, pages = {1714--1757}, year = {2020}, editor = {Abernethy, Jacob and Agarwal, Shivani}, volume = {125}, series = {Proceedings of Machine Learning Research}, month = {09--12 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v125/ghai20a/ghai20a.pdf}, url = {https://proceedings.mlr.press/v125/ghai20a.html}, 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.} }
Endnote
%0 Conference Paper %T No-Regret Prediction in Marginally Stable Systems %A Udaya Ghai %A Holden Lee %A Karan Singh %A Cyril Zhang %A Yi Zhang %B Proceedings of Thirty Third Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2020 %E Jacob Abernethy %E Shivani Agarwal %F pmlr-v125-ghai20a %I PMLR %P 1714--1757 %U https://proceedings.mlr.press/v125/ghai20a.html %V 125 %X 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.
APA
Ghai, U., Lee, H., Singh, K., Zhang, C. & Zhang, Y.. (2020). No-Regret Prediction in Marginally Stable Systems. Proceedings of Thirty Third Conference on Learning Theory, in Proceedings of Machine Learning Research 125:1714-1757 Available from https://proceedings.mlr.press/v125/ghai20a.html.

Related Material