acceptodds
Under review as a conference paper at ICLR 2027

PAC Learnability of Stable Selective State-Space Models from a Single Time Series

Abstract

Selective State-Space Models (SSMs) are dynamical systems where the state-transition, input and readout maps may depend on the current input. This mechanism is central to the celebrated Mamba architecture for long-range tasks, but it is also present in more classical model classes used in control engineering and time-series predictions, such as Linear Parameter-Varying (LPV) systems. In this paper we study learnability from a single time-series for a certain class of selective SSMs of which the state-transition, input and readout maps are affine functions of suitable features of the current inputs. We propose a concrete learning algorithm and a finite-sample probabilistic , PAC bound on the parameter-estimation (and hence prediction error) for this learning algorithm. The algorithm itself is an extension of the Ho–Kalman realization-based learning algorithm for linear systems, and it relies on computing the so-called Markov parameters of the SSMs. Our results show that the proposed class of selective SSMs satisfies the single-trajectory analogue of PAC learnability, i.e., it is possible to learn a model with high-enough probability and high-enough accuracy, given a sufficient number of data points.

Primary area:
learning theory
Keywords:
Selective State-Space Models, PAC learnability, Single-Trajectory learning, Time series

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_jUenOpenReview ↗
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
  1. This work bounds the parameter estimation error of a more general class of SSMs using only a single trajectory.
Critical weaknesses
  1. 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.

  2. 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.

  3. 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
AuthorsOpenReview ↗

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\mathcal{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]B_L=\mathbb{E} [R_{L} [k] Z_{L} [k]^{T}], where RL[k]R_{L} [k] is the omitted output tail defined in equation (34). Lemma D.8, equation (49), shows that ΛLGL−1−ΘL=BLGL−1\Lambda_{L}G_{L}^{-1}-\Theta_{L}=B_{L}G_{L}^{-1}. This equation appears in Racz et al. (2025a) (Lemma II.1, eq (3)) without the bias term BLGL−1B_{L}G_{L}^{-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−1G_L^{-1} influences the sampling error Λ^L,N−ΛL\hat \Lambda_{L,N}-\Lambda_{L} and the truncation residual BLB_{L}. Increasing LL 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 LNL_N 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∥∥\|\|G_L^{-1}\|\| with LL.

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, GLG_L is usually estimated from the observed data trajectory as an average of empirical scheduling-weighted input regressors, which converges to GLG_L 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 G^L,N\widehat{G}_{L,N} instead of GLG_L. 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 GLG_L (for which we give a sufficient condition, namely a lower bound on NN), 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]

AuthorsOpenReview ↗

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 N1<N2N_1 < N_2 sample sizes (time steps), such that the bounding term at N2N_2 is smaller than the estimation error at N1N_1, 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 (ρ=0.2,0.35,0.5\rho = 0.2, 0.35, 0.5). 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]

AuthorsOpenReview ↗

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.

Reviewer_c4M9OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

The paper studies the PAC learnability of stable selective SSMs from a single time series. The focus is on LPV systems, where the authors extend the Ho–Kalman method to derive finite-sample bounds on parameter estimation error.

Critical strengths
  • The paper addresses a theoretical problem that is potentially relevant in a number of settings (learning dynamical systems from a single trajectory)

  • The extension to LPV and LPV-SAA systems is a valuable contribution.

  • The mathematical formulation seems comprehensive, structured, and with explicit assumptions. The connection with the literature is also well elaborated.

  • The bridge between classical system identification and modern sequence modelling is non-trivial.

Critical weaknesses

Limited practical applicability of the learning algorithm.

The proposed algorithm assumes knowledge of the population Gram matrix GLG_L (Eq. 12). The authors acknowledge this in Remark 3.1 but leave its empirical estimation to future work. It is unclear whether their results will hold with an estimate of GLG_L, but, more critically, this weakens the claim of learnability from a single observed trajectory (as multiple trajectories would be needed to estimate GLG_L).

Restrictive assumptions.

The guarantees rely on a number of assumptions (see Assumptions 4.1, 4.2, 4.4, 4.5, 4.6), which relate to quadratic stability, minimality, bounded stationary processes, persistence of excitation, and noise–regressor orthogonality. These might be reasonable in the system ID literature, but it is not clear how they restrict the applicability of the results to ML settings. This is relevant, since the authors claim that their work is motivated from using SSMs for forecasting and control/RL (Intro, lines 63-69).

Limited connection to modern ML architectures.

The motivation mentions Mamba and selective SSMs, but the presented results concern LPV representations with a fixed map ϕ\phi. Therefore, it is not clear what the implications are for SSMs used in practice, which are learned from data. My main concern here is that the contribution targets control-theoretic system identification rather than ML practical pipelines.

Empirical validation.

No numerical experiments are provided. This is not a critical point in itself, but it becomes concerning here since i) the authors motivated their work from practical problems, and ii) the assumptions are difficult to address in practice. Simple synthetic experiments could illustrate how their method can recover parameters in a controlled synthetic-data case. Without these, it is difficult to assess / illusrtate the usefulness of the proposal.

Practical significance of the bounds.

To add to the previous point, it is difficult to understand the significance of the bounds. As seen in Thm 5.1, the bound depends on a number of quantities that are unknown in the data-driven case. Therefore, it remains unclear how to instantiate the bound in practice

Questions for authors

These are a limited subset of the points raised above in my comments on weaknesses. Please refer to the list of weaknesses too.

  • How realistic is the assumption that (G_L) is known? Is it possible to provide a guarantee using its empirical estimate? If not, how can the algorithm be applied to the single-trajectory case?

  • Re Mamba: What conclusions can be mentioned about the learnability of Mamba architectures? How restrictive are the considered affine representations?

  • Can a controlled experiment be used to confirm the provided theoretical results?

6 comments
AuthorsOpenReview ↗

Response to Reviewer c4M9

[Comment 5/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. Limited practical applicability of the algorithm / 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, GLG_L is usually estimated from the observed data trajectory as an average of empirical scheduling-weighted input regressors, which converges to GLG_L 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 G^L,N\widehat{G}_{L,N} instead of GLG_L. The extension does not require any new significant assumptions or technical tools. Roughly speaking we show that as long as G^\widehat{G} is a good enough approximation of GLG_L (for which we give a sufficient condition, namely a lower bound on NN), Theorem 5.1 holds with a similar asymptotic scaling and slightly different constants. See Appendix E [in earlier 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, in particular Remark 3.1.

2. Restrictive assumptions. We understand the concern of the reviewer, however we argue that these assumptions are often present in the ML literature either implicitly or explicitly. In particular, to the best of our knowledge, all PAC-like bounds for time series contain at the very least some assumptions on the mixing properties of the data generating system, which in the general case is difficult to estimate. Our set of assumptions allows us to say something about the mixing properties of the underlying processes.

We address each of the assumptions' restrictiveness as follows. 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) before the end of the rebuttal period.

a) Stability is a standard assumption in any domain related to learning dynamical systems or dynamical system based models. Many RNN related works (e.g. https://arxiv.org/abs/1805.10369) assume contractive state matrices, state-space models such as S4, S4D, S5, LRU, and the Mamba model all either implicitly or explicitly establish stability (e.g. via their parameterizations). For instance, the S4 paper (https://arxiv.org/pdf/2111.00396) notes a modification of the parameterization because ``numerical instabilities when the A matrix has eigenvalues on the right half plane'' cause problems (Section 3.4). This also makes sense intuitively, an unstable system's solution trajectory (i.e. a forward pass) can easily depend on the choice of numerical solver. The Mamba paper uses a diagonal state matrix with negative entries both in the paper and in the official github repository (e.g. https://github.com/state-spaces/mamba/blob/main/mamba_ssm/modules/mamba_simple.py line 132). Stability is also common in time series domains, e.g. time series forecasting (https://arxiv.org/abs/2205.08897, NeurIPS, 2022), reservoir computing: (https://arxiv.org/abs/1910.13886, JMLR, 2020), recurrent sequence prediction: (https://arxiv.org/abs/1805.10369, ICLR, 2019).

b) Minimality is a weak technical assumption. We know from LPV realization theory that an LPV system can be recovered from its observed trajectories only up to its minimal component. Informally, if the data generator system is not minimal it contains hidden parameters that do not influence the observations. It is generally not possible to recover these parameters from data trajectories, for more details see (Petreczky et al., 2016) and (Alkhoury et al., 2017) references of the paper. Moreover, the Ho-Kalman algorithm (when applied with the true Markov parameters) returns the minimal system that generated the data trajectory. In other words, if we have two nonminimal LPV systems that could have generated our input data, the Ho-Kalman can't distinguish between the two and will return the (unique up to basis transformations) minimal system that generates the data. Hence even the definition of estimation error is not well-defined for nonminimal systems.

AuthorsOpenReview ↗

Response to Reviewer c4M9

[Comment 5/2]

c) Bounded processes: normalization of the input, output, or even some inner mechanics of an ML model (e.g. batch norm, layer norm) is very common in ML. Usually, the allowed parameter vectors of a model are also assumed to be bounded (e.g. finite step gradient descent with bounded learning rates on bounded inputs usually results in a bounded set of admissible parameters and bounded model outputs).

d) Stationarity) of the considered processes is not without example in the ML literature, e.g. time-series prediction / uncertainty quantification (https://arxiv.org/abs/2010.09107, ICML, 2021), (https://arxiv.org/abs/2212.03463, ICML, 2023), (https://arxiv.org/abs/2203.15885, JMLR, 2024).

The output of a stable system driven by bounded stationary input, scheduling and noise processes from the infinite past is also stationary. Also it is often assumed in time series prediction domains that the input is generated by a stable system that is driven by stationary randomness (e.g. i.i.d. innovation), thus its output is asymptotically stationary, some examples are time-series prediction / reservoir computing: (https://arxiv.org/abs/1910.13886, JMLR, 2020), (https://arxiv.org/abs/1712.00754,JMLR, 2018); causal learning from time series: (https://arxiv.org/abs/2203.06056, JMLR, 2024).

Stationarity assumptions are also consistent with common modelling practices in time series prediction. Usually detrending and seasonal adjustment are applied to a nonstationary time series, and the learning part is applied to the resulting stationary residual. To the best of our knowledge, directly applying learning algorithms to nonstationary processes is neither common in the literature, nor in practice.

AuthorsOpenReview ↗

Response to Reviewer c4M9

[Comment 5/3]

e) Noise-regressor orthogonality is necessary for our analysis to eliminate the noise contribution from the moment terms ΛL\Lambda_L which are used to estimate the Markov parameters. While it rules out an additional noise-dependent term that would not disappear as the number of time steps grows, it still allows the truncation residual RLR_L to be correlated with the regressors ZLZ_L, thus this assumption does not eliminate the truncation bias BLGL−1B_L G_L^{-1}. Therefore this assumption does not really resolve one of the main technical difficulties compared to related work. Furthermore, similar assumptions are present in ML papers: time-series regression: (https://arxiv.org/abs/2206.08269, NeurIPS, 2022), meta-learning / representation learning: (https://arxiv.org/abs/2002.11684, ICML, 2021), transformers / in-context learning: (https://arxiv.org/abs/2306.04637, NeurIPS, 2023), contextual bandits: (https://arxiv.org/abs/1703.00048, ICML, 2017).

f) Persistence of excitation indeed comes from control theoretic and system ID literature. It is needed so that GLG_L is invertible and its inverse is sufficiently bounded, and the regressors ZLZ_L, which correspond to features in ML literature, are linearly independent almost surely. Without it, unobserved directions in the dLd_L dimensional space where ZLZ_Ls live (i.e. such vectors v that vTZL[k]=0v^T Z_L[k]=0 almost surely) would lead to indistinguishable ΘL\Theta_L vectors that are shifted by vv. Equivalently, the regression problem defined by eq (35) in Lemma D.6 does not have a unique solution. For example, when the learnt model is intended to be used under input distribution shift, these irrelevant directions may easily become relevant.

As a result, persistence of excitation is necessary for guaranteeing that the learning algorithm succeeds, not just for our proof technique. This is particularly relevant in those domains where the underlying ML task is related to parameter estimation and recovering an unknown model, e.g. scientific ML: (https://arxiv.org/abs/1710.09668, ICML, 2018), (https://arxiv.org/abs/1509.03580, PNAS, 2016); econometrics / counterfactual prediction: (https://arxiv.org/abs/1612.09596, ICML, 2017); causal discovery:(https://arxiv.org/abs/1803.01422, NeurIPS, 2018); time-series structure learning: (https://arxiv.org/abs/2002.00498, AISTATS, 2020); RL / reward-free exploration: (https://arxiv.org/abs/2002.02794, ICML, 2020).

Furthermore, achieving persistence of excitation in practice is usually cheap and is achieved by adding a small amount of noise to the input trajectory. Intuitively, this corresponds to a commonly used set of data augmentation methods where a random transformation is applied to the input (e.g. random flip / rotation / blur for image classification). The role of the latter is to feed the model a larger section of the relevant input space in order to increase robustness. Persistence of excitation plays the exact same intuitive role for algorithms learning dynamical systems.

In the ML literature, persistence of excitation can also be translated to the assumption on the nondegeneracy of the feature second-moment matrix, which appears in e.g. representation learning: (https://arxiv.org/abs/2002.11684, ICML, 2021).

[EDIT: the equation number has been updated to match the most recent revision]

Reviewer_nYacOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
1
Soundness
3
Read review
Paper summary

The paper proves a finite-sample bound on the parameter estimation error of affine LPV state-space systems (which include switched, bilinear, and some selective SSMs) learned from a single non-i.i.d. trajectory. The algorithm estimates Markov parameters by least squares and recovers the system matrices by Ho-Kalman. Under stability, minimality, and persistence-of-excitation assumptions, Theorem 5.1 gives a rate of N^(-zeta) with zeta = 1/2 for white-noise inputs and smaller for correlated inputs. The main advance over Racz et al. (2025a) and Sattar et al. (2025) is the larger system class and allowing non-i.i.d. inputs. The paper is purely theoretical.

Critical strengths

The setting is more general than the closest prior work: one class covers switched and bilinear systems, the inputs need not be i.i.d., and the system starts in its stationary regime rather than at rest.

Critical weaknesses
  1. No motivating example and no experiments Applications (forecasting with Mamba variants, control and RL, aerospace, robotics) are each mentioned in one sentence, and none is developed into a concrete example. There are also no experiments, while the closest prior work (Racz et al. 2025a) includes one. A motivating example carried through to a small synthetic experiment would make the paper much more convincing.

  2. The presentation is not written for the ICLR audience Six assumptions, a dozen constants spread over Sections 2 to 5, and a bit unusual sentence like "words over a finite alphabet" make the paper very hard to follow. The paper does give an informal theorem (Theorem 2.1), but it comes after two and a half pages of LPV notation and is itself stated in that notation, with little intuition for what drives the rate or why each assumption is needed. By contrast, Simchowitz et al. (2018, 2019 at COLT) state their main result in plain terms in Sections 1 and 2 and build the assumptions and discussion around it. For a purely theoretical paper, this organization matters, and the authors may consider restructuring along those lines. Also, a worked example for a small switched system would also help.

As a minor point, I noticed many typos ("expressivnes", "we cant take", "where rho si as", "Therefor"). Please check these for the revision.

Questions for authors
  1. The algorithm assumes the Gram matrix G_L of the regressors is known (Remark 3.1). Can you elaborate whether this is a fair assumption?

  2. Does the LPV representation in Appendix D cover Mamba-style models as they are actually used in practice, where the transition entries are learned rather than known in advance? If not, which selective SSMs does the analysis apply to?

5 comments
AuthorsOpenReview ↗

Response to Reviewer nYac

[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. No motivating example, no 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 N1<N2N_1 < N_2 sample sizes (time steps), such that the bounding term at N2N_2 is smaller than the estimation error at N1N_1, 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 (ρ=0.2,0.35,0.5\rho = 0.2, 0.35, 0.5). 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 more application friendly experiments would strengthen 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 (see also our answer to the Mamba question), 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.

2. The presentation is not written for ICLR. We understand the reviewer's concern and recognize that the mathematical preliminaries are lengthy. This is exactly the reason why we included an informal theorem in the first place. We also see how the presentation in Simchowitz et al. may be easier to read. Due to the strict schedule of the rebuttal period, we did not manage to include this kind of restructure in the first revision. We will do our best to upload another revision before the rebuttal period ends, in which

  • we rephrase the informal theorem in plainer terms and move it before the mathematical introduction,
  • we make use of the additional page we have to add suitable intuitive preliminaries for the new informal theorem,
  • we include the main terms in the bound and the most important assumptions in an informal phrasing,
  • we consider placing a numerical example's plot in this section, if the page limit allows us.

We would also like to point out that the class of systems we consider is much more general than the one in Simchowitz et al. which had been well known and analyzed for decades. Consequently, proving similar results in our learning framework requires different mathematical analysis and new concepts, which in turn requires a broader and heavier collection of notation, not just for the proof but also for presenting the main theorem, or even the intuitive message behind it.

3. Minor point: typos. We thank the reviewer for pointing out the typos, they will be fixed in the next revised version, before the end of the rebuttal period.

AuthorsOpenReview ↗

Response to Reviewer nYac

[Comment 2/2]

Questions for the authors

1. Known population Gram matrix. Access to the population Gram matrix was assumed mainly for the sake of easier technical analysis. In practice, GLG_L is usually estimated from the observed data trajectory as an average of empirical scheduling-weighted input regressors, which converges to GLG_L 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 G^L,N\widehat{G}_{L,N} instead of GLG_L. The extension does not require any new significant assumptions or technical tools. Roughly speaking we show that as long as G^\widehat{G} is a good enough approximation of GLG_L (for which we give a sufficient condition, namely a lower bound on NN), Theorem 5.1 holds with a similar asymptotic scaling and slightly different constants. See Appendix E in the most recent revised version [earlier it was Appendix C] for more details. We also slightly revise the main text and refer the reader to the appendix regarding this detail.

2. Mamba-style models as LPV systems. We agree that the presentation of Appendix E of the original submission was not clear enough, thus we revised that section for clearer presentation into Appendix G in the most recent revision. In short, the selective Mamba block can be formulated as an LPV system in several ways. One way is based on a corollary of the Cayley-Hamilton theorem, but it is not clear how to apply our analysis to this formulation (see Remark E.1 in the revised version). Therefore, we focus on an approximation of the selective Mamba block that is close to practical implementations. Namely, in practice (e.g. Python libs), the matrix exponential and the softplus function are often computed using their respective Taylor polynomial approximations. Motivated by this, we consider the Mamba block from Gu&Dao (2023, published at COLM in 2024) with the stable, diagonal state matrix, and assume that the softplus and the matrix exponential (that is used to compute the ZOH discretization) are replaced by a good enough polynomial approximation (on bounded domains). We show that the resulting Mamba block can be formulated as an LPV system to which Theorem 5.1 can be applied. We implicitly make some mild assumptions that hold in practice, such as that the polynomial approximations are good enough, the stable diagonal state matrix (from the Mamba paper), compact parameter and input domains (e.g. Euclidean balls), or that the input process has a joint density wrt the Lebesgue measure. See the revised Appendix G [earlier Appendix E] for more details.

We thank again the reviewer for their hard work and are happy to clarify any detail regarding our response and answer any further question.

AuthorsOpenReview ↗

2nd Response to Reviewer nYac

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 previous response) 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 KHKK_{HK} 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 [Appendix F in earlier revisions].

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.

[EDIT: in the most recent revision, experiments are described in Appendix H]

Comments on the paper

1 comment

Dear All,

We are grateful for your work on this rebuttal. We summarize the review discussions and the changes in the revision compared to the original submission in the following.

Shared points by all Reviewers:

  1. knowledge of the population Gram matrix GLG_L,
  2. the applicability on the Mamba architecture,
  3. lack of experiments to illustrate the theoretical contribution.

We think we entirely resolved these issues in our responses and revision,

  1. we gave a natural and compact extension of the theorem to the empirical estimate (from the data sample) of GLG_L in Appendix E
  2. we revised the Mamba related section in the appendix into a clear presentation into Appendix G; we showed that the Theorem applies to the practical approximation of the Mamba core (i.e. the softplus and exponential is approximated by a polynomial which is often the case in practice with Taylor approximations)
  3. we added 3 synthetic numerical examples to Appendix H (one figure to the main text), which illustrate our theorem; the third experiment shows that our bound can be used to set a hyperparameter (the Hankel selection) of the learning algorithm so that the estimation error is low (without running the algorithm many times).

Reviewer nYac: In addition to the shared points, the Reviewer asked for an informal presentation of our results, which we included in the revision in Section 2.2. (also Appendix C.1 and C.1.1) in the exact format the Reviewer required. The Reviewer accepted our response as answers to his questions.

Reviewer c4M9: In addition to the shared points, the Reviewer was concerned about the restrictiveness of the assumptions, the practical applicability and the usefulness to the ML community of our results. In two comprehensive responses we addressed all these issues  1. we discussed why each assumption is realistic with several examples from the ML literature from top venues  2. we presented our third experiment, several learnability papers from top venues with followup papers containing their  comprehensive empirical validation (often by other authors), and several concrete future work ideas with precedents from the ML literature. We gathered 34 additional citations to back up our arguments, most of it from top tier ML venues.

Appendix B and Appendix C in the revision contain the suitable version of these discussions.

Reviewer jUen: In addition to the shared points, the Reviewer asked for the clarification of the proof novelties which we answered in detail in our first response. The Reviewer raised an additional question to which we provided further clarifications on a point already covered in the original manuscript.

Changes in the revision. For simplicity, we also separately list the changes in the revision compared to the original manuscript. All the changes (except typo fixes) are written in blue.

  • Section 2.2. adds an informal overview and a Example 2.1 which we use to illustrate the results on, and a Figure from the experiments section to illustrate the theorem  - Appendix B about the applicability of our results and future work ideas
  • Appendix C contains the extended discussion of the assumptions, and illustrates them and the bounding term on Example 2.1
  • Appendix E contains the extension to empirical Gram matrices
  • Appendix G revises the former Appendix E and shows how to apply the main Theorem on the selective Mamba block
  • Appendix H contains the details of the experiments and an additional Figure
  • the supplementary material now contains the source code of the experiments
  • we made some minor modifications in the main text which addresses the new appendices and reflects on the discussion with the reviewers  - typo fixes (these are not blue)

Thank you again and best regards, The Authors

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.