Abstract
This paper establishes the first theoretical correctness guarantees for using ReLU neural networks to analyze the stability of switched linear systems. By framing ReLU networks as Continuous Piecewise Linear (CPWL) functions, the authors demonstrate that neural Lyapunov functions can effectively approximate the Joint Spectral Radius (JSR). The study shows that neural approaches can overcome the "curse of dimensionality" inherent in traditional Sum-of-Squares (SOS) methods, provided that regularization and incremental learning are employed to prevent overfitting.
Introduction
In control theory, a switched linear system jumps between different modes of linear behavior, such as a walking robot transitioning between left and right foot contact. Determining the stability of such systems—ensuring all trajectories eventually return to zero—is a fundamental challenge. Mathematically, this requires computing the Joint Spectral Radius (JSR), a task that is NP-hard and often undecidable in general cases.
While classical methods like Sum-of-Squares (SOS) provide formal guarantees, they suffer from the "curse of dimensionality," scaling poorly as system complexity increases. Neural networks offer a powerful alternative for learning Lyapunov functions, but they have historically lacked the formal guarantees required for safety-critical applications. This paper bridges that gap by providing theoretical bounds on the network complexity required to approximate the JSR to a specific accuracy.
Methods: ReLU Networks as Lyapunov Candidates
The authors utilize Neural Lyapunov Functions (NLFs) based on ReLU-activated feedforward networks. Their approach is built on several key technical pillars:
- CPWL Representation: ReLU networks represent Continuous Piecewise Linear (CPWL) functions. In control theory, CPWL functions define polytopic norms, which are known to be excellent tools for JSR approximation.
- Theoretical Bounds: The paper derives new theorems relating the depth and width of a ReLU network to the precision of the JSR approximation, providing the first universal approximation result tailored for NLFs.
- Sample-Based Training: Instead of massive optimization, the network is trained on points sampled from the unit sphere. The loss function minimizes the system's growth rate to find the tightest Lyapunov function.
- Overfitting Mitigation: To prevent the network from underestimating the JSR (a dangerous form of overfitting in stability analysis), the authors introduce L1-regularization and incremental learning.
Key Insights: The Efficiency Flip
A major finding is the "Efficiency Flip." Traditional SOS methods require a number of variables that grows polynomially with dimension but exponentially with the polynomial degree. As shown in Figure 1, for high-dimensional systems, the CPWL approach via neural networks can require significantly fewer variables to achieve comparable precision.
To ensure the learned function $V(x)$ is a valid Lyapunov candidate, the authors structurally enforce non-negativity on the output weights. They also highlight the "Overfitting Trap": without regularization, neural networks tend to provide optimistic (incorrectly low) estimates of the JSR, which could lead to false stability claims in real-world systems.
Key Results
In a 2D benchmark, the neural approach achieved a JSR approximation of ~8.69, outperforming both ellipsoidal methods (9.58) and degree-4 SOS (8.72). In higher-dimensional tests (e.g., 8D systems), the neural network provided tighter approximations than SOS in a fraction of the time when properly regularized.
As seen in Figure 6, standard neural training (blue line) can lead to "optimistic" estimates that fall below the true JSR. However, techniques like incremental learning and L1-regularization (orange and yellow lines) allow the network to converge toward a mathematically sound and tighter bound than traditional SOS approximations.
Limitations and Future Work
While promising, the raw output of a trained neural network is currently a sample-based estimate. Converting this into a 100% guaranteed formal upper bound requires a post-processing step (computing a convex hull) that remains computationally intensive. Future work will focus on exploring more sophisticated architectures and extending this framework to non-linear switched systems.
Summary updated