acceptodds
Under review as a conference paper at ICLR 2027

Gradient-Based Learning of Minimal Predictive Realizations from Finite Hankel Blocks

Abstract

We study gradient-based learning of linear recurrent models in an overparameterized hidden space from finite Hankel matrices, whose entries are scores of concatenated prefixes and suffixes. We assume that the target has finite Hankel rank and observe a base matrix attaining this rank together with its one-symbol shifts. Exact fitting of the base and one-symbol Hankel blocks through a decoder does not guarantee correct multistep predictions with unconstrained transitions. We construct a training procedure that updates state, decoder, and transition parameters concurrently, with each loss restricted to its corresponding parameter group. We prove global convergence from any full-rank state initialization and arbitrary finite initializations of the remaining parameters. The limiting state matrix has the target Hankel rank, and removing redundant dimensions yields a model with the minimum possible state dimension that predicts every finite sequence exactly. For every fixed positive feedback strength, we exhibit a normally attracting manifold of non-global local minima with an open basin containing full-rank initializations. A computable switching certificate then combines global triangular training with convergent fully coupled updates. We also prove deterministic fixed-step convergence under sufficient step-size conditions and derive fixed-length prediction-error bounds for least-squares reconstructions from perturbed Hankel matrices. Experiments on finite-rank weighted sequence systems recover the target rank in all 90 runs and illustrate failures of one-step fitting, local convergence under coupled gradients, and prediction stability under Hankel perturbations.

Primary area:
learning theory
Keywords:
linear recurrent models, Hankel matrices, predictive state representations, gradient dynamics, nonconvex optimization

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_F7dQOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper studies learning a state matrix WW, decoder parameters Γ\Gamma, and transition parameters Ωx\Omega_x from known matrices HH and HxH_x, where each letter xx in an alphabet has it's own Ωx\Omega_x and HxH_x. The state loss trains WW⊤WW^\top to approximate G=HH⊤G=HH^\top (with weight decay on the WW), the decoder loss trains WW⊤ΓWW^\top\Gamma to approximate HH, and each transition loss trains WW⊤ΩxWW⊤ΓWW^\top\Omega_xWW^\top\Gamma to approximate the corresponding HxH_x.

Theorem 9 proves that when WW is updated only using the state loss, Γ\Gamma is udpated using only the decoder loss, and each Ωx\Omega_x is updated only by its corresponding transition loss, then the gradient flow converges globally from any initialisation of WW that is full rank and arbitrary finite initialisations of Γ\Gamma and the Ωx\Omega_x. In contrast, Theorem 12 proves that when every parameter is updated by every loss that depends on it, the gradient flow can converge to non-optimal minima. Theorem 13 proves that after a finite time, it is possible to switch from the decoupled training to fully coupled updates while still converging.

When HH is a complete finite block of the target function’s finite-rank Hankel matrix and HxH_x are its one-symbol shifts, the limiting parameters induce an exact linear recurrent realisation through the decoder C=W⊤ΓC=W^\top\Gamma and transitions Ax=W⊤ΩxWA_x=W^\top\Omega_xW.

Critical strengths
  1. The mathematical formulation is precise, and the assumptions and main theoretical results are clearly stated, although some of the mathematical arguments can be hard to follow. I did not identify any errors in the proofs of the results.
  2. The controlled synthetic experiments nicely demonstrate the key theoretical results.
Critical weaknesses

It is not clear how much relevance the results of this paper have outside the relatively narrow case considered, where one has access to a complete finite Hankel block and its one-symbol shifts, and follows the particular training procedure proposed by the paper. In particular, it is unclear if the difference between triangular and fully coupled training has any implications on training recurrent models in practice. In my opinion, this limits the paper’s apparent appeal for the general ICLR audience. However, my background is outside this particular theoretical area, and I welcome the other reviewers’ perspectives on the significance of these results.

Questions for authors

I have no questions for the authors.

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

The paper presents/studies a switched linear dynamical system model for sequence learning. For this problem, they consider unknown system, and are able using gradient methods to learn the dynamics. This is similar to results for learning in LDS without knowing the system, such as spectral filtering results, but they model they consider here is different (not more and not less general), since the system matrices can switch based on the inputs, and the inputs belong to some finite alphabet. They show that they can learn the system even with over parameterization, and with certain types of noise (which is not very general noise). It is a theoretical paper that proves convergence results for their optimization algorithm.

Critical strengths

It is a strong paper in terms of theoretical guarantees. Over parameterization is a difficult topic, and they are able to say something meaningful in this space. The dynamics model is strong in some aspects (switching matrices over discrete alphabets).

Critical weaknesses

I'm not sure why this dynamics model is interesting, and the authors can comment on this in the rebuttal, or relate to LDS and the vast literature there.
Missing comparison to significant literature in learning LDS, especially improper learning via spectral filtering and related work. No relevance to the practice of sequence learning is demonstrated or stated, nor robotics, or control.

Questions for authors

I invite the authors to comment on relevance of this theoretical model to practical relevance in either sequence prediction or robotics.

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

In short the paper is about convergence properties of the flow of gradient system of the loss function L_state. It is about how overparameterized matrix W converges to the minimal representation. And of course knowing minimal representation is important in control theory and subspace methods, but I have unfortunately lost the picture of the relevance to machine learning algorithms here. Having said this I appreciate how carefull derivation is. I read the work as a study of convergence of dynamical systems. In this particular instance, many difficulties have to resort out., for example noticing the the results is independent on mutiplication by an orthogonal matrix searching for the solution in the space of symmetric matrices.

Critical strengths

The paper is strong mathematically. It is written carefully. Every object used in the paper is properly introduced.

Critical weaknesses

The authors did not specify why the addressed problem is relevant for machine learning. It is a study in convergence of dynamical systems, which is nothing wrong but the connection with machine learning shall be given.

The guidlines for the reader would be appreciated in theorem of explaining what will be derived next and why the result is important. For example, the authors put some attention to study the quotient space GL(m)/O(m), but have not plainly said that this corresponds to the symmetric matrix, to make reading easier.

Questions for authors

What does it mean "to learn" in this paper ? It sounds it is the convergence of a dynamical system

Why the map \rho_v is a restriction, the domain is the whole R_f ?

Why the loss function L_state is vital to study in machine learning ?

In theorem 5, convergence is discussed but it must be in some kind generic sense because the discussed gradient system has saddle points ?

Comments on the paper

1 comment
Area_Chair_WhDEOpenReview ↗

Reminder to reviwers to read author's responses

Dear Reviewers,

Thank you for your efforts in providing thorough reviews.

As the discussion period is underway, I would like to kindly remind you to read the authors' responses to your reviews and provide follow-up comments where appropriate or leave a comment. In particular, please consider whether the responses address your questions and concerns, and update your assessment if the clarifications or additional information affect your initial evaluation.

Your engagement in this discussion is important for ensuring a fair and thorough review process.

Thank you again for your time and contributions!

Best regards, Area Chair

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.