{"id":"b9f42e7f-b336-4019-bb0e-8fd670c4463e","arxiv_id":"2501.00421","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A median-of-bucket-OLS algorithm recovers sub-Gaussian-style system identification rates under heavy-tailed noise with only finite fourth moment, and tolerates a small fraction of adversarially corrupted trajectories.","lead":"This paper designs a robust estimator that learns the update matrix of a linear dynamical system from many short trajectories even when the noise has only a finite fourth moment, much heavier than Gaussian. It shows the error still shrinks at nearly the same rate as in the ideal Gaussian case, up to a factor depending on the state dimension and the noise kurtosis.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorems 1–2 appear sound, but Theorem 3's adversarial guarantee is not proven: the Hoeffding step in Appendix D assumes independence of Z_j W_j under an adversary that may choose corruptions adaptively.","rationale":"The reader's stated weakest assumption is the zero-initial-condition/isotropic-noise premise. That is a modeling condition, and the paper explicitly adopts it, so it is less load-bearing than the adversarial independence gap. However, the reader's rationale independently flags the same Theorem 3 issue, so there is partial agreement. I examined Theorems 1 and 2 for a possible flaw in the derivation of the vector denominator bound (Lemma 15), the trace inequalities, and the geometric-median boosting step; I did not find a fatal error. The main safety issue is that the adversarial proof applies Hoeffding to random variables whose independence is not guaranteed under the strong-contamination model. This is a concrete proof gap rather than an internal inconsistency of the heavy-tailed result, and it is addressable by either restricting the adversary to be oblivious or supplying a dependence-robust argument. Since the reader's conditional verdict already reflects this level of concern, I recommend no change to the verdict.","tokens_in":25321,"tokens_out":17250,"duration_ms":178394,"concrete_test":"Analytical check: re-derive eq. (31) under the minimax strong-contamination model by conditioning on the adversary's corruption pattern W. Show whether sup_W P(sum_j Z_j W_j > K/4 - eta N | W = w) is bounded by exp(-2K(1/8 - eta N/K)^2), or construct an adversary (e.g., W_j = 1 exactly on the buckets whose OLS estimates are closest to A) for which the Hoeffding bound fails. If the conditioning argument succeeds, Theorem 3 stands; if not, Theorem 3 should be stated only for an oblivious adversary whose corruption set is independent of the data.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The strongest claimed result, Theorem 2, is internally consistent: the bucket-wise OLS bounds via fourth-moment Markov/Chebyshev arguments and the geometric-median boosting step hold together, and the zero-initial-condition/isotropic-noise assumptions are stated explicitly in the problem formulation. The load-bearing vulnerability is Theorem 3 (Appendix D). Under the strong-contamination model, the adversary may inspect the data before choosing which eta-N trajectories to corrupt, so the corruption indicators W_j are random and dependent on the clean data and on one another. The proof defines Z_j as the bad event for bucket j and W_j as the event that bucket j is uncorrupted, then in eq. (31) centers Z_j W_j by E[Z_j W_j] and applies Hoeffding. Hoeffding requires independence of the summands; the bound E[Z_j W_j] <= p is only a marginal bound. If W_j is chosen adversarially after observing the realized buckets, the conditional distribution of Z_j on uncorrupted buckets can be biased, and the centered sum need not concentrate at the claimed rate. Thus the displayed probability bound P(1/K sum_j (Z_j W_j - E[Z_j W_j]) >= 1/8 - eta N/K) <= exp(-2K(1/8 - eta N/K)^2) is not justified. This does not invalidate Theorems 1-2, but it leaves the abstract's 'arbitrarily corrupt' robustness claim unproven as written.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies finite-sample identification of the transition matrix A in the LTI system x_{t+1} = A x_t + w_t from N independent length-T trajectories, under a noise model (Eq. (2)) that assumes only zero mean, covariance σ²I, and finite fourth moments E[w_t(i)^4] = σ̃⁴. The proposed algorithm Robust-SysID partitions the trajectories into K buckets, forms an OLS estimate from each bucket using the last two states, and aggregates the bucket estimates with a Frobenius-norm geometric median. Theorem 1 gives a scalar error bound matching the sub-Gaussian OLS rate up to constants, with a kurtosis-dependent number of trajectories per bucket. Theorem 2 gives a vector bound ||Â − A|| ≤ C d^{3/2} sqrt(log(1/δ)/(N λ_min(G_T))) with K = ceil(c1 log(1/δ)) and M ≥ c2 d² C_A C_w. Theorem 3 claims an additive O(√η) error under an adversary that can corrupt an η fraction of trajectories. The proofs combine Chebyshev/Markov bounds on the per-bucket OLS numerator and denominator, followed by Hoeffding-based boosting through the median.","tokens_in":25553,"tokens_out":6520,"duration_ms":68639,"significance":"If Theorems 1 and 2 hold, the paper makes a solid contribution: it provides the first PAC-style system identification guarantees under a noise model that requires only a finite fourth moment, and it nearly matches the sub-Gaussian benchmark of Dean et al. [7], with only an extra O(d) factor in the vector setting. The scalar theorem, in particular, is clean and fully derived, and the explicit dependence on the kurtosis σ̃⁴/σ⁴ is a meaningful and informative feature. The proof strategy—combining weak per-bucket OLS estimators with geometric-median boosting—is natural and well executed for the clean-data setting. However, the adversarial extension in Theorem 3 is not proven as written: the Hoeffding argument in Appendix D requires an independence that the stated strong-contamination model does not provide. This gap weakens the advertised adversarial robustness claim, although it does not undermine the heavy-tailed identification results that form the paper's core.","major_comments":[{"comment":"The Hoeffding step in the proof of Theorem 3 is not justified under the stated strong-contamination model. The proof introduces W_j as the indicator that bucket j has no corruptions, and then centers Z_j W_j by E[Z_j W_j] and applies Hoeffding. But if the adversary may choose the corrupted trajectories after seeing the realized data—the standard strong-contamination model—then W_j is a random variable depending on the clean data and on the other W_j's. Consequently the summands Z_j W_j − E[Z_j W_j] are not independent, and Hoeffding's inequality cannot be applied as written. Moreover, the bound E[Z_j W_j] ≤ p derived at the end of Appendix D uses (29), which is an unconditional guarantee for a clean bucket; conditioning on W_j = 1 can select unfavorable realizations of the clean data, so P({||Â_j − A|| ≥ ε} ∩ {W_j = 1}) need not be ≤ p. Thus the displayed probability bound leading to the statement of Theorem 3 is not established. This is a load-bearing gap in the adversarial contribution, although it does not invalidate Theorems 1 and 2.","section":"Appendix D, Eq. (31)"},{"comment":"The adversarial model is underspecified in a way that matters. The text says an adversary can 'arbitrarily corrupt a small fraction η of the trajectories' and cites the strong-contamination model of [23], which normally permits the adversary to depend on the data. The proof, however, requires W_j to be independent of the clean data and of each other—essentially an oblivious adversary. The authors should either provide a proof for the adaptive strong-contamination model or explicitly restrict Theorem 3 to an oblivious adversary and adjust the abstract and Section 6 accordingly. As written, the claimed adversarial guarantee is stronger than what the proof supports.","section":"Section 6 and Appendix D"}],"minor_comments":[{"comment":"The condition M ≥ c2(σ̃²/σ²) should read M ≥ c2(σ̃⁴/σ⁴), matching Lemma 2 and Theorem 1; the displayed σ̃²/σ² is a typo.","section":"Appendix B, final paragraph"},{"comment":"In the displayed Hoeffding expression, the centered sum is written with E[Y_1] but the surrounding text and the subsequent bound use E[Z_1]; this inconsistency is a typo and should be corrected.","section":"Lemma 16, proof"},{"comment":"The requirement K ≥ ⌈c2 log(1/δ) + c3 ηN⌉ is stated with a real argument inside a ceiling, and the feasibility N = MK together with M ≥ c4 d² C_A C_w and the upper bound on η should be stated explicitly; this is a clarity issue about the parameter ranges for which the theorem applies.","section":"Theorem 3, statement"}],"recommendation":"major_revision","confidential_remarks":"The core heavy-tailed contribution—Theorems 1 and 2—appears sound and well argued. The main risk is the overclaimed adversarial guarantee in Theorem 3, whose proof has a genuine independence gap under the stated adaptive contamination model. If the authors cannot repair the proof, they should weaken or remove the adversarial claim from the abstract and contributions, or restrict it to an oblivious adversary. Given the value of the clean-data results, I do not see this as a rejection, but the paper should not be accepted while Theorem 3 is stated in its current form."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: Theorems 1 and 2 are the real content, and they look right. Theorem 3, the adversarial robustness extension, has a gap that needs fixing before the abstract's \"arbitrarily corrupt\" claim can be taken at face value.\n\nWhat's genuinely new: the paper gives the first finite-sample PAC bounds for multi-trajectory LTI system identification under noise with only a finite fourth moment. The scalar case matches the sub-Gaussian rate exactly, and the vector case recovers it up to an O(d) factor. That is a real improvement over sub-Gaussian or sub-Weibull assumptions in prior work. The analysis is refreshingly elementary: Chebyshev on each bucket, a fourth-moment control of the covariance denominator, and a geometric-median boost. I checked the central fourth-moment trace bounds in Lemma 15 and they hold up; the whitening step is legitimate under the stated assumptions. The kurtosis-dependent trajectory requirement is an interesting and honest limitation, not hidden.\n\nWhere it gets soft: the stress-test note is correct. In Appendix D, the proof of Theorem 3 applies Hoeffding to Z_j W_j, where W_j indicates whether bucket j is uncorrupted. Under the strong-contamination model, the adversary can choose corruptions after seeing the data, so W_j is not independent of the bucket contents. The marginal bound E[Z_j W_j] ≤ p is derived by conditioning on W_j=1 and invoking the clean-bucket guarantee, but if the adversary corrupts buckets that look bad, that conditional probability can exceed p. The centered sum need not concentrate at the claimed rate, and the displayed exponent is not justified. This is a load-bearing gap in Theorem 3, not a typo. It does not damage Theorems 1–2.\n\nOne smaller caveat: the model assumes isotropic noise covariance and zero initial condition. Those are stated explicitly in Section 2, so I would not call them hidden assumptions, but the abstract oversells the generality by not mentioning the isotropic second-moment requirement. That is a presentational fix, not a mathematical one.\n\nVerdict: send to peer review. The heavy-tailed results deserve referee time and the adversarial claim can be repaired or appropriately weakened. A serious referee should focus on Theorem 3 and the independence issue there. I would cite this paper for Theorems 1–2.","headline":"Theorems 1–2 are a genuine and likely correct advance for heavy-tailed sys-ID; Theorem 3's adversarial guarantee is not proven as written, so the paper needs a revision before the robustness claim can stand.","tokens_in":26132,"tokens_out":1519,"would_cite":true,"duration_ms":17206,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["93E12","62F35","62H12"],"pacs":[],"model":"deepseek-v4-flash","headline":"Even when a linear system's process noise has only a finite fourth moment and arbitrarily heavy tails, a bucketed least-squares estimate fused by a geometric median recovers nearly the same sample-complexity bound as Gaussian noise, with…","keywords":["heavy-tailed noise","linear system identification","finite fourth moment","geometric median","median of means","sample complexity","PAC bounds","adversarial corruption"],"falsifier":"Simulate the scalar system with a zero-mean noise distribution that has a finite fourth moment but a deliberately large kurtosis (for example, a $t$-distribution with five degrees of freedom, scaled to variance $\\sigma^2$), set $K=\\lceil c_1\\log(1/\\delta)\\rceil$ and $M=c_2\\tilde\\sigma^4/\\sigma^4$, and check empirically whether the failure probability of $|\\hat a-a|>C\\sqrt{\\log(1/\\delta)/(N g_T)}$ stays below $\\delta$; a systematic violation would refute the claimed bound.","tokens_in":1933,"feed_emoji":"⚙️","tokens_out":2135,"duration_ms":71512,"temperature":0.7,"pith_summary":"This paper asks whether the transition matrix of a linear time-invariant system can be learned when the process noise is heavy-tailed, with only a finite fourth moment and no sub-Gaussian tails. The authors propose a robust estimator, Robust-SysID, that splits the collected trajectories into buckets, computes an ordinary least-squares estimate in each bucket, and then fuses the bucket estimates with a geometric median. They prove that this estimator recovers the same logarithmic dependence on the failure probability as the sub-Gaussian OLS benchmark: exactly in the scalar case, and up to an extra factor of $d^{3/2}$ in the vector case. The number of trajectories must grow with the kurtosis of the noise distribution, which quantifies the price of heavy tails. The same algorithm is shown to tolerate adversarial corruption of a small fraction of trajectories.","feed_headline":"System ID matches Gaussian rates under heavy-tailed noise","feed_subtitle":"A bucketed least-squares plus geometric-median estimator needs only a finite fourth moment.","key_machinery":"The load-bearing mechanism is the combination of bucketing with the geometric median: within each bucket a plain least-squares fit is only weakly concentrated (failure probability decays polynomially), but the median across $K=\\lceil c_1\\log(1/\\delta)\\rceil$ independent buckets boosts the failure probability to $\\delta$ via Hoeffding's inequality. The vector analysis rests on a fourth-moment identity for $\\mathbb{E}[(x_T x_T^\\top)^2]$ (Lemma 5) that lets one bound the trace of the whitened residual covariance, yielding the lower bound $\\lambda_{\\min}(\\sum_{i\\in B_j} z_T^{(i)}(z_T^{(i)})^\\top)\\ge M/2$ once each bucket holds at least $M\\ge c d^2 C_A C_w$ trajectories. This denominator bound, together with a Frobenius-norm Markov bound on the numerator $\\sum_{i\\in B_j} w_T^{(i)}(z_T^{(i)})^\\top$, is what replaces the sub-Gaussian concentration arguments of prior work.","core_discovery":"The central claim is that a median-of-means style construction eliminates the need for light-tailed noise in finite-sample linear system identification. Under the noise model $\\mathbb{E}[w_t w_t^\\top]=\\sigma^2 I$ and $\\mathbb{E}[(w_t(i))^4]=\\tilde\\sigma^4$, Robust-SysID achieves, with probability at least $1-\\delta$, the bound $\\|\\hat{A}-A\\| \\le C d^{3/2}\\sqrt{\\log(1/\\delta)/(N\\lambda_{\\min}(G_T))}$ when each bucket contains $M\\ge c_2 d^2 C_A C_w$ trajectories and the number of buckets is $K=\\lceil c_1\\log(1/\\delta)\\rceil$. In the scalar case the bound becomes $|\\hat a-a|\\le C\\sqrt{\\log(1/\\delta)/(N g_T)}$, identical in form to the sub-Gaussian OLS rate. The proof avoids all sub-Gaussian concentration arguments, relying instead on Chebyshev and Markov inequalities together with a fourth-moment computation that controls the smallest eigenvalue of the whitened empirical covariance. A corollary is that when an adversary corrupts an $\\eta$ fraction of trajectories, the same estimator's error degrades only by an additive $O(\\sqrt{\\eta})$ term.","pith_inferences":["The bucketed geometric-median construction is a generic booster: any least-squares type estimator whose error is bounded in probability with polynomial failure rate can be promoted to logarithmic failure probability, so the same recipe should apply to other identification and control tasks such as estimating the $B$ matrix or the Riccati solution.","The extra $d^{3/2}$ factor appears tied to the use of the Frobenius norm in the geometric-median step and to Markov-type concentration; if a spectral-norm geometric median with comparable guarantees existed, the vector bound might close to the sub-Gaussian rate, a gap the authors leave open.","A natural testable extension is whether a trimmed-mean or median-of-means variant that truncates by coordinate could reduce the kurtosis dependence below linear, since the paper only shows the linear dependence appears in its analysis, not that it is fundamental."],"forward_implications":["Under noise with only a finite fourth moment, the failure probability enters the estimator's error bound logarithmically, so high-confidence guarantees are not much costlier than under Gaussian noise.","In the scalar case the robust estimator matches the sub-Gaussian OLS rate exactly; in the vector case it matches up to a factor $d^{3/2}$ in the error bound and $O(d^2)$ in the required number of trajectories.","The number of trajectories needed per bucket grows linearly with the kurtosis $\\tilde\\sigma^4/\\sigma^4$, making the cost of heavy tails explicit.","With adversarial corruption of up to an $\\eta$ fraction of trajectories, the same estimator still delivers the heavy-tailed bound plus an additive $O(\\sqrt{\\eta/\\lambda_{\\min}(G_T)})$ error.","Under a controllability assumption the technique extends to systems with inputs, where the input matrix is also unknown."],"supporting_citations":[{"why":"Identifies the open question of system identification under heavy-tailed noise and supplies the sub-Gaussian benchmark.","marker":"[2]"},{"why":"Provides the multi-trajectory sub-Gaussian OLS bound and the whitening technique that the vector proof adapts.","marker":"[7]"},{"why":"Prior weaker-noise result requiring sub-Weibull tails, the main comparison showing the fourth-moment assumption is a genuine relaxation.","marker":"[20]"},{"why":"Shows the failure probability dependence of OLS degrades under heavy tails, motivating the need for a new estimator.","marker":"[21]"},{"why":"Supplies the geometric median and its concentration property (Lemma 10) used in the boosting step.","marker":"[22]"},{"why":"Defines the strong-contamination model and the $O(\\sqrt{\\eta})$ benchmark that Theorem 3 matches.","marker":"[23]"},{"why":"Supplies the matrix Markov inequality used as an alternative tool in the numerator and denominator bounds.","marker":"[26]"},{"why":"The heavy-tailed spectral-norm concentration result discussed as a possible route to removing one factor of $\\sqrt d$.","marker":"[27]"}],"fun_headline_variants":["System ID robust to heavy tails, matches sub-Gaussian rates","Only finite fourth moment needed for optimal system ID rates","Robust estimator for LTI systems tames heavy-tailed noise","Adversary-proof system ID with no sub-Gaussian assumptions","Kurtosis determines trajectory count for system ID"],"cache_read_input_tokens":28160,"weakest_assumption_plain":"The entire proof requires the noise to be zero-mean with isotropic covariance ($\\mathbb{E}[w_t w_t^\\top]=\\sigma^2 I$), a finite fourth moment per coordinate, and every trajectory to start from the zero state, so that the state covariance is exactly $\\sigma^2 G_T$ and the whitening step is valid.","fun_headline_variants_meta":{"raw":{"variants":["System ID robust to heavy tails, matches sub-Gaussian rates","Only finite fourth moment needed for optimal system ID rates","Robust estimator for LTI systems tames heavy-tailed noise","Adversary-proof system ID with no sub-Gaussian assumptions","Kurtosis determines trajectory count for system ID"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000729,"raw_usage":{"total_tokens":3317,"prompt_tokens":1051,"completion_tokens":2266,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":667,"completion_tokens_details":{"reasoning_tokens":2185}},"tokens_in":667,"tokens_out":2266,"duration_ms":18153,"temperature":1.0,"reasoning_tokens":2185,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T22:54:01.592121+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Simulate the scalar system with a zero-mean noise distribution that has a finite fourth moment but a deliberately large kurtosis (for example, a $t$-distribution with five degrees of freedom, scaled to variance $\\sigma^2$), set $K=\\lceil c_1\\log(1/\\delta)\\rceil$ and $M=c_2\\tilde\\sigma^4/\\sigma^4$, and check empirically whether the failure probability of $|\\hat a-a|>C\\sqrt{\\log(1/\\delta)/(N g_T)}$ stays below $\\delta$; a systematic violation would refute the claimed bound.","supporting_citations":[{"cited_title":"Statistical learning theory for control: A finite-sample perspective","cited_arxiv_id":null,"evidence_quote":"Identifies the open question of system identification under heavy-tailed noise and supplies the sub-Gaussian benchmark."},{"cited_title":"On the sam- ple complexity of the linear quadratic regulator","cited_arxiv_id":null,"evidence_quote":"Provides the multi-trajectory sub-Gaussian OLS bound and the whitening technique that the vector proof adapts."},{"cited_title":"Finite time identification in unstable linear systems","cited_arxiv_id":null,"evidence_quote":"Prior weaker-noise result requiring sub-Weibull tails, the main comparison showing the fourth-moment assumption is a genuine relaxation."},{"cited_title":"The lower tail of random qu adratic forms with applications to ordinary least squares","cited_arxiv_id":null,"evidence_quote":"Shows the failure probability dependence of OLS degrades under heavy tails, motivating the need for a new estimator."},{"cited_title":"Geometric median and robust estima tion in banach spaces","cited_arxiv_id":null,"evidence_quote":"Supplies the geometric median and its concentration property (Lemma 10) used in the boosting step."},{"cited_title":"Robust multivariat e mean estimation: the optimality of trimmed mean","cited_arxiv_id":null,"evidence_quote":"Defines the strong-contamination model and the $O(\\sqrt{\\eta})$ benchmark that Theorem 3 matches."},{"cited_title":"Ahlswede and A","cited_arxiv_id":null,"evidence_quote":"Supplies the matrix Markov inequality used as an alternative tool in the numerator and denominator bounds."}],"review_version":1}