Neural Lyapunov functions are learned "energy" functions that provably decrease along a system's trajectories. They certify that nonlinear controllers are stable over regions much larger than classical polynomial methods can reach. They are trained by gradient descent on a non-convex loss, though, and when training stalls nobody can tell why. Either the optimizer got stuck, or no certificate of that shape exists. This proposal makes that question answerable.
The certificate is a two-layer ReLU network, a network with one hidden layer of units that output $\max(0,\cdot)$. For such a network, fitting both the function's values and its gradient along the dynamics can be rewritten exactly as a convex program, borrowing the activation-pattern reformulation from the theory of why overparameterized networks train well. Every Lyapunov condition imposed at a sampled state then becomes a linear inequality. The search either returns the globally optimal certificate on the sampled states or returns a convex proof that none exists in the class. The same program measures the gap between what gradient descent reached and what was reachable, on correlated trajectory data where the existing global-convergence theory does not apply.
Core Claim
Gradient-based certificate learners report stalls and plateaus. Neural Lyapunov Control trains a neural controller and a neural Lyapunov function against a satisfiability-modulo-theories (SMT) solver called dReal that searches for violating states, and the training step needs heuristic restarts. Learning Certified Control Using Contraction Metric co-trains a controller and a contraction metric with plain stochastic gradient descent and checks validity only after training. Both papers motivate this work, because they show that the training step is the uncertified bottleneck.
The theory side offers two guarantees, and neither transfers. Global Convergence of Sobolev Training for Overparameterized Neural Networks proves that gradient flow globally fits values and directional derivatives. That is the right loss type for a certificate, but it needs width $m=\Omega(n^6k^4\cdots)$ and separated, non-degenerate inputs. Trajectory samples that bunch near an equilibrium violate those conditions. Convex Relaxations of ReLU Neural Networks Approximate Global Optima in Polynomial Time supplies the method we reuse: an exact convex reformulation of weight-decayed two-layer ReLU training over fixed activation patterns, plus a sampled-pattern relaxation whose $O(\sqrt{\log n})$ gap is proven only for Gaussian inputs.
The observation that connects these is that inside one activation pattern, both the network output and its spatial gradient are linear in the reformulated weights. The Lie derivative, meaning the rate of change of $V$ along the dynamics, $\nabla V(x)^\top f(x)$, is therefore also linear once $f$ is known. The certificate problem for a fixed closed loop is thus convex without any lazy-training approximation, extreme width, or Gaussian assumption.
The Convex Program
Let $\tilde x=[x;1]$ be the state with a bias coordinate appended. Let $g_1,\dots,g_P$ be gate vectors that define activation patterns, and let $d_i(x)=\mathbb{1}[g_i^\top\tilde x\ge 0]$. The certificate is parameterized as $V(x)=\sum_i d_i(x)(u_i-v_i)^\top\tilde x$, where $u_i,v_i$ are the reformulated weights. Its gradient is $\nabla V(x)=\sum_i d_i(x)(u_i-v_i)_{1:n}$, where $n$ is the state dimension.
Take closed-loop dynamics $f$, meaning plant plus a fixed controller, and sampled states $x_1,\dots,x_K$ with margin $\epsilon>0$. We solve
$$\min_{u,v}\ \sum_{i=1}^P \|u_i\|_2+\|v_i\|_2 \quad \text{s.t.}\quad V(x_k)\ge \epsilon\|x_k\|,\ \ \nabla V(x_k)^\top f(x_k)\le -\epsilon\|x_k\|,\ \ V(0)=0,$$
together with the cone constraints $(2d_i(x_k)-1)\,u_i^\top\tilde x_k\ge 0$ and the same for $v_i$. These cone constraints ensure that the solution maps back to an actual ReLU network whose units fire exactly as the gates predict on the samples.
The result is a second-order cone program. When every pattern realized on the data is included, its optimum equals the global optimum of the weight-decayed non-convex certificate problem on those samples, by the equivalence in Convex Relaxations of ReLU Neural Networks Approximate Global Optima in Polynomial Time. If the program is infeasible, its dual gives a certificate that no two-layer ReLU Lyapunov function satisfies the sampled conditions. Gradient descent can never provide that kind of negative result.
Research Program
We build a counterexample-guided loop in which the learner step is this convex program. Each round, we map the solution back to a ReLU network. We then run a falsifier on it: dReal as in Neural Lyapunov Control for systems with up to six states, and Lipschitz-margin gridding beyond that. Any violating states are added as new linear constraints, and the program is re-solved.
Because the feasible set only shrinks, the loop has a clean termination structure. It either certifies the network or reaches infeasibility, which proves the class is too small and justifies adding patterns rather than restarting.
We will handle two technical issues directly.
The first is non-smoothness. A piecewise-linear $V$ needs decrease on every active piece at pattern boundaries, which is the generalized-gradient condition. We enforce it by imposing the Lie constraint for each adjacent pattern at samples near a boundary. That is still linear.
The second is the number of patterns. It is small for the low-dimensional benchmarks, where exact enumeration over data-realized patterns is feasible. For larger systems we use sampled gates and measure the resulting gap empirically. That measurement doubles as a test of whether the Gaussian assumption in Kim and Pilanci's bound actually matters for trajectory data.
For controller co-design, which is genuinely bilinear, we alternate two steps. The certificate step is globally optimal via the convex program. The controller step is a gradient update on the Lie margin. The goal is not to claim co-design is solved. It is to locate where non-convexity actually remains once the certificate half is exact.
The second product is a diagnostic. For every stalled gradient-descent run of the standard learner, we solve the convex program on the same samples. This tells us whether the stall was an optimization failure, meaning a feasible certificate existed, or a capacity limit, meaning the program was infeasible. It is the first direct measurement of the non-convex gap in certificate learning.
Baselines
The naive reference is a quadratic Lyapunov function from the linear-quadratic regulator (LQR) at the equilibrium, verified over its largest valid sublevel set. It is convex, cheap, and the usual default. Every method is scored by certified region-of-attraction volume against the same falsifier.
The strongest existing method is the learner-falsifier approach of Neural Lyapunov Control. It reports certified regions of attraction "300% to 600% larger" than LQR and sum-of-squares on its benchmarks, and it balanced the 3-link humanoid where sum-of-squares failed. No absolute region-volume numbers were found on Lacuna, so we will rerun it ourselves.
The comparison is held fair in three ways. The same closed-loop controller is shared by both methods, taken from their training where applicable. Both use the same dReal falsifier and tolerance, and both get the same sampled-state budget. The gradient learner is also given a wall-clock budget equal to our convex solves, including restarts, and a network width equal to the number of active patterns our solution uses.
Beating it means one of two outcomes at matched time. The first is a larger certified region of attraction. The second is equal volume, with certification succeeding on seeds where the gradient learner stalled.
Sum-of-squares programming serves as the classical convex competitor. It is run at polynomial degrees that match our solve time.
The key ablation removes the convex step but keeps everything else. It trains the same mapped-back ReLU parameterization by gradient descent from random initialization and from the NTK-style wide regime, at widths up to the memory limit. This isolates whether the gain comes from global optimization or from the parameterization.
A second ablation replaces exact pattern enumeration with Gaussian-sampled gates. It measures how much of the gap Kim and Pilanci's relaxation leaves on trajectory data.
For co-design, the baseline is Learning Certified Control Using Contraction Metric. It was the only method to find stable controllers on all nine of its models. We compare our alternating scheme against it on synthesis success rate over seeds for PVTOL and Segway.
Why not just…?
Why not just make the network wider and rely on overparameterization theory? This is the most serious threat, since width empirically removes bad minima The Loss Surface of Deep and Wide Neural Networks. The proven widths, however, scale polynomially and far beyond practice, and they assume separated data Global Convergence of Sobolev Training for Overparameterized Neural Networks. Even when width works, gradient descent cannot report that a certificate does not exist. The wide-network ablation settles the empirical part. If wide gradient descent matches our certified volume and success rate at equal compute, the remaining contribution shrinks to infeasibility proofs and gap measurement, and we will say so.
Why not just use sum-of-squares, which is already convex? Sum-of-squares is limited to polynomial certificates. It was 300% to 600% more conservative than neural certificates and numerically failed on the humanoid Neural Lyapunov Control. It also failed on Segway and the Neural Lander, whose dynamics are non-polynomial Learning Certified Control Using Contraction Metric. Our program is convex but piecewise-linear and data-adaptive, so it avoids the polynomial restriction. It is included as a baseline regardless.
Why not just use the loop-transformation semidefinite program for neural controllers? Imitation Learning with Stability and Safety Guarantees convexifies stability conditions using sector bounds on activations. It is restricted to linear time-invariant plants, and its semidefinite programs scale cubically. Our constraints are linear per sample and apply to nonlinear $f$. We will still report its region of attraction on the pendulum's linearization as a reference point.
Proposed Experiments
The benchmarks are those used by the cited papers: the inverted pendulum, the 6-state Caltech ducted fan, and the 3-link humanoid from Neural Lyapunov Control; cart-pole and the 2D quadrotor from safe-control-gym; and PVTOL and Segway from the contraction-metric suite. The metrics are four: certified region-of-attraction volume, wall-clock time to certification, the fraction of seeds certified, and the relative optimality gap between the final gradient-descent loss and the convex optimum on identical samples.
The decisive check is the stall diagnosis. We collect runs where the Neural Lyapunov Control learner plateaus and solve the convex program on their samples. If most stalls turn out feasible, then the field's "hard optimization" is an artifact of the optimizer and the convex learner should dominate. If most turn out infeasible, the bottleneck is certificate capacity, and the right move is to change the parameterization rather than the optimizer. Either outcome is informative.
A second check tracks the sampled-gate gap as data moves from uniform samples to trajectory samples bunched near the equilibrium. Growth of the gap would show that the Gaussian assumption in existing relaxation bounds does real work, and that bounds adapted to trajectory data are needed.
References
- Neural Lyapunov Control
- Learning Certified Control Using Contraction Metric
- Global Convergence of Sobolev Training for Overparameterized Neural Networks
- Convex Relaxations of ReLU Neural Networks Approximate Global Optima in Polynomial Time
- The Loss Surface of Deep and Wide Neural Networks
- Imitation Learning With Stability and Safety Guarantees
- Safe-Control-Gym: A Unified Benchmark Suite for Safe Learning-Based Control and Reinforcement Learning in Robotics