- Rating
- 3
- Confidence
- 1
- Informativeness
- 2
- Presentation
- 1
- Soundness
- 2
Read review
Paper summary
This paper studies learnability from a single time-series for a certain class of selective SSMs. The authors extend the classical Ho–Kalman realization algorithm to linear parameter-varying state-space models (LPV‑SSA). Under a set of stability, minimality and weak-dependence assumptions, they derive finite-sample PAC bounds for parameter estimation from a single noisy time series. The authors claim that the novelty of their work lies in the following aspects: (1) providing parameter estimation error bounds for a more general class of state-space models (SSMs); (2) learning from a single trajectory; (3) allowing non-i.i.d. inputs; and (4) not requiring the system to be at rest when the training data are collected.
Critical strengths
- This work bounds the parameter estimation error of a more general class of SSMs using only a single trajectory.
Critical weaknesses
-
The authors should clarify which aspects of the proposed analysis are fundamentally new, beyond extending the system class and relaxing assumptions on the input and initial conditions.
-
The paper relies on the strong assumption that the Gram matrix is known rather than estimated purely from observed data. This assumption substantially limits the practical value of the proposed algorithm and weakens the completeness of the theoretical framework, since system identification theory typically aims to recover system parameters purely from observed input–output data.
-
There are no synthetic numerical experiments to empirically validate the theoretical results. It would be helpful to simulate trajectories from an LPV‑SSA, run the extended Ho–Kalman algorithm, and verify whether the empirical parameter estimation error scaling matches the derived bound.
Questions for authors
See Weaknesses.
6 comments
Response to Reviewer jUen
[Comment 2/2]
3. Numerical experiments. We extend the revised version of the paper with two synthetic examples to illustrate the main theorem. First, we consider a scalar-state LPV system as the true system and plot both the estimation error of the Ho-Kalman algorithm as a function of the number of time steps, and the bounding term of Theorem 5.1. Figure 1 in the revised manuscript shows that there exist sample sizes (time steps), such that the bounding term at is smaller than the estimation error at , which means that there exists at least one scenario (even though it is a toy example) where the bound is non-vacuous.
Our second synthetic example contains 3 instances of a SISO (single-input single-output) LPV system with 4 dimensional states, with degrees of stability (). In this case we plot each pair of estimation error and bounding term. It can be seen that the bound scales with the stability in a manner similar to that of the actual estimation error, which supports the intuition that stability is a key property when learning state-space models.
We agree with the reviewer that empirical investigation of how the estimation error and the bound scale with changes in system properties other than stability would be beneficial for the paper. On the other hand, the paper's contribution is theoretical, the most important messages are the formulation of selective SSMs as LPV systems, the theoretical bound on the estimation error and the resulting corollary on PAC-learnability, therefore we leave the comprehensive experimental investigation for future work. Nevertheless, we are doing everything we can to add some more experiments by the end of the rebuttal period.
We thank again the reviewer for their hard work and are happy to clarify any detail regarding our response and answer any further question.
[EDIT: the experiments are described in Appendix H of the most recent revision]
2nd Response to Reviewer jUen
In addition to our previous answer, we added a new interim revision (we are still working on the restructure around the informal theorem as per our first response to Reviewer nYac) in which we added a new synthetic experiment for further insights on future applicability of our result.
We consider a nonlinear, small LPV system and 24 different row selections for the Hankel matrix (as described in Section 3 of our paper). We empirically estimate from our bound (the term relevant to the Hankel matrix) from the data trajectory and sort the estimates from smallest to highest. We expect that the smaller this bounding term is, the smaller the estimation error will be when the corresponding Hankel matrix is used by the learning algorithm, and this is exactly what we measure, as can be seen in Figure 3 in the revised Appendix H [in earlier revisions it was Appendix F].
This is an example of practical applicabilty of our bound: without the actual learning, we computed statistics of the data (our bounding term) that foretold which Hankel selection performs the best. We emphasize that this is just one aspect of the bound, all other parameters were fixed during this experiment. The comprehensive empirical investigation on how to use all the bounding terms together to predict the learning performance requires significant error and future work. Nevertheless we hope this small example is insightful enough to justify future applicability and usefulness to the ML community.
Response to Reviewer jUen
[Comment 2/1]
We thank the reviewer for their constructive comments. We uploaded a revised version of the manuscript, modifications of the text are in color blue. All references, equation numbers, chapters, sections, etc. refer to the revised manuscript. Most of the revision is added to the appendix, however we are planning at least one more revision before the rebuttal period ends, to which we sometimes refer in our answers.
We address each weakness point and author question below in order.
Critical Weaknesses
1. Fundamentally new aspects of the analysis (excluding system class and assumption relaxations. The most important points from the theoretical analysis:
a) The correspondence between general selective SSMs and LPV systems (including practical Mamba block approximations, see the revised Appendix G [in earlier revisions it was Appendix E] for more details). This allows applying realization theory and system identification results to selective SSMs.
b) In the proof we exploit class-S properties of the data generator, and the stability of the LPV system to obtain a CBS (Causal Bernoulli Shift) representation of the output and the scheduling-weighted input regressor trajectories. In particular, we show that the product of two jointly generated (by the same innovation) CBS processes is also CBS, and we apply this to the output and input regressor trajectories.
Racz et al. (2025a) and Eringis et al. apply similar arguments. However, in this paper the joint moment term contains an additional residual, Equation (46) defines the tail moment BL=E[RL[k]ZL[k]T], where RL[k] is the omitted output tail defined in equation (34). Lemma D.8, equation (49), shows that ΛLGL−1−ΘL=BLGL−1. This equation appears in Racz et al. (2025a) (Lemma II.1, eq (3)) without the bias term BLGL−1, therefore their argument cannot be applied to the setting in the current paper without carefully controlling this bias term which we do in the proof.
c) In the proof we analyze how the multiplication by GL−1 influences the sampling error Λ^L,N−ΛL and the truncation residual BL. Increasing L reduces our bound on the truncation bias (eq (48)), but increases our bound on the sampling error (eq (53)). Our analysis controls both effects via LN in equation (22). As a result, equation (21) explicitly connects the convergence rate of the algorithm to the stability of the system and the growth of ∥∥GL−1∥∥ with L.
Cox et al. (2018), Cox and Toth (2021) partially discuss this tradeoff, however our analysis gives an explicit finite-sample bound, which eventually allows us to derive the parameter-estimation error bound, which does not seem to follow from the results of Cox without our addition to the proof.
Furthermore, we respectfully emphasize that relaxing assumptions and extending results to a broader model class is often highly nontrivial and difficult to do. For example, our data related assumptions are much weaker than the usual i.i.d. assumptions, while extending similar results from linear or even switched systems to LPV systems required a lot of effort in the proof.
We are also happy to include a suitable form of this response in the next revised paper (main text or appendix depending on what the page limit allows).
2. Known population Gram matrix. We agree that our original presentation did not adequately address this concern, however we argue that this assumption is not as strong as it seems at first. Namely, access to the population Gram matrix was assumed mainly for the sake of easier technical analysis. In practice, GL is usually estimated from the observed data trajectory as an average of empirical scheduling-weighted input regressors, which converges to GL as the number of time steps grows. We add a new section in the appendix where we show how to extend our analysis and Theorem 5.1 to the algorithm which takes the empirical Gram matrix GL,N instead of GL. The extension does not require any new significant assumptions or technical tools. Roughly speaking we show that as long as $\widehat G $ is a good enough approximation of GL (for which we give a sufficient condition, namely a lower bound on N), Theorem 5.1 holds with a similar asymptotic scaling and slightly different constants. See Appendix E [in eariler revisions it was Appendix C] in the revised version for more details. We also slightly revise the main text and refer the reader to the appendix regarding this detail.
[EDIT: all equation numbers are updated to match the most recent revision]