CLT-Optimal Parameter Error Bounds for Linear System Identification
There has been remarkable progress over the past decade in establishing finite-sample, non-asymptotic bounds on recovering unknown system parameters from observed system behavior. Surprisingly, however, we show that the current state-of-the-art bounds do not accurately capture the statistical complexity of system identification, even in the most fundamental setting of estimating a discrete-time linear dynamical system (LDS) via ordinary least-squares regression (OLS). Specifically, we utilize asymptotic normality to identify classes of problem instances for which current bounds overstate the squared parameter error, in both spectral and Frobenius norm, by a factor of the state-dimension of the system. Informed by this discrepancy, we then sharpen the OLS parameter error bounds via a novel second-order decomposition of the parameter error, where crucially the lower-order term is a matrix-valued martingale that we show correctly captures the CLT scaling. From our analysis we obtain finite-sample bounds for both (i) stable systems and (ii) the many-trajectories setting that match the instance-specific optimal rates up to constant factors in Frobenius norm, and polylogarithmic state-dimension factors in spectral norm.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Solving Elliptic Optimal Control Problems via Neural Networks and Optimality System
In this work, we investigate a neural network based solver for optimal control problems (without / with box constraint) for linear and semilinear second-order elliptic problems. It utilizes a coupled system derived from …
Robust Optimal Control for Nonlinear Systems with Parametric Uncertainties via System Level Synthesis
This paper addresses the problem of optimally controlling nonlinear systems with norm-bounded disturbances and parametric uncertainties while robustly satisfying constraints. The proposed approach jointly optimizes a nom…
Certainty Equivalence is Efficient for Linear Quadratic Control
We study the performance of the certainty equivalent controller on Linear Quadratic (LQ) control problems with unknown transition dynamics. We show that for both the fully and partially observed settings, the sub-optimal…
Minimal Order Recovery through Rank-adaptive Identification
This paper addresses the problem of identifying linear systems from noisy input-output trajectories. We introduce Thresholded Ho-Kalman, an algorithm that leverages a rank-adaptive procedure to estimate a Hankel-like mat…
Towards a Dimension-Free Understanding of Adaptive Linear Control
We study the problem of adaptive control of the linear quadratic regulator for systems in very high, or even infinite dimension. We demonstrate that while sublinear regret requires finite dimensional inputs, the ambient …