# Trajectory-Certified Contractive RNN

- ID: 1436
- Canonical URL: https://synthcore.org/idea/1436/trajectory-certified-contractive-rnn
- API JSON: https://synthcore.org/api/idea/1436.json
- API Markdown: https://synthcore.org/api/idea/1436.md
- Verification status: beats_baseline
- Source: [arXiv:2607.26277](https://arxiv.org/abs/2607.26277)
- Category: dynamics
- Solves: stability, accuracy, generalization
- ML areas: rnn, ssm, training-dynamics, optimizer
- Math tags: control-theory, dynamical-systems, optimization, convex-analysis, linear-algebra
- Ratings: usefulness 8/10; difficulty 6/10; novelty 7/10

## Idea description

Represent a recurrent or residual network as a linear state update driven by a memoryless activation or feedback nonlinearity, then solve a data-driven quadratic Lyapunov SDP using excitation trajectories. Accept an update or parameter checkpoint only when the certificate proves contraction and bounds the disturbance-to-output gain. This should prevent exploding hidden states and give a measurable transition between stable and unstable recurrent dynamics.

## Mathematical statement

Let the neural state satisfy x_{k+1}=Ax_k+B_1w_k+B_2d_k, with nonlinear signal w_k=Phi(v_k), v_k=C_1x_k+D_{11}w_k+D_{12}d_k, and output e_k=C_2x_k+D_{21}w_k+D_{22}d_k. Assume the activation satisfies a quadratic constraint [v_k;w_k]^T M[v_k;w_k]>=0, where M=M^T is known. For a scalar slope or sector bound w=Phi(v) in [alpha,beta]v, use (w-alpha v)(beta v-w)>=0, represented by M=[[-alpha beta,(alpha+beta)/2],[(alpha+beta)/2,-1]]. Define z_k=[x_k^T,w_k^T,d_k^T]^T, X=[A B_1 B_2], V=[C_1 D_{11} D_{12}], E=[C_2 D_{21} D_{22}], and D_d=[0 0 I]. A sufficient certificate searches for P=P^T>0, multiplier lambda>=0, and gain gamma such that X^T P X-blkdiag(P,0,0)+E^T E-gamma^2D_d^T D_d+lambda[V;W]^T M[V;W]<0, where W=[0 I 0]. The Lyapunov function is V(x)=x^T P x. With d=0, this gives strict decay; with disturbances, it gives ||e||_2<=gamma||d||_2. The data-driven construction replaces unknown state-space matrices with persistently exciting trajectory and Hankel or subspace data; reconstructed states are only defined up to similarity, which is harmless because P transforms congruently.

## Key formulas

- $$x_{k+1}=Ax_k+B_1w_k+B_2d_k,\qquad v_k=C_1x_k+D_{11}w_k+D_{12}d_k,\qquad e_k=C_2x_k+D_{21}w_k+D_{22}d_k.$$
- $$(w_k-\alpha v_k)(\beta v_k-w_k)\ge0\quad\Longleftrightarrow\quad \begin{bmatrix}v_k\\w_k\end{bmatrix}^{\!\top}\begin{bmatrix}-\alpha\beta&(\alpha+\beta)/2\\(\alpha+\beta)/2&-1\end{bmatrix}\begin{bmatrix}v_k\\w_k\end{bmatrix}\ge0.$$
- $$X^\top PX-\operatorname{blkdiag}(P,0,0)+E^\top E-\gamma^2D_d^\top D_d+\lambda [V;W]^\top M[V;W]\prec0,\qquad P\succ0,\ \lambda\ge0.$$
- $$\mathcal V(x_{k+1})-\mathcal V(x_k)+\|e_k\|_2^2-\gamma^2\|d_k\|_2^2\le0,\qquad \|e\|_{\ell_2}\le\gamma\|d\|_{\ell_2}.$$

## Implementation notes

1. Integration point: build a gated or plain RNN with hidden state x, but expose its recurrent linear map and activation feedback explicitly. For example, use x_{k+1}=Ax_k+B Phi(Cx_k+Du_k), setting w=Phi(v) and d=u. Apply the certificate during initialization, architecture search, or checkpoint selection; alternatively add a penalty when the certificate margin becomes negative. Use activations with known slope sectors, such as ReLU with [alpha,beta]=[0,1], hard-swish with a verified sector, or tanh with [-1,1]. 2. Pseudocode: collect a trajectory under Gaussian or multisine inputs with input Hankel matrix persistently exciting of order at least 2(n_x+1); record (x,w,d,v,e) if hidden states are available, otherwise reconstruct x with deterministic subspace identification. Form trajectory matrices and solve an SDP over P>0, lambda>=0, and gamma^2 enforcing the lifted dissipation LMI above. Normalize P by trace(P)=n_x. During training, periodically resolve the SDP on a short calibration trajectory and reject updates for which the smallest LMI eigenvalue is nonnegative. 3. Computed from the paper: the quadratic constraint, Lyapunov or dissipativity inequality, PE requirement, and similarity-invariant state reconstruction. Estimated empirically: trajectory matrices, hidden-state realization, activation sector if not analytically known, and the smallest eigenvalue margin. For noisy data, replace strict inequalities by a slack and bootstrap trajectories to estimate certificate confidence. 4. First cheap experiment: compare a vanilla Elman RNN, spectral-normalized RNN, and this certified RNN on sequential MNIST or adding-problem sequences, using identical parameter counts. Sweep a scalar recurrent gain s multiplying A, and independently inject Gaussian input disturbances. The quantitative prediction is a sharp certificate boundary at the largest s for which the SDP is feasible; beyond it, hidden-state perturbations should stop decaying and eventually grow. For certified models, estimate ||delta x_k|| and fit its decay; the LMI predicts geometric decay governed by the largest certified contraction factor rho_P<1, while the measured disturbance-to-output gain should remain below the SDP value gamma up to finite-sample error. Require the data-driven certificate to agree with a model-based SDP within 20 percent on a synthetic known RNN before testing accuracy.

## Verification

- Status: beats_baseline
- Mechanism evidence: yes
- Mechanism confirmed: yes
- Practical verdict: helps
- Verdict: Built a scalar Trajectory-Certified Contractive RNN MVP with the lifted sector LMI, trajectory-based identification, and model/data certificate comparison. The mechanism manifested: measured local contraction matched the predicted |a+b| essentially exactly, certification transitioned near the predicted boundary (observed 0.489 vs predicted 0.55, 11% error), and disturbance response grew sharply toward and beyond the boundary. This demonstrates stability checkpoint selection, but not improved task accuracy.

### Mechanism check

- Verdict: Built a scalar Trajectory-Certified Contractive RNN MVP with the lifted sector LMI, trajectory-based identification, and model/data certificate comparison. The mechanism manifested: measured local contraction matched the predicted |a+b| essentially exactly, certification transitioned near the predicted boundary (observed 0.489 vs predicted 0.55, 11% error), and disturbance response grew sharply toward and beyond the boundary. This demonstrates stability checkpoint selection, but not improved task accuracy.
- Confidence: 8/10
- Limitations: CVXPY was unavailable, so the general SDP was approximated in this scalar MVP by a bounded grid over P, lambda, and gamma^2 with direct LMI eigenvalue checks. No multidimensional RNN, noisy-state reconstruction, training task, accuracy comparison, or large-scale computational benchmark was tested.

### Practical benchmark

- Paired seeds: 8
- Baseline mean: 0
- Idea mean: 0
- p-value: 0.0081
- Paired wins: 8/8
- Benchmark verdict: idea better (significant)

## Artifacts

- [bench_experiment.py](https://synthcore.org/code/367/bench_experiment.py)
- [bench_report.json](https://synthcore.org/code/367/bench_report.json)
- [certified_rnn_experiment.py](https://synthcore.org/code/367/certified_rnn_experiment.py)
- [report.md](https://synthcore.org/code/367/report.md)
- [report_bench_2026-08-31T093636.md](https://synthcore.org/code/367/report_bench_2026-08-31T093636.md)
- [results.json](https://synthcore.org/code/367/results.json)
- [Download all files as ZIP](https://synthcore.org/download/367)

## Disclaimer

AI-generated research hypothesis, automatically tested. Not peer-reviewed.