Source-linked AI summary
Huber-based Robust System Identification with Near-Optimal Guarantees Across Independent and Adversarial Regimes
Jihun Kim, Javad Lavaei
TL;DR
System identification must handle settings where the disturbance type is unknown, yet least-squares and ℓ1-norm estimators each address only one of the two extreme regimes. The paper applies a Huber estimator to identify the governing matrix from a single trajectory, establishing an optimal error rate for persistent noise under stated conditions and O(µ) error for sparse adversarial attacks.
Problem
Least-squares is limited against biased attacks and ℓ1-norm estimation cannot overcome persistent noise, while the disturbance type is unknown in advance.
Source: §I · p. 1Method
The paper estimates the governing matrix from a single trajectory using a Huber estimator with threshold µ and a SINDy-type nonlinear basis structure.
Source: §I · pp. 1–2Results
The estimator achieves an optimal error rate under persistent zero-mean noise with positive density around zero and symmetry or linear basis functions, and O(µ) error under sparse adversarial attacks.
Source: §I · p. 2, §VIII · p. 10Takeaways & Limitations
The framework provides theoretical guarantees for a SINDy-type identification approach across persistent-noise and sparse-attack regimes.
Source: §I · p. 2
Abstract
from arXiv · showhide
Dynamical systems can confront one of two extreme types of disturbances: persistent zero-mean independent noise, and sparse nonzero-mean adversarial attacks, depending on the specific scenario being modeled. While mean-based estimators like least-squares are well-suited for the former, a median-based approach such as the $\ell_1$-norm estimator is required for the latter. In this paper, we propose a Huber-based estimator, characterized by a threshold constant $\mu$, to identify the governing matrix of a linearly parameterized nonlinear system from a single trajectory of length $T$. This formulation bridges the gap between mean- and median-based estimation, achieving provably robust error in both extreme disturbance scenarios under mild assumptions. In particular, for persistent zero-mean noise with a positive probability density around zero, the proposed estimator achieves an $\mathcal{O}(1/\sqrt{T})$ error rate if the disturbance is symmetric or the basis functions are linear. For arbitrary nonzero-mean attacks that occur at each time with probability smaller than 0.5, the error is bounded by $\mathcal{O}(\mu)$. We validate our theoretical results with experiments illustrating that integrating our approach into frameworks like SINDy yields robust identification of discrete-time systems.
I. INTRODUCTION
The paper frames identification from a single trajectory as necessary when resetting systems is costly or impossible, and proposes Huber estimation for settings where the disturbance regime is unknown.
I. INTRODUCTION
- System identification from a single trajectory avoids forcing resets that can incur massive downtime in infrastructure or cannot be performed for human patients.The task is formulated as estimating an unknown governing matrix from the observed trajectory.Source: §I · p. 1
- Least-squares handles persistent zero-mean noise but fails against adversarial attacks, whereas the ℓ1-norm estimator handles sparse attacks but not persistent noise.The central challenge is that the disturbance type is unknown in advance.Source: §I · p. 1
- The paper proposes a Huber estimator with threshold µ, establishing guarantees across both disturbance extremes for a SINDy-type structure.The framework uses potentially nonlinear basis functions and a sparse target matrix.Source: §I · pp. 1–2
- For persistent zero-mean noise, the estimator has an O(1/√T) error rate under the stated density and symmetry-or-linearity conditions, while sparse adversarial attacks yield O(µ) error.The paper also reports numerical validation of the approach in SINDy-type identification.Source: §I · p. 2
II. PROBLEM FORMULATION AND CORE ASSUMPTIONS
The analysis treats persistent independent zero-mean noise and sparse history-dependent adversarial attacks separately. Its guarantees assume stable trajectories, sub-Gaussian disturbances and initial state, and expected excitation in the relevant regime.
II. PROBLEM FORMULATION AND CORE ASSUMPTIONS
- The system-stability condition is ρL < 1, where ρ is the target matrix's spectral norm and L is the basis function's Lipschitz constant.The first two assumptions are stated to ensure that trajectories generated by the true system do not diverge.Source: §II · p. 2
- The initial state and disturbances are assumed sub-Gaussian, with their coordinate-wise ψ2-norms bounded by σ.The disturbance vectors need not be zero-mean or independent under this assumption.Source: §II · p. 2
- The two disturbance regimes are persistent independent zero-mean noise and attacks chosen arbitrarily by an adversary at times occurring with probability p < 0.5.In the attack scenario, the adversary has access to the system history at attack times.Source: §II · p. 2
- Expected excitation requires the basis functions to cover the full feature space in expectation, either generally or conditional on an attack occurring.The corresponding conditions use λ > 0 and apply to the persistent-noise and attack scenarios, respectively.Source: §II · p. 2
III. HUBER-BASED SYSTEM IDENTIFICATION
The Huber estimator uses a loss that is quadratic for small residuals and linear for large ones. Its threshold µ controls a convex formulation that interpolates between least-squares and ℓ1-norm estimation.
III. HUBER-BASED SYSTEM IDENTIFICATION
- The Huber loss penalizes small residuals quadratically and large residuals linearly, enabling it to bridge least-squares and ℓ1-norm estimation.The residual is the difference between the next state and the modeled state.Source: §III · pp. 2–3
- An equivalent convex formulation combines a least-squares term with an ℓ1 penalty on auxiliary residual variables.The formulation is presented as an alternative to optimizing the Huber loss directly.Source: §III · p. 3
- Large µ makes the estimator approach least-squares, while small positive µ makes it approach the ℓ1-norm estimator.The threshold must be strictly positive for the estimator to be well-posed.Source: §III · p. 3
IV. MAIN RESULTS: NEAR THE BEST OF BOTH WORLDS
The Huber estimator has guarantees in both persistent zero-mean noise and sparse adversarial attacks, with the noise guarantee requiring additional conditions. Its threshold μ must balance the two regimes.
Persistent zero-mean noise
- Under persistent zero-mean noise, the estimator achieves the optimal trajectory-length error rate under an additional mild noise assumption.The stated conditions include positive probability density around zero and symmetric disturbances, unless the basis functions are linear.Source: §IV · p. 3
- The symmetry condition is needed because Huber clipping can bias asymmetric noise; linear basis functions circumvent this requirement.The Huber penalty truncates estimated sample errors to [−μ, μ].Source: §IV · pp. 3–4
Sparse nonzero-mean attacks
- Under sparse nonzero-mean attacks, the Huber estimator bounds estimation error by O(μ) after finite time.The proof uses the ℓ1 estimator’s finite-time exact recovery and the bounded difference between the ℓ1 and Huber losses.Source: §IV · p. 4
Threshold selection
- Choosing μ trades off the regimes: smaller values tighten the attack-error bound, while persistent-noise guarantees require μ above a positive threshold.The paper recommends the minimum μ satisfying Assumption 4; increasing it further does not improve the persistent-noise rate.Source: §IV · p. 4
V. NUMERICAL EXPERIMENTS
The experiments compare least-squares, ℓ1, and Huber estimators on discrete-time systems under persistent noise and sparse attacks. Huber matches least-squares’ rate in the noise setting and retains bounded error under attacks, while reconstructing stable trajectories in both settings.
Experimental setup
- The discrete-time experiments use a three-dimensional system with nonlinear features and compare the three estimators under symmetric persistent noise and state-dependent sparse attacks.The trajectory length is 2500, and the Huber threshold is μ = 0.1.Source: §V · p. 4
Estimation error
- Huber matches least-squares’ O(1/√T) error rate under persistent noise and has O(μ) error under sparse attacks, significantly outperforming least-squares.Under sparse attacks, ℓ1 achieves zero error for T ≥ 100; Figure 1 plots Frobenius error against trajectory length.Source: Figure 1 · p. 4, §V · p. 4
Trajectory stability
- At T = 2500, Huber reconstructs stable trajectories in both disturbance settings; ℓ1 fails to stabilize under persistent noise, while least-squares diverges under attacks.In the attack setting, ℓ1 perfectly reconstructs the true stable trajectory; under persistent noise, least-squares and Huber closely track it.Source: §V · p. 4, Figure 2 · p. 5
VI. PROOF OF THEOREM 1
The proof develops concentration bounds for the noisy trajectory and uses them to connect expected excitation with empirical excitation. These bounds support the analysis of the Huber estimator under persistent zero-mean noise.
VI. PROOF OF THEOREM 1
- The proof uses vector-valued martingale bounds to control sums of zero-conditional-mean terms arising in the estimator analysis.It also bounds trajectory and feature magnitudes before applying concentration arguments.Source: §VI · pp. 5–6
- The proof bounds trajectory and feature-vector magnitudes using stability and sub-Gaussian assumptions before applying concentration.The trajectory bound uses a geometric sum, while the feature bound is used in the excitation argument.Source: §VI · pp. 5, 7
- Sufficient expected excitation implies sufficient empirical excitation with high probability under the stated assumptions.The excitation condition requires feature vectors to cover the parameter space in expectation.Source: §VI · pp. 6–7
3. Since (19) dominates (20),
Theorem 1 establishes an O(1/√T) estimation error rate under persistent zero-mean independent noise. Its proof controls the objective's gradient using samples with small residuals and sufficient excitation.
3. Since (19) dominates (20),
- O(1/√T) error is achieved by the Huber estimator under persistent zero-mean independent noise.The proof establishes optimality conditions and bounds the error with high probability.Source: §3 · p. 7
- The proof uses time indices with small residuals and perturbations to obtain a lower bound on the objective's Jacobian along candidate parameter errors.These indices remain in the relevant set along the segment from zero to the error vector.Source: §3 · pp. 7–8
- A sufficiently large trajectory length makes the resulting boundary inequality hold with high probability, bounding the estimator's error.The argument combines the bounds on the index set and feature norms with a union bound.Source: §3 · p. 8
VII. PROOF OF THEOREM 2
Theorem 2 analyzes sparse nonzero-mean attacks, first establishing exact recovery for the ℓ1-norm estimator and then bounding Huber-estimator error by O(µ). The proof compares the Huber objective with the absolute-residual objective.
VII. PROOF OF THEOREM 2
- The attack-regime proof assumes sufficient expected excitation conditional on an attack and controls the number of attacked time indices.These bounds support the objective comparison and recovery argument.Source: §VII · pp. 8–9
- Under Scenario 2 and the stated assumptions, the ℓ1-norm estimator uniquely recovers the true system matrix with probability at least 1 − δ.The proof lower-bounds the objective's change using non-attacked and attacked time indices.Source: §VII · pp. 8–9
- The Huber estimator's estimation error is bounded by O(µ) under sparse nonzero-mean adversarial attacks.The proof uses a bound on the difference between the scaled Huber and absolute-residual objectives, together with optimality.Source: §VII · pp. 9–10
VIII. CONCLUSION
The conclusion presents the Huber estimator as a middle ground between least-squares and ℓ1-norm estimation. It reports near-optimal error under specified persistent-noise conditions and bounded error under sparse adversarial attacks.
VIII. CONCLUSION
- The Huber estimator provides a principled middle ground between least-squares and ℓ1-norm estimators for robust system identification.The framework is presented as a unified theoretical treatment of both disturbance regimes.Source: §VIII · p. 10
- O(1/√T) error is achieved with positive noise density around zero when disturbances are symmetric or basis functions are linear.The conclusion characterizes this rate as optimal.Source: §VIII · p. 10
- The Huber estimator has bounded constant estimation error against sparse adversarial attacks.The conclusion describes these results as unified guarantees across both extreme disturbance regimes.Source: §VIII · p. 10