We consider the problem of learning linear dynamical systems under adversarial contamination from a single trajectory of length T. While identification of linear dynamical systems itself is well-studied, the problem of robust system identification under adversarial contamination is relatively less explored. In this work, we study the setting where a fraction of the T observations are contaminated by adversarial outliers. We propose different estimators based on relaxations of least-trimmed squares along with an alternating minimization algorithm. Furthermore, we also propose two estimators which exploit the group-sparsity (through penalization/hard-constraints) of the outliers. For the estimator with group-sparse penalty, we derive non-asymptotic error bounds which establish its robustness to outliers. We also show empirically that the proposed estimators work well in practice.
Figures & tables
Figure 1: Frobenius norm error, A−A∗F/A∗F , for T∈{50,100,200,400,800} with (a) ϵ=0 , (b) ϵ=0.02 , and (c) ϵ=0.1 , under the random heavy-tailed contamination model.
Figure 2: Frobenius norm error, A−A∗F/A∗F , for ϵ∈{0,0.01,0.02,0.05,0.1} with (a) T=100 , (b) T=400 , and (c) T=800 , under the random heavy-tailed contamination model.
Sphere-AM
Sphere Relaxation.
SDP-AM
Semi-definite program Relaxation.
Biconvex-AM
Bi-convex relaxation.
ConvexQ(A)-AM
Convexifying Q(A) to estimate z .
LS-BSP
LS with block-sparse penalty.
LS-BSHC
LS with block-sparse constraints.
OLS
A -constrained least squares.
Table 3
Appendix figures & tables6 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 3: Frobenius norm error, A−A∗F/A∗F , for T∈{50,100,200,400,800} with (a) ϵ=0 , (b) ϵ=0.02 , and (c) ϵ=0.1 , for block burst contamination model.
Figure 4: Frobenius norm error, A−A∗F/A∗F , for ϵ={0,0.01,0.02,0.05,0.1} with (a) T=100 , (b) T=400 , and (c) T=800 , for block burst contamination model.
Figure 5: Frobenius norm error, A−A∗F/A∗F , for T∈{50,100,200,400,800} with (a) ϵ=0 , (b) ϵ=0.02 , and (c) ϵ=0.1 , under the sign flip contamination model.
Figure 6: Frobenius norm error, A−A∗F/A∗F , for ϵ={0,0.01,0.02,0.05,0.1} with (a) T=100 , (b) T=400 , and (c) T=800 , under the sign flip contamination model.
Figure 7: Frobenius norm error, A−A∗F/A∗F , for T∈{50,100,200,400,800} with (a) ϵ=0 , (b) ϵ=0.02 , and (c) ϵ=0.1 , under the high-leverage contamination model.
Figure 8: Frobenius norm error, A−A∗F/A∗F , for ϵ={0,0.01,0.02,0.05,0.1} with (a) T=100 , (b) T=400 , and (c) T=800 , under the high-leverage contamination model.
We consider the problem of learning structured linear dynamical systems over convex sets K, where only a small subset of the observations are available at each time point. An estimator which minimizes a bias-corrected, potentially non-convex objective function is proposed. Non-asymptotic bounds are obtained for the statistical error, which depend on the local complexity of K, the trajectory length T, and the sub-sampling probability p. Convergence of the projected gradient descent algorithm is also established. The general theory is applied to settings where (i) K is a subspace, (ii) K is the set of bi-isotonic matrices, and (iii) K is the set of matrices whose rows are formed by sampling Lipschitz functions. We show meaningful recovery of the transition matrix is possible for values of T much smaller than what is required in the unconstrained case, and for p=o(1).
Aravinda Kanchana Ruwanpathirana, Hemant Tyagi, Sunny G. W. Wang
Division of Mathematical Sciences, SPMS, NTU Singapore 637371
We consider the problem of learning the parameters of a N-dimensional stochastic linear dynamics under both full and partial observations from a single trajectory of time T. We introduce and analyze a new estimator that achieves a small maximum element-wise error on the recovery of symmetric dynamic matrices using only T=O(logN) observations, irrespective of whether the matrix is sparse or dense. This estimator is based on the method of moments and does not rely on problem-specific regularization. This is especially important for applications such as structure discovery.
Minh Vu, Andrey Y. Lokhov, Marc Vuffray
Theoretical Division, Los Alamos National Laboratory, Los Alamos, NM 87545, USA
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.
Yichen Zhou, Stephen Tu
Ming Hsieh Department of Electrical and Computer Engineering, University of Southern California, Los Angeles, California, USA.