Data driven modeling in the presence of time series structure: : Improved bounds and effective algorithms

This thesis consists of five appended papers devoted to modeling tasks where the desired models are learned from data sets with an underlying time series structure. We develop a statistical methodology for providing efficient estimators and analyzing their non-asymptotic behavior. We further suggest novel algorithmic design techniques for obtaining practical procedures to compute these estimators. Specifically, we study time series models of increasing levels of difficulty. In the first paper, we study change point and clustering systems where the dynamic structure of the time series is entirely encoded in the combinatorial properties of the estimated parameters. We then investigate in the second paper Finite Input Response (FIR) models, which exhibit a time-shifted random design. The obtained results are then generalized in the third paper to linear Hidden Markov models since they are infinite impulse response models with a particular polynomial structure. Finally, in the fourth and fifth papers, we investigate linear time-invariant (LTI) state-space models where the covariates generated along the path of the system are not just dependent but also dependent on the estimated parameter. Hence, the spectral properties of this estimated parameter affect the estimation performance. Throughout this journey, we develop a statistical methodology for deriving statistically efficient estimators. This statistical methodology relays on the idea that efficient estimators should strike a compromise between a signal term and a noise term. The signal term is intimately related to the spectral properties of the design matrix, and the noise term is intimately associated with the covariates multiplication process. To quantify both of these terms and obtain upper bounds for the estimation errors, we develop new concentration and deviation inequalities based on chaining integrals and self-normalized martingale inequalities. We also obtain lower bounds for the estimation errors by extending the Cramér-Rao inequality to a biased ...