REVIEW 2 major objections 2 minor 28 references
Boosting-Enabled Robust System Identification of Partially Observed LTI Systems Under Heavy-Tailed Noise
T0 review · 2 major / 2 minor · reviewed 2026-08-16 · deepseek-v4-flash
Pith's one-line read This paper proves that a partially observed linear system's input-response matrices can be estimated with high confidence under noise that has only a finite variance, without any Gaussian tail assumption.
desk verdict Solid, honest theory paper: first finite-sample guarantee for partially observed LTI identification under second-moment noise, with a clean median-of-means proof and no load-bearing flaw. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing mechanism is boosting by geometric median in the matrix space $\mathbb{R}^{p\times mT}$ equipped with the Frobenius norm (the entrywise Euclidean norm): $\hat G=\arg\min_{\theta}\sum_{j=1}^K\|\theta-\hat G_j\|_F$. Its stability lemma (Lemma 6 in the paper) states that if the median is far from the truth, then a positive fraction of the bucket estimators must themselves be far from the truth; with only $1/8$ of buckets failing, $K=\lceil32\log(1/\delta)\rceil$ buckets push the overall failure probability below $\delta$. Because the noise is only heavy-tailed, the per-bucket analysis replaces Chernoff-type bounds with Markov's inequality on squared Frobenius norms, using the variance additivity identity for independent matrix summands. The finite fourth moment of the input enters precisely where $\mathbb{E}[\|\hat u\|^4]\le(mT)^2\tilde\sigma_u^4$ is used to prove that the per-bucket Gram matrix $U_jU_j^\top$ is invertible with the stated sample size.
What would settle it
Run the algorithm with a zero-mean input that has finite covariance but infinite fourth moment, such as a multivariate $t$ distribution with four degrees of freedom, choosing $K=\lceil32\log(1/\delta)\rceil$ and any finite bucket size $M$. The theorem's proof specifically requires $M\gtrsim(mT)^2(\tilde\sigma_u^4/\sigma_u^4)$, which diverges when $\tilde\sigma_u^4$ is infinite; if the empirical failure frequency still stays below $\delta$ with an error matching the bound, the fourth-moment assumption is unnecessary, while an ill-conditioned $U_jU_j^\top$ or a degraded rate would confirm it is load-bearing.
Extended reading notes
Core claim
The paper's central claim is that, under zero-mean i.i.d. noise with covariance matrices $\sigma_w^2 I_n$ and $\sigma_v^2 I_p$, and a zero-mean i.i.d. input with covariance $\sigma_u^2 I_m$ and finite fourth moment $\tilde\sigma_u^4$, the estimator described above achieves, with probability at least $1-\delta$, $$\|\hat G-G\|\le \frac{\sigma_v C_1+\sigma_w C_2}{\sigma_u}\sqrt{\frac{p\log(1/\delta)}{N}},$$ where $C_1=c_1T^{1.5}\sqrt{pm}$, $C_2=c_2\|F\|T^{2.5}\sqrt{nm}$, $K=\lceil32\log(1/\delta)\rceil$, $M\ge c_4(mT)^2(\tilde\sigma_u^4/\sigma_u^4)$, and $N=MK$. Here $G=[D\;CB\;CAB\;\cdots\;CA^{T-2}B]$ is the block of the first $T$ Markov parameters, and $\hat G$ is the geometric median of the per-bucket least-squares estimates. The bound matches the multi-trajectory sub-Gaussian rate up to a factor of order $T\max(n,m,p)$, and the Ho-Kalman realization step then transfers the logarithmic confidence to estimates of the original system matrices $(A,B,C,D)$ up to similarity transformation.
Load-bearing premise
The load-bearing premise is that the excitation input has a finite fourth moment; the proof's guarantee that the least-squares fit in each bucket is well posed uses an average of the fourth power of the input, and without that moment the stated sample-size condition has no force.
Editorial extensions
If this is right
- Via the Ho-Kalman realization step, the $\log(1/\delta)$ dependence transfers from the Markov parameters to estimates of $(A,B,C,D)$ up to similarity, so downstream model-based control can inherit high-probability model-error bounds under heavy-tailed noise.
- The per-bucket sample requirement $M\gtrsim(mT)^2(\tilde\sigma_u^4/\sigma_u^4)$ depends only on the input distribution, and replacing the heavy-tailed input by a Gaussian one removes the kurtosis factor and reduces $M$ to order $mT$.
- The error bound has the same $\sqrt{\log(1/\delta)/N}$ scaling as the sub-Gaussian multi-trajectory baseline, so the cost of dropping light-tailed assumptions is only polynomial in the system dimensions, not exponential in $\log(1/\delta)$.
- Because each rollout starts from zero and rollouts are independent, the result holds without mixing or stability assumptions on $A$; the only system-dependent constant entering through the process-noise term is $\|F\|$.
Reading between the lines
- A direct stress test suggested by the proof is to replace the input distribution by one with finite variance and infinite fourth moment, such as a multivariate $t$ distribution with four degrees of freedom; the theorem's mechanism predicts that the invertibility lemma breaks, so either the error bound degrades or the geometric median still rescues it, and either outcome would settle the paper's op
- The same bucket-and-median architecture could be adapted to the single-trajectory setting by chopping one long rollout into weakly dependent segments, but the temporal correlations would need an explicit decorrelation argument that the paper does not provide.
- The kurtosis ratio $\tilde\sigma_u^4/\sigma_u^4$ entering $M$ is an estimable quantity, so a practitioner could estimate it from input data before collecting outputs and choose the number of rollouts accordingly, making the sample-size prescription data-driven.
- Because the geometric-median lemma tolerates a minority of bad buckets, the estimator is plausibly robust not only to heavy tails but also to a fraction of entirely corrupted rollouts, although the paper does not analyze adversarial corruption.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies non-asymptotic system identification of partially observed linear time-invariant systems from multiple independent rollouts when the process and measurement noises are heavy-tailed and have only finite second moments. The authors propose a bucketed ordinary-least-squares estimator whose outputs are combined via the geometric median with respect to the Frobenius norm, and prove Theorem 1, which states that the Markov parameter estimator satisfies a bound of the form ||Ghat-G|| <= ((sigma_v C1 + sigma_w C2)/sigma_u) sqrt(p log(1/delta)/N) with probability at least 1-delta, provided the number of buckets K is ceil(32 log(1/delta)), each bucket has M = O((mT)^2 sigma_tilde_u^4/sigma_u^4) rollouts, and the input is zero-mean i.i.d. with finite fourth moment. The proof is built on Lemmas 1-3, which use Markov's inequality to control the sample covariance, the process-noise term, and the measurement-noise term per bucket, and Lemma 4, which uses a geometric-median boosting argument and Hoeffding's inequality to convert constant per-bucket failure probabilities into a logarithmic dependence on delta.
Significance. If the main result holds, it is a meaningful advance: it shows that logarithmic dependence on the confidence parameter is achievable for partially observed LTI system identification under noise distributions that are only assumed to have finite second moments, nearly matching the rates previously available under Gaussian or sub-Gaussian assumptions. The algorithm is simple, the proof strategy is largely self-contained, and the paper is unusually transparent about the cost of removing sub-Gaussian assumptions, including the extra dimension factors and the role of the fourth-moment assumption on the input. The explicit discussion of the input kurtosis and the open question about whether the fourth moment is necessary is a strength. However, as detailed below, the proof of the boosting lemma contains a threshold error that is load-bearing for the stated logarithmic-in-delta rate; the central claim appears defensible after a localized correction, but the manuscript in its current form does not establish Theorem 1 as written.
major comments (2)
- [Section 4, Lemma 4] The proof of Lemma 4 defines epsilon = (sqrt(8)/M)(1/sigma_u)(sigma_v C1 + sigma_w C2), but this is not compatible with the per-bucket guarantee (13). Setting q = 1/8 in (13) gives ||Ghat_j - G|| <= 8(sigma_v C1 + sigma_w C2)/(sigma_u sqrt(M)) with probability at least 7/8, so the per-bucket failure probability can only be bounded by 1/8 for thresholds of order 1/sqrt(M). The chosen epsilon is of order 1/M, so the claim E[Z1] <= 1/8 used in the Hoeffding step is not established. Consequently, the final logarithmic-in-delta bound in (8) and (14) does not follow from the written proof, and the final substitution M = N/K cannot produce the stated sqrt(p log(1/delta)/N) rate from an epsilon of order 1/M. This is a load-bearing issue, although it appears repairable by choosing epsilon proportional to (sigma_v C1 + sigma_w C2)/(sigma_u sqrt(M)) and tracking the resulting constants.
- [Section 4, Lemma 1 proof] In the proof of Lemma 1, the displayed equality E[sum_{i != l} (uhat(i))^2 (uhat(l))^2] = ((mT)^2 - mT) sigma_u^4 assumes independence of the coordinates of each input vector, whereas Assumption (4) only specifies the covariance and the marginal fourth moments. The same final bound can be obtained by applying Cauchy-Schwarz to each cross term, so the lemma remains valid after this correction, but the proof as written relies on a stronger assumption than stated.
minor comments (2)
- [Throughout] There are several typographical errors, for example 'we device a novel algorithm' in Section 1 should be 'we devise a novel algorithm'; these should be corrected in revision.
- [Section 4, Lemma 4] The proof of Lemma 4 mixes strict and non-strict inequalities when defining the events S_j and Z_j and when applying Lemma 6; the argument can be made fully rigorous by introducing a small slack in the thresholds and then taking the slack to zero.
Circularity Check
No significant circularity: Theorem 1 is derived from the stated moment assumptions and external robust-statistics lemmas; the only self-citation is an elementary variance identity that is not load-bearing.
full rationale
Theorem 1 is a genuine derivation rather than a disguised input. The per-bucket OLS error bound (13) is obtained from Lemmas 1-3, which use Markov's inequality on the moments specified in (3)-(4); the failure probability is then reduced from constant per-bucket q = 1/8 to delta via Lemma 4, whose proof invokes Lemma 6, a geometric-median robustness property cited from Minsker [9], and Hoeffding's inequality. None of these steps fits a parameter to data: K, M, and N are set a priori from delta and the moment ratios, and the constants C1, C2 in (9) are dimension/system factors, not fitted values. The only self-citation is Lemma 5, taken from the authors' prior work [25]; it is the elementary additivity of the variance statistic for independent random matrices and is used only to evaluate E[||X||_F^2] in the Markov bounds. This lemma is parameter-free, has stated assumptions, and does not presuppose Theorem 1, so under the review rules it constitutes independent support and does not raise the circularity score. The comparison to the sub-Gaussian benchmark [6] is an external benchmark, not an input to the derivation. I find no self-definitional step, no fitted input renamed as a prediction, and no load-bearing self-citation chain.
Assumptions & free parameters
assumptions (6)
- domain assumption Noise sequences {w_t} and {v_t} are zero-mean i.i.d. with finite second moments and isotropic covariances sigma_w^2 I_n and sigma_v^2 I_p (Assumption 1).
- domain assumption System starts from zero initial state x_0 = 0 (Assumption 2).
- domain assumption Input sequence {u_t} is zero-mean i.i.d., independent of the noise, with covariance sigma_u^2 I_m and finite fourth moment with E[(u_t(i))^4] = sigma_tilde_u^4 (Eq. 4).
- domain assumption The M rollouts within a bucket and the K buckets are independent (data collection in Section 2.1).
- standard math Geometric median property (Lemma 6) from Minsker [9].
- standard math Variance decomposition for independent matrices (Lemma 5, from the authors' prior work [25]).
Cite this review
Pith. "Pith review of Boosting-Enabled Robust System Identification of Partially Observed LTI Systems Under Heavy-Tailed Noise." pith.science (2026). https://pith.science/paper/K4W3JIPT
@misc{pith2026250418444,
author = {Pith},
title = {Pith review of: Boosting-Enabled Robust System Identification of Partially Observed LTI Systems Under Heavy-Tailed Noise},
year = {2026},
howpublished = {\url{https://pith.science/paper/K4W3JIPT}},
note = {Machine review of arXiv:2504.18444}
}
read the original abstract
We consider the problem of system identification of partially observed linear time-invariant (LTI) systems. Given input-output data, we provide non-asymptotic guarantees for identifying the system parameters under general heavy-tailed noise processes. Unlike previous works that assume Gaussian or sub-Gaussian noise, we consider significantly broader noise distributions that are required to admit only up to the second moment. For this setting, we leverage tools from robust statistics to propose a novel system identification algorithm that exploits the idea of boosting. Despite the much weaker noise assumptions, we show that our proposed algorithm achieves sample complexity bounds that nearly match those derived under sub-Gaussian noise. In particular, we establish that our bounds retain a logarithmic dependence on the prescribed failure probability. Interestingly, we show that such bounds can be achieved by requiring just a finite fourth moment on the excitatory input process.
Reference graph
Works this paper leans on
-
[1]
Tze Leung Lai and Ching Zong Wei. Asymptotic properties o f general autoregressive models and strong consistency of least-squares estimates of their parameters. Journal of multivariate analysis, 13(1):1–23, 1983
work page 1983
-
[2]
Non-asymptotic analysis of robust control from coarse-grained identification
Stephen Tu, Ross Boczar, Andrew Packard, and Benjamin Rech t. Non-asymptotic analysis of robust control from coarse-grained identification. arXiv preprint arXiv:1707.04791 , 2017
arXiv 2017
-
[3]
Learning without mixing: Towards a sharp analysis of linear system id entification
Max Simchowitz, Horia Mania, Stephen Tu, Michael I Jorda n, and Benjamin Recht. Learning without mixing: Towards a sharp analysis of linear system id entification. In Conference On Learning Theory, pages 439–473. PMLR, 2018
work page 2018
-
[4]
Near optimal finite t ime identification of arbitrary linear dynamical systems
Tuhin Sarkar and Alexander Rakhlin. Near optimal finite t ime identification of arbitrary linear dynamical systems. In International Conference on Machine Learning , pages 5610–5618. PMLR, 2019
work page 2019
-
[5]
Statistical learning theory for control: A finite-sample perspective
Anastasios Tsiamis, Ingvar Ziemann, Nikolai Matni, and George J Pappas. Statistical learning theory for control: A finite-sample perspective. IEEE Control Systems Magazine , 43(6):67–97, 2023
2023
-
[6]
Non-asymptotic identification of li near dynamical systems using mul- tiple trajectories
Yang Zheng and Na Li. Non-asymptotic identification of li near dynamical systems using mul- tiple trajectories. IEEE Control Systems Letters , 5(5):1693–1698, 2020
2020
-
[7]
Effective construction of linear state-varia ble models from input/output functions
RE Kalman. Effective construction of linear state-varia ble models from input/output functions. at-Automatisierungstechnik, 14(1-12):545–548, 1966
work page 1966
-
[8]
Non-asymptotic identifica tion of lti systems from a single trajectory
Samet Oymak and Necmiye Ozay. Non-asymptotic identifica tion of lti systems from a single trajectory. In 2019 American control conference (ACC) , pages 5655–5661. IEEE, 2019
work page 2019
Show all 28 references
-
[9]
Geometric median and robust estimat ion in banach spaces
Stanislav Minsker. Geometric median and robust estimat ion in banach spaces. 2015
2015
-
[10]
High-dimensional probability: An introduction with appli cations in data science, volume 47
Roman Vershynin. High-dimensional probability: An introduction with appli cations in data science, volume 47. Cambridge university press, 2018
2018
-
[11]
Robust multivariat e mean estimation: the optimality of trimmed mean
Gabor Lugosi and Shahar Mendelson. Robust multivariat e mean estimation: the optimality of trimmed mean. 2021
2021
-
[12]
System identification
Lennart Ljung. System identification. In Signal analysis and prediction , pages 163–173. Springer, 1998
1998
-
[13]
On the sam- ple complexity of the linear quadratic regulator
Sarah Dean, Horia Mania, Nikolai Matni, Benjamin Recht, and Stephen Tu. On the sam- ple complexity of the linear quadratic regulator. Foundations of Computational Mathematics , 20(4):633–679, 2020
2020
-
[14]
Finite sample sy stem identification: Optimal rates and the role of regularization
Yue Sun, Samet Oymak, and Maryam Fazel. Finite sample sy stem identification: Optimal rates and the role of regularization. In Learning for dynamics and control , pages 16–25. PMLR, 2020
2020
-
[15]
Linear system identification under multiplicative noise from multiple tr ajectory data
Yu Xing, Ben Gravell, Xingkang He, Karl Henrik Johansson , and Tyler Summers. Linear system identification under multiplicative noise from multiple tr ajectory data. In 2020 American Control Conference (ACC) , pages 5157–5261. IEEE, 2020
2020
-
[16]
Learning th e dynamics of autonomous linear systems from multiple trajectories
Lei Xin, George Chiu, and Shreyas Sundaram. Learning th e dynamics of autonomous linear systems from multiple trajectories. In 2022 American Control Conference (ACC) , pages 3955–
2022
-
[17]
Lea rning from many trajectories
Stephen Tu, Roy Frostig, and Mahdi Soltanolkotabi. Lea rning from many trajectories. Journal of Machine Learning Research , 25(216):1–109, 2024
2024
-
[18]
Concentration bounds for single param eter adaptive control
Anders Rantzer. Concentration bounds for single param eter adaptive control. In 2018 Annual American Control Conference (ACC) , pages 1862–1866. IEEE, 2018
2018
-
[19]
Finite sample a nalysis of stochastic system iden- tification
Anastasios Tsiamis and George J Pappas. Finite sample a nalysis of stochastic system iden- tification. In 2019 IEEE 58th Conference on Decision and Control (CDC) , pages 3648–3654. IEEE, 2019
2019
-
[20]
Finite-time ide ntification of linear systems: Fundamental limits and optimal algorithms
Yassir Jedra and Alexandre Proutiere. Finite-time ide ntification of linear systems: Fundamental limits and optimal algorithms. IEEE Transactions on Automatic Control , 68(5):2805–2820, 2022
2022
-
[21]
Lea rning nonlinear dynamical systems from a single trajectory
Dylan Foster, Tuhin Sarkar, and Alexander Rakhlin. Lea rning nonlinear dynamical systems from a single trajectory. In Learning for Dynamics and Control , pages 851–861. PMLR, 2020
2020
-
[22]
S ingle trajectory nonparametric learning of nonlinear dynamics
Ingvar M Ziemann, Henrik Sandberg, and Nikolai Matni. S ingle trajectory nonparametric learning of nonlinear dynamics. In conference on Learning Theory , pages 3333–3364. PMLR, 2022
2022
-
[23]
Finite time identification in unstable linear systems
Mohamad Kazem Shirani Faradonbeh, Ambuj Tewari, and Ge orge Michailidis. Finite time identification in unstable linear systems. Automatica, 96:342–353, 2018
2018
-
[24]
Sub-weibull distribu- tions: Generalizing sub-gaussian and sub-exponential pro perties to heavier tailed distributions
Mariia Vladimirova, Stéphane Girard, Hien Nguyen, and Julyan Arbel. Sub-weibull distribu- tions: Generalizing sub-gaussian and sub-exponential pro perties to heavier tailed distributions. Stat, 9(1):e318, 2020
2020
-
[25]
Outlier-robust linea r system identification under heavy-tailed noise
Vinay Kanakeri and Aritra Mitra. Outlier-robust linea r system identification under heavy-tailed noise. arXiv preprint arXiv:2501.00421 , 2024
2024 arXiv
-
[26]
Linear systems can be hard to learn
Anastasios Tsiamis and George J Pappas. Linear systems can be hard to learn. In 2021 60th IEEE Conference on Decision and Control (CDC) , pages 2903–2910. IEEE, 2021
2021
-
[27]
Matrix analysis
Roger A Horn and Charles R Johnson. Matrix analysis . Cambridge university press, 2012. A Preliminary results In the proofs of Lemmas 1, 2, and 3, we bound the Frobenius norm of random matrices. In this regard, the following result defines a variance statistic, v ar(·), and sho...
2012
-
[28]
Applying an union bound over the T blocks in VjU ⊤ j , with probability at least 1 − q/3, ‖Xl‖2 F ≤ 3(1/q)T 2σ2 vσ2 uM pm, for all l ∈ { 0, 1,
Setting the R.H.S = q/(3T ) in ( 19), we have with probability at least 1 − q/(3T ), ‖Xl‖2 F ≤ 3(1/q)T 2σ2 vσ2 uM pm. Applying an union bound over the T blocks in VjU ⊤ j , with probability at least 1 − q/3, ‖Xl‖2 F ≤ 3(1/q)T 2σ2 vσ2 uM pm, for all l ∈ { 0, 1, . . . , T − 1}. ...
Reviewed August 16, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.