RobustLDS: Learning linear dynamical systems under adversarial corruptions
summary
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,
In short
The work proposes estimators for learning linear dynamical systems when a fraction of observations are corrupted by an adversary. It introduces methods based on relaxing least-trimmed squares and alternating minimization, along with estimators exploiting group-sparsity of outliers. The results provide non-asymptotic error bounds proving the robustness of these methods 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 used across episodes
This episode discusses
- RobustLDS: Learning linear dynamical systems under adversarial corruptions · Paper Radio
- Efficient and Consistent Robust Time Series Analysis
- Optimal Robust Linear Regression in Nearly Linear Time
- Robust Sparse Estimation for Gaussians with Optimal Error under Huber Contamination
- Tail-robust estimation of factor-adjusted vector autoregressive models for high-dimensional time series
- Robust Estimation of Sparse, High Dimensional Time Series with Polynomial Tails
- Huber-based Robust System Identification with Near-Optimal Guarantees Across Independent and Adversarial Regimes
- System Identification under Noise and Attack Regimes: Agnostic and Composite Robustness
- High Dimensional Robust M-Estimation: Arbitrary Corruption and Heavy Tails
- Robust and Sparse Estimation of Linear Regression Coefficients with Heavy-tailed Noises and Covariates
- Robust estimation with Lasso when outputs are adversarially contaminated
- Large Vector Auto Regressions
- Learning linear dynamical systems under convex constraints · Paper Radio
- Robust estimation for high-dimensional time series with heavy tails
The paper
RobustLDS: Learning linear dynamical systems under adversarial corruptions · Read on arXiv
Division of Mathematical Sciences, SPMS, NTU Singapore
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.
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.
More episodes
- 2610.11038-Decision-Sufficient Posterior Approximation
- 2610.11082-A General (sqrt T gamma T) Lower Bound for Kernel Bandits
- 2610.11139-Accelerating Non-Smooth and Heavy-Tailed Sampling
- 2610.11145-Tight Bounds for Equivalence Testing with Non-Adaptive Conditional Samples
- 2610.11226-When Lower Reconstruction Loss Hurts: Distributionally Robust Refinement for Low-Bit LLM Quantization
- 2610.11266-Regularized Small Area Estimation with Graph Laplacian Benchmarking priors
- 2610.11388-Sequential Conditional Independence Testing with Machine Learning Models
- 2610.11475-Rare Gate Disagreements Can Limit Plasticity: When Gradient Flow Mispredicts Finite-Batch SGD
- 2610.11407-Beyond Distributional Fidelity: Causal-Penalized Diffusion for Synthetic Tabular Data
- 2610.11459-Feature Space Adaptation for Effortless Gaussian Process Flows