Adaptive SOS Lyapunov Certificate Ladder

1. Integration point: start with a two- or three-dimensional polynomial RNN or a ReLU RNN whose activation regions are fixed during certification. Use \(z_{t+1}=F_\theta(z_t)\), choose \(V(z)=z^TPz\) with \(P\succ0\), and certify on \(z\geq0\) and \(\|z\|_2\leq R\). For ReLU networks, certify each active linear region or replace ReLU locally by a polynomial approximation. 2. Pseudocode: train for K steps; freeze \(\theta\); construct coefficients of \(q_\theta(z)=V(z)-V(F_\theta(z))-\alpha\|z\|^{2d}\); for r=0,1,2,... solve the SDP for \(Q_r\succeq0\), adding SOS multipliers for box constraints; accept the update if all Gram matrices have minimum eigenvalue above tolerance \(-\tau\). If infeasible, reduce the optimizer step, increase stability regularization, or try r+1. Estimate the threshold by binary-searching the smallest \(\varepsilon\) such that \(q_\theta+\varepsilon\|z\|^{2d}\) is certified at level r. 3. Computed quantities are SDP feasibility, Gram eigenvalues, and \(\varepsilon_r\); polynomial approximation error, region coverage, and numerical tolerance are empirical estimates. 4. First experiment: train a two-dimensional RNN on MNIST sequences, comparing SGD, spectral normalization, and SOS-controlled training. Sweep recurrent weights across an empirical rollout-divergence boundary. The prediction is \(\varepsilon_r\) decreases monotonically with r, and certified models exhibit geometric Lyapunov decay \(V(z_t)\lesssim(1-c)^tV(z_0)\). The first feasible level should predict the empirical stability boundary within 20%, while robust certificates should persist under small parameter perturbations.