Near optimal finite time identification of arbitrary linear dynamical systems

Tuhin Sarkar, Alexander Rakhlin
Proceedings of the 36th International Conference on Machine Learning, PMLR 97:5610-5618, 2019.

Abstract

We derive finite time error bounds for estimating general linear time-invariant (LTI) systems from a single observed trajectory using the method of least squares. We provide the first analysis of the general case when eigenvalues of the LTI system are arbitrarily distributed in three regimes: stable, marginally stable, and explosive. Our analysis yields sharp upper bounds for each of these cases separately. We observe that although the underlying process behaves quite differently in each of these three regimes, the systematic analysis of a self–normalized martingale difference term helps bound identification error up to logarithmic factors of the lower bound. On the other hand, we demonstrate that the least squares solution may be statistically inconsistent under certain conditions even when the signal-to-noise ratio is high.

Cite this Paper

BibTeX
@InProceedings{pmlr-v97-sarkar19a, title = {Near optimal finite time identification of arbitrary linear dynamical systems}, author = {Sarkar, Tuhin and Rakhlin, Alexander}, booktitle = {Proceedings of the 36th International Conference on Machine Learning}, pages = {5610--5618}, year = {2019}, editor = {Chaudhuri, Kamalika and Salakhutdinov, Ruslan}, volume = {97}, series = {Proceedings of Machine Learning Research}, month = {09--15 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v97/sarkar19a/sarkar19a.pdf}, url = {https://proceedings.mlr.press/v97/sarkar19a.html}, abstract = {We derive finite time error bounds for estimating general linear time-invariant (LTI) systems from a single observed trajectory using the method of least squares. We provide the first analysis of the general case when eigenvalues of the LTI system are arbitrarily distributed in three regimes: stable, marginally stable, and explosive. Our analysis yields sharp upper bounds for each of these cases separately. We observe that although the underlying process behaves quite differently in each of these three regimes, the systematic analysis of a self–normalized martingale difference term helps bound identification error up to logarithmic factors of the lower bound. On the other hand, we demonstrate that the least squares solution may be statistically inconsistent under certain conditions even when the signal-to-noise ratio is high.} }
Endnote
%0 Conference Paper %T Near optimal finite time identification of arbitrary linear dynamical systems %A Tuhin Sarkar %A Alexander Rakhlin %B Proceedings of the 36th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2019 %E Kamalika Chaudhuri %E Ruslan Salakhutdinov %F pmlr-v97-sarkar19a %I PMLR %P 5610--5618 %U https://proceedings.mlr.press/v97/sarkar19a.html %V 97 %X We derive finite time error bounds for estimating general linear time-invariant (LTI) systems from a single observed trajectory using the method of least squares. We provide the first analysis of the general case when eigenvalues of the LTI system are arbitrarily distributed in three regimes: stable, marginally stable, and explosive. Our analysis yields sharp upper bounds for each of these cases separately. We observe that although the underlying process behaves quite differently in each of these three regimes, the systematic analysis of a self–normalized martingale difference term helps bound identification error up to logarithmic factors of the lower bound. On the other hand, we demonstrate that the least squares solution may be statistically inconsistent under certain conditions even when the signal-to-noise ratio is high.
APA
Sarkar, T. & Rakhlin, A.. (2019). Near optimal finite time identification of arbitrary linear dynamical systems. Proceedings of the 36th International Conference on Machine Learning, in Proceedings of Machine Learning Research 97:5610-5618 Available from https://proceedings.mlr.press/v97/sarkar19a.html.

Related Material