FINITE SAMPLE GUARANTEES FOR LEARNING THE DYNAMICS OF SYSTEMS

The problem of system identification is to learn the system dynamics from data. While classical system identification theories focused primarily on achieving asymptotic consistency, recent efforts have sought to characterize the number of samples needed to achieve a desired level of accuracy in the learned model. This thesis focuses on finite sample analysis for identifying/learning dynamical systems.

In the first part of this thesis, we provide novel results on finite sample analysis for learning different linear systems. We first consider the system identification problem of a fully observed system (i.e., all states of the system can be perfectly measured), leveraging data generated from an auxiliary system that shares ``similar" dynamics. We provide insights on the benefits of using the auxiliary data, and guidelines on selecting the weight parameter during the model training process. Subsequently, we consider the system identification problem for a partially observed autonomous linear system, where only a subset of states and multiple short trajectories of the system can be observed. We present a finite sample error bound and characterize the learning rate.

In the second part of this thesis, we explore the practical usage of finite sample analysis under several different scenarios. We first consider a parameter learning problem in a distributed setting, where a group of agents wishes to collaboratively learn the underlying model. We propose a distributed parameter estimation algorithm and provide finite time bounds on the estimation error. We show that our analysis allows us to determine a time at which the communication can be stopped (due to the costs associated with communications), while meeting a desired estimation accuracy. Subsequently, we consider the problem of online change point detection for a linear system, where the user observes data in an online manner, and the goal is to determine when the underlying system dynamics change. We provide an online change point detection algorithm, and a data-dependent threshold that allows one to achieve a pre-specified upper bound on the probability of making a false alarm. We further provide a finite-sample-based lower bound for the probability of detecting a change point with a certain delay.

Finally, we extend the results to linear model identification from non-linear systems. We provide a data acquisition algorithm followed by a regularized least squares algorithm, along with an associated finite sample error bound on the learned linearized dynamics. Our error bound demonstrates a trade-off between the error due to nonlinearity and the error due to noise, and shows that one can learn the linearized dynamics with arbitrarily small error given sufficiently many samples.