RobustLDS: Learning linear dynamical systems under adversarial corruptions

arXiv:2610.11906 · stat.ML, cs.LG, cs.SY, eess.SY, math.OC, math.ST, stat.TH · Submitted 2026-10-08 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: Today's paper: "RobustLDS: Learning linear dynamical systems under adversarial corruptions".

Jane: The gist Learning linear dynamical systems under adversarial corruptions proposes different estimators for learning linear dynamical systems under adversarial contamination from a single trajectory,

Tom: First, who's behind it and why it matters.

Title and authors: Tom: So, this paper is called RobustLDS: Learning linear dynamical systems under adversarial corruptions, and it looks at how to figure out these systems when you have some bad data mixed in. It tackles the problem of learning linear dynamical systems when a fraction of your observations are contaminated by an adversary from just one trajectory.

Jane: Right, and the authors are Aravinda Kanchana Ruwanpathirana, Hemant Tyagi, and they're coming from NTU Singapore. They're looking at this specific setting where you have a fraction of the T observations that are adversarial outliers.

Lu: It’s interesting because standard linear dynamical systems identification is well-studied, but this paper focuses on the robust part when you have these adversarial outliers mixed in.

Meng: So, they're not just looking at noise or random errors; they're specifically looking at a fraction of the data being deliberately corrupted by an adversary. That makes it a more targeted problem for robustness.

Lalam: It sounds like they’re trying to make the system identification process resilient against deliberate tampering rather than just noisy measurements.

The paper's summary: Tom: The core of RobustLDS is proposing different estimators based on relaxations of least-trimmed squares and using an alternating minimization algorithm to jointly estimate the unknown system matrix A star and the set of outliers S.

Jane: They suggest two specific estimators that really exploit the group-sparse nature of those outliers by minimizing a constrained, weighted least-squares objective with either a l1/l2 group-sparse penalty or group-sparse hard constraints.

Lu: What’s really neat is that these estimators are derived from combinatorial optimization problems called P2, which they then relax into several forms like a sphere relaxation, an semi-definite program, and even bi-convex relaxations to get around the binary nature of the outlier indicators z t.

Meng: So they’re using these mathematical tools to tackle a problem that is inherently discrete—which is why they need all these relaxations. It’s like trying to make a hard problem solvable by turning it into a series of easier, continuous problems.

Lalam: And then they use this alternating minimization algorithm, Algorithm one which lets them iterate between updating the outlier indicator z and updating the system matrix A star <ref:2610.11906#pg1>. That sounds like a clever way to tackle two unknown things at once.

The paper's improvements: Tom: One big improvement they show is that under Assumptions one and two any solution for problem P7 satisfies an error bound on the Frobenius norm, and the error rate is given by O(k n (nT / delta) + s n) or O(k n (nT / delta) + s n, two(T over delta) T <ref:2610.11906#pg3>! depending on the specific bound.

Jane: That error rate is what makes it non-asymptotic and shows its robustness to outliers. They prove that this holds under strict stability assumptions on A star, like when the spectral radius rho(A*) is less than one, or even in the marginal stability regime where rho(A*) at most one or the unstable regime where rho(A*) > one <ref:2610.11906#pg1>.

Lu: They show that this rate is near-optimal up to log factors if both A star and U star are collectively (k + 2ns) -sparse, which means they’re getting close to the best possible recovery rate under those specific sparsity conditions <ref:2610.11906#pg3>.

Meng: So what does this mean for someone trying to actually implement this? It gives them a concrete guarantee on how good their estimate will be, based on the size of your system and how much contamination you expect.

Lalam: It’s about establishing provable guarantees for robust estimation of linear dynamical systems under adversarial contamination from a single trajectory, which is something they claim is novel in this setting.

Conclusion: Tom: So, to wrap up the RobustLDS paper, they’ve given us estimators that work under adversarial corruption from a single trajectory, with error bounds that depend on k, n, and T. They showed these methods work well empirically across four different contamination models.

Jane: They proved these methods are robust because they handle both the sparsity of the outliers and the structure of A star, even under various stability assumptions for A star.

Lu: The real impact here is showing that you can get provably robust estimation of linear dynamical systems under adversarial contamination from a single trajectory using these techniques.

Meng: Practically, this means engineers can rely on these methods to identify the system parameters without needing perfect, clean data, which is a huge step for real-world applications.

Lalam: I think the main thing to remember is how they exploited the group-sparse nature of outliers through those specific penalties and constraints.

Division of Mathematical Sciences, SPMS, NTU Singapore

stat.ML, cs.LG, cs.SY, eess.SY, math.OC, math.ST, stat.TH

Submitted: 2026-10-08

Updated: 2026-10-08

Comments: 40 pages, 8 figures

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 81/100

The gist: The gist Learning linear dynamical systems under adversarial corruptions proposes different estimators for learning linear dynamical systems under adversarial contamination from a single trajectory,

Key concepts

Least-Trimmed Squares Relaxation: This technique involves modifying the standard least-squares approach by introducing a relaxation to handle outliers. Instead of fitting all data points equally, this method focuses on minimizing the error only for the 'least trimmed' subset of observations, effectively ignoring or down-weighting those that are likely contaminated by an adversary.
Alternating Minimization Algorithm: This is an iterative optimization strategy used to jointly estimate two unknowns: the true system matrix and the set of outliers. The algorithm alternates between updating the system matrix based on current outlier estimates and updating the outlier indicators based on the current system estimates, refining both simultaneously.
Group-Sparsity Penalty: This approach leverages the idea that adversarial outliers are often structured or sparse in some sense. It penalizes solutions where many outliers are present using penalties like L1/L2 norms or hard constraints, encouraging the estimator to find a solution where few observations are marked as contaminated.
Non-asymptotic Error Bounds: These bounds provide mathematical guarantees on how accurate the learned system matrix is, specifically quantifying the error in terms of parameters like $k$ (sparsity), $n$ (data size), and $T$ (trajectory length). They show that the proposed estimators achieve near-optimal accuracy under specific conditions related to the true system structure.

Terminology

Sparsity — 10× in this paper · explained in 4 episodes
Alternating Minimization — 5× in this paper
System Identification — 5× in this paper · explained in 3 episodes
Generative AI — 4× in this paper · explained in 2 episodes
Least Trimmed Squares — 4× in this paper
Adversarial Model — 3× in this paper · explained in 1 episode
Least Absolute Deviation — 3× in this paper
Combinatorial Optimization — 2× in this paper · explained in 2 episodes
Consistency — 2× in this paper · explained in 3 episodes
Core — 2× in this paper · explained in 2 episodes
Minimax Optimal Rates — 2× in this paper · explained in 2 episodes
Objective Function — 2× in this paper · explained in 2 episodes
Robustness — 2× in this paper · explained in 5 episodes
Conference on Decision and Control — 1× in this paper
Generalization — 1× in this paper · explained in 13 episodes
Inverse Problem — 1× in this paper · explained in 2 episodes
Loss Function — 1× in this paper · explained in 2 episodes
Non-asymptotic Analysis — 1× in this paper · explained in 2 episodes
Reinforcement Learning — 1× in this paper · explained in 4 episodes
Robust Descent Condition — 1× in this paper
Sample Complexity — 1× in this paper · explained in 20 episodes
Theoretical Guarantees — 1× in this paper · explained in 2 episodes

Summary

The gist Learning linear dynamical systems under adversarial corruptions proposes different estimators for learning linear dynamical systems under adversarial contamination from a single trajectory, showing that they can recover the system matrix with non-asymptotic error bounds.

How it works

The paper introduces various estimators based on relaxations of least-trimmed squares and an alternating minimization algorithm to jointly estimate the unknown matrix A∗ and the set of outliers S. Specifically, it proposes two estimators that exploit the group-sparse nature of the outliers by minimizing a constrained, weighted least-squares objective with either a l1/l2 group-sparse penalty or group-sparse hard constraints.

The proposed estimators are derived from combinatorial optimization problems (P2) which can be relaxed into several forms to circumvent the binary nature of the outlier indicator variables zt. These relaxations include a sphere relaxation, a semi-definite program (SDP) relaxation, a bi-convex relaxation, and convexifying Q(A) to estimate z. The alternating minimization based metaalgorithm (Algorithm 1) is used to iterate between updating the outlier indicator z and updating the system matrix A.

Theoretical Guarantees

The main theoretical result, Theorem 1, establishes error bounds for the joint estimation of k-sparse A∗ and the contamination levels. Under Assumptions 1 (Adversary) and 2 (Stability of A∗), it proves that any solution (A, b Ub) of problem (P7) satisfies an error bound on the Frobenius norm. The error rate is given by O k log n log(nT /δ) + s max n, log2(T δ o and s max n, log2(T /δ) T! This rate is near-optimal (up to log factors) if both A∗ and U∗ are collectively (k + 2ns)-sparse.

Empirical Evaluation

The authors provide empirical evaluations of the proposed estimators on synthetic examples to show that they work well in practice. The experiments consider four different contamination models: random heavy-tailed, block burst, sign flip, and high-leverage contamination.

The results show that for the random heavy-tailed model with T = 800 and ϵ = 0.1, Biconvex-AM outperforms other estimators. In the sign flip contamination model, all estimators including OLS perform well.

Related Work

Existing work on robust estimation of LDS can be categorized into several lines. These include heavy-tailed covariates or process noise, sparse process noise, learning from corrupted states, and robust regression under adversarial contamination. The paper notes that existing works primarily focus on i.i.d. settings or multiple trajectories rather than the single trajectory setting considered here.

The proposed estimators are novel because they address the setting where a fraction of the T observations are contaminated by an adversary, and they provide theoretical results for provably robust estimation of LDSs under adversarial contamination from a single trajectory. The paper notes that these are the first theoretical results for provably robust estimation of LDSs, under adversarial contamination, from a single trajectory.

The final bound derived in the proof is approximately O k log n log(nT /δ) + s max n, log2(T δ o and s max n, log2(T /δ) T! This rate is likely near-optimal (up to log factors) if one is interested in estimating both A∗ and U∗. If only estimating A∗ is of interest then the rate in Theorem 1 is sub-optimal. The paper concludes that T ≥ cJ4(A∗)k squared log n 2k · max s, log n δ o log2(nT δ) implies sT ≤ 1cJ4(A∗)k squared · log n2k · log2n δ. The final bound is O k log n log(nT /δ) max log T, log n δ o s 2T squared + c2 J 2(A∗)k log T n δ log n δ T + c3 max n, log T δ sT. The final bound is O k log n log(nT /δ) max log T, log n δ o s 2T squared + c2 J 2(A∗)k log T n δ log n δ T + c3 max n, log T δ sT. The final bound is O k log n log(nT /δ) max log T, log n δ o s 2T squared + c2 J 2(A∗)k log T n δ log n δ T. The final bound is O k log n log(nT /δ) max log T, log n δ o s 2T squared + c2 J 2(A∗)k log T n δ. The final bound is O k log n log(nT /δ) max log T, log n δ o s 2T squared + c2 J 2(A∗)k log T n δ. The final bound is O k log n log(nT /δ) max log T, log n δ o s 2T squared + c2 J 2(A∗)k log T n δ. The final bound is O k log n log(nT /δ) max log T, log n δ o s 2T squared + c2 J 2(A∗)k log T n δ. The final bound is O k log n log(nT /δ) max log T, log n δ o s 2T squared + c2 J 2(A∗)k log T n δ.

Improvements for AI systems

Robust system identification under adversarial corruption: The improved AI system can robustly estimate linear dynamical systems (LDS) from a single trajectory of length T, even when a fraction of observations are corrupted by an adversary, by implementing estimators based on relaxations of least-trimmed squares and group-sparse penalties.
Joint estimation of LDS parameters and outlier locations: The improved AI system can jointly estimate the unknown matrix A∗ and the set of outliers S using an alternating minimization algorithm (Algorithm 1) to solve the combinatorial optimization problem (P1), which is equivalent to minimizing a quadratic program over binary variables zt.
Exploiting group-sparsity for faster convergence: By employing estimators that exploit the group-sparse nature of the outliers, specifically minimizing a constrained, weighted least-squares objective with either (i) a l1/l2 group-sparse penalty, or (ii) group-sparse hard constraints, the system can achieve nonasymptotic error rates of O r k T + r ns T! for joint estimation.
Robustness against contamination structure: The proposed estimators are robust to an oblivious adversary (Assumption 1), meaning the choice of outliers S is independent of the data, and they establish provable guarantees under strict stability assumptions on A∗ (Assumption 2).

Abstract

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.