Research map / Learning theory and algorithms / Prediction and decision losses
Learning the Uncertainty Sets of Linear Control Systems via Set Membership: A Non-asymptotic Analysis
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Gives the first non-asymptotic convergence-rate bounds for set membership estimation (SME) of linear dynamical systems under bounded i.i.d. disturbances and BMSB excitation, plus a UCB-SME variant for unknown disturbance bounds.
Problem
Set membership estimation for uncertainty sets of unknown linear systems x_{t+1}=A*x_t+B*u_t+w_t has no non-asymptotic convergence rate, especially with correlated data and bounded disturbances.
Approach
Analyze SME's diameter via a stopping-time-based event construction that handles correlation between regressors and past disturbances, using the block-martingale small-ball condition for persistent excitation; extend to unknown disturbance bounds via a learned upper confidence bound (UCB-SME).
Key results
- SME with known tight disturbance bound achieves diameter rate Õ(n_x^{1.5}(n_x+n_u)^2/T) under q_w(ε)=Ω(ε) distributions, faster in T than the LSE rate O(sqrt(n_x+n_u)/sqrt(T)).
- UCB-SME achieves the same T-rate as SME with known bound, with a sqrt(n_x) worse dimension dependence.
- In simulations on Boeing 747 dynamics, SME and UCB-SME yield smaller diameters than 90% LSE confidence regions and converge faster.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use SME or UCB-SME instead of the LSE 90% confidence region | Boeing 747 system identification · Boeing 747 dynamics with truncated Gaussian and uniform disturbances | uncertainty-set diameter | Helped |
| Use SME instead of the LSE 90% confidence region for estimating the model uncertainty set | Tube-based robust adaptive MPC · Constrained linear quadratic tracking | tracking performance | Helped |
| Use SME rather than LSE confidence regions | System identification across varying system dimensions · Autonomous linear systems with truncated Gaussian and uniform disturbances | dimension scaling | No clear effect |
Surprising findings
- Simulations show SME's dimension scaling is not significantly worse than LSE's, suggesting the theoretical n_x dependence is a proof artifact.
- SME does not converge under unbounded Gaussian disturbances, so it is suited to bounded-disturbance settings.
Limitations
- Analysis restricted to box-shaped disturbance support and diameter as the size metric.
- Dimension dependence (n_x^{3.5}-type) is loose compared to simulations.
- Computational complexity grows linearly with the number of samples; approximate SME convergence is unknown.
Experimental setup
Datasets: simulated linear systems (Boeing 747 longitudinal flight dynamics, 1D system, autonomous systems of varying dimension)
Benchmarks: simulated linear systems (Boeing 747 dynamics, scaling with dimension, robust adaptive MPC linear quadratic tracking)
Metrics: diameter of uncertainty set (Frobenius norm) tracking performance
Baselines: least squares estimation 90% confidence regions
Builds on: block-martingale small-ball condition least squares estimation confidence regions robust system level synthesis robust adaptive MPC
Closest papers by meaning
- Identification of Analytic Nonlinear Dynamical Systems with Non-asymptotic Guarantees (NeurIPS 2024 · similarity 0.88)
- Robust System Identification: Finite-sample Guarantees and Connection to Regularization (ICLR 2025 · similarity 0.86)
- Certainty Equivalence is Efficient for Linear Quadratic Control (NeurIPS 2019 · similarity 0.84)
- Finite Sample Analyses for Continuous-time Linear Systems: System Identification and Online Control (NeurIPS 2025 · similarity 0.83)
- Disentangling Linear Quadratic Control with Untrusted ML Predictions (NeurIPS 2024 · similarity 0.81)
- PAC-Bayesian Error Bound, via Rényi Divergence, for a Class of Linear Time-Invariant State-Space Models (ICML 2024 · similarity 0.81)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.