Sample-complexity bound for high-order linear systems
For a broad class of high-order linear systems—equivalently, vector autoregressive processes—the constrained empirical-risk minimizer attains the i.i.d. parametric rate up to logarithmic factors. Its dependence on the system-response condition number \(\kappa\) is only logarithmic, and it incurs no multiplicative mixing-time penalty.
Statement
\[\left\|\widehat{\boldsymbol A}-\boldsymbol A^\star\right\|_F^2 \leq \widetilde{\mathcal O}\!\left(D^2\left(1+\ln\kappa\right)\frac{p d^2}{N(T-p)}\right)\]
- \(p\)
- autoregressive order
- \(d\)
- dimension of each state \(\boldsymbol x_t\in\mathbb R^d\)
- \(N\)
- number of independent trajectories
- \(T\)
- length of each trajectory
- \(D\)
- known bound on the prediction-operator norm and the estimator search space
- \(\kappa\)
- condition number of the system-response operator mapping innovations to the full trajectory
- \(\widetilde{\mathcal O}\)
- asymptotic upper-bound notation suppressing logarithmic factors in the other problem parameters
- \(\boldsymbol A^\star\)
- true block transition matrix \([A_1^\star,\ldots,A_p^\star]\in\mathbb R^{d\times pd}\)
- \(\widehat{\boldsymbol A}\)
- constrained empirical-risk minimizer, also in \(\mathbb R^{d\times pd}\)