Parallel method proves stability of deep neural systems faster
Hyperlyve: Parallelized Enumeration and Exact Lyapunov Stability Certification for Deep ReLU Networks
Computational GeometryMachine LearningLogic in Computer Science
Summary
Ensuring that systems controlled by deep neural networks remain stable over time is a big challenge. The authors present Hyperlyve, a tool that breaks down a neural network into regions defined by its ReLU activations and checks stability conditions precisely within each region. This allows it to certify that the system's behavior will settle down safely in cases where other methods are too slow. Hyperlyve’s approach is mathematically thorough and much faster than previous tools. It also clarifies the difficulty level of checking these stability guarantees.
What this means in practice
- •For control engineers: Verify stability of control systems using deep neural networks more efficiently and precisely by partitioning neural activations.
- •For autonomous vehicle developers: Certify that autonomous systems with neural controllers behave stably in diverse operating regions without excessive computational cost.
Authors
Brian Yarbrough, Jesse Wayment, Jingbo Wang, Philip E. Paré, Shreyas Sundaram
Abstract
We introduce Hyperlyve (Hyperplane Partitioned Lyapunov Verification and Enumeration), a framework for proving the asymptotic stability of nonlinear dynamical systems, including those with neural network controllers. Hyperlyve learns and formally certifies continuous piecewise-affine (CPA) neural Lyapunov functions within a counterexample-guided inductive synthesis (CEGIS) loop. Hyperlyve's key innovation is a parallel algorithm that enumerates the hyperplane arrangement formed by the ReLU activations of deep networks and certifies that Lyapunov conditions hold within each polyhedral region. We derive sound and complete regional tests to verify the asymptotic stability of the exact smooth dynamics (rather than a piecewise-linear approximation) within a compact domain of interest. Furthermore, we formally characterize the computational complexity of the CPA neural Lyapunov verification problem as co-NP-complete, filling a key gap in the literature. Empirical results demonstrate that Hyperlyve enumerates ReLU networks over 150-times faster than competing tools, which contributes to Hyperlyve proving the asymptotic stability of systems that are currently intractable for state-of-the-art verifiers.