⚡ electrical engineering

SCORE: Statistical Certification of Regions of Attraction via Extreme Value Theory

The paper introduces SCORE, a statistical certification framework that leverages Projected Stochastic Gradient Langevin Dynamics and Extreme Value Theory to efficiently bound safety violations and certify Regions of Attraction for high-dimensional nonlinear dynamical systems, overcoming the scalability limitations of traditional deterministic verification methods.

Original authors: Pietro Zanotta, Panos Stinis, Ján Drgoňa

Published 2026-04-01

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Pietro Zanotta, Panos Stinis, Ján Drgoňa

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are the safety inspector for a massive, chaotic roller coaster. Your job is to answer one critical question: "If a rider starts anywhere within this specific zone, will the ride eventually slow down and stop safely at the station, or will they fly off the track?"

In the world of engineering and math, this "safe zone" is called the Region of Attraction (ROA).

For simple, small roller coasters (low-dimensional systems), we have old, rigid rulebooks (like Sum-of-Squares programming) that can check every single inch of the track to guarantee safety. But as the roller coaster gets bigger, more complex, and has more loops and twists (high-dimensional systems), these old rulebooks break. They try to check every single point, get overwhelmed by the sheer number of possibilities, and give up. This is known as the "curse of dimensionality."

Enter SCORE: The Statistical "Weather Forecaster" for Safety.

The paper you shared introduces a new method called SCORE. Instead of trying to check every point on the track (which is impossible for huge systems), SCORE acts like a smart weather forecaster. It doesn't try to predict the exact weather for every second; instead, it uses statistics to predict the worst-case storm with high confidence.

Here is how SCORE works, broken down into simple analogies:

1. The Problem: The "Needle in a Haystack"

Imagine the roller coaster track is a giant, bumpy mountain range. The "safe" part is the valley where the ride slows down. The "unsafe" part is the peak where the ride might fly off.

Old Methods: Try to measure the height of every single grain of sand on the mountain to find the highest peak. If the mountain is 500 miles wide (500 dimensions), this takes forever and is impossible.
SCORE's Approach: Instead of measuring every grain of sand, SCORE sends out a swarm of tiny, slightly drunk hikers (called PSGLD). These hikers wander around the mountain, but they are biased to climb uphill toward the highest peaks. They don't need to check the whole mountain; they just need to find the highest spots.

2. The Secret Sauce: The "Extreme Value" Trick

Once the hikers find the highest peaks they can, SCORE doesn't just look at the numbers. It uses a branch of math called Extreme Value Theory (EVT).

Think of it like this:

If you roll a die 10 times, you might get a 6.
If you roll it 1,000 times, you'll definitely get a 6.
But if you roll it a million times, what is the absolute highest number you could possibly get?

SCORE treats the safety violations like these dice rolls. It takes the "worst" results found by the hikers (the highest peaks) and groups them into "blocks." It then asks a mathematical question: "Based on the shape of these highest peaks, what is the absolute theoretical limit of how high the mountain could possibly be?"

3. The "Weibull" Safety Net

The paper proves that for these specific types of roller coasters, the "highest peaks" follow a specific mathematical shape called the Weibull distribution.

The Analogy: Imagine a bucket with a lid. No matter how much water you pour in, it can't go higher than the lid.
The Math: The Weibull distribution is like that bucket with a lid. It tells us that there is a finite ceiling to how bad the safety violation can get. Even if we haven't found the exact highest peak yet, the math tells us, "The peak cannot possibly be higher than this specific number."

4. The Result: A Statistical Guarantee

SCORE doesn't say, "I am 100% sure this is safe." Instead, it says:

"I have simulated thousands of scenarios. Based on the statistical patterns of the worst cases I found, I am 99.99% confident that the absolute worst-case safety violation is still negative (meaning the ride is safe)."

Why is this a Big Deal?

The paper tested this on two things:

A small, known problem (2D): It proved that SCORE is just as accurate as the old, slow methods.
A massive, unknown problem (500 dimensions): This is where SCORE shines.
- Old Methods: Gave up immediately. They couldn't handle the complexity of a 500-dimensional system.
- SCORE: Solved it in under 10 minutes.

The Takeaway

Think of SCORE as a shift from being a pedantic accountant (checking every single penny) to being a risk manager (using data to predict the worst-case scenario with high confidence).

By accepting that we can't check everything in a complex, high-dimensional world, SCORE uses smart statistics to find the "ceiling" of danger. If that ceiling is below the safety line, we can certify the system as safe, even if we've never seen every single point in the system. This allows engineers to safely design much larger, more complex, and more powerful systems than ever before.

1. Problem Statement

The core challenge addressed is the certification of the Region of Attraction (ROA) for high-dimensional nonlinear dynamical systems.

Context: Safety-critical control systems require rigorous guarantees that trajectories starting within a specific region will converge to a stable equilibrium (the origin). This is typically proven using Lyapunov functions $V(x)$ , where the condition $\dot{V}(x) < 0$ must hold strictly within the region.
The Bottleneck: Traditional deterministic verification methods, such as Sum-of-Squares (SOS) programming and Satisfiability Modulo Theories (SMT), provide hard guarantees but suffer from the curse of dimensionality.
- SOS faces combinatorial matrix explosions as polynomial degrees increase.
- SMT solvers encounter NP-hard constraint resolution issues, particularly with dense representations like Neural Lyapunov Functions (NLFs).
- Limitation: Existing methods typically fail to scale beyond 20 dimensions, making them inapplicable to modern high-dimensional systems (e.g., dense ODEs with $N=500$ ).

2. Methodology: The SCORE Framework

The authors propose SCORE (Statistical Certification of Regions of Attraction via Extreme Value Theory), a framework that shifts from seeking absolute deterministic guarantees to bounding the worst-case safety violation with high statistical confidence.

A. Problem Reframing

Instead of exhaustively verifying the entire volume of the state space, the problem is reduced to finding the global maximum of the Lyapunov derivative, $\gamma^* = \max_{x \in \mathcal{M}} \dot{V}(x)$ , strictly on the boundary manifold $\mathcal{M}$ defined by the sublevel set $V(x) = \rho$ . If the statistical upper bound of $\gamma^*$ is strictly negative, the region is certified.

B. Core Components

Projected Stochastic Gradient Langevin Dynamics (PSGLD):
- The optimization process is modeled as a stochastic diffusion restricted to the compact manifold $\mathcal{M}$ .
- PSGLD injects Gaussian noise to prevent the optimizer from collapsing into a single local maximum, allowing it to explore the "peaks" of the $\dot{V}(x)$ landscape.
- The process converges to a stationary Gibbs measure.
Extreme Value Theory (EVT) & The Weibull Domain:
- Theoretical Insight: The authors prove that under the assumption of "Projected Quadratic Geometry" (Morse genericity), the local optimality gap of the PSGLD samples follows a scaled Chi-squared distribution.
- Consequence: This implies that the distribution of the maximum values of $\dot{V}(x)$ belongs to the Weibull maximum domain of attraction.
- Significance: The Weibull domain is characterized by a finite right endpoint. This allows the framework to compute a rigorous statistical upper bound on the global maximum of $\dot{V}(x)$ , rather than an unbounded estimate.
The Certification Algorithm:
- Sampling: Run multiple PSGLD chains to collect samples of $\dot{V}(x)$ .
- Block Maxima: Divide samples into blocks and extract the maximum from each block to form an extreme-value dataset.
- Fitting: Fit a Generalized Extreme Value (GEV) distribution (specifically Weibull-type, where shape parameter $\xi < 0$ ) to the block maxima using Maximum Likelihood Estimation (MLE).
- Confidence Bound: Calculate the theoretical upper endpoint ( $z^*$ ) and apply bootstrapping to generate a strict upper confidence interval ( $CI_{upper}$ ).
- Decision: The region is certified if $CI_{upper} < 0$ and the data passes a Kolmogorov-Smirnov (KS) goodness-of-fit test.
Maximal ROA Search:
- A binary search strategy is employed to find the largest sublevel set $\Omega_\rho$ that satisfies the certification condition, leveraging the fact that rejecting an aggressive level set is computationally cheaper than certifying a conservative one.

3. Key Contributions

Novel Statistical Framework: Integration of EVT with PSGLD to reframe ROA certification as a constrained rare-event simulation problem, bypassing deterministic bottlenecks.
Theoretical Guarantee of Boundedness: A rigorous proof demonstrating that the optimization process on a compact manifold places local maxima into the Weibull domain, ensuring a finite statistical upper bound exists.
Unprecedented Scalability: Empirical validation showing the method scales to 500 dimensions, far exceeding the limits of current formal verification pipelines.

4. Experimental Results

The paper validates the method through two primary experiments:

A. Tightness (2D Van der Pol Oscillator)

Benchmark: Compared against exact SOS programming and SMT-based methods (NLF, ICNN, Zubov).
Result: When applied to a high-quality SOS-derived candidate, the SCORE framework certified 83% of the true ROA (compared to 95% for exact SOS).
Insight: This demonstrates that the statistical bound is highly tight and rigorous; the remaining gap is attributed to the candidate function synthesis, not the certification engine itself.

B. Scalability (High-Dimensional ODEs)

Benchmark: A dense, unstructured linear dissipative system with dimensions up to $N=500$ .
Timeout Constraint: 10 minutes per certification task.
Performance:
- SMT/SOS Baselines: Failed completely beyond $N=2$ (for Neural/SMT hybrids) or $N=20$ (for SOS).
- SCORE: Successfully certified the ROA for $N=500$ with 99.99% confidence.
Reason for Success: The method relies on local gradient evaluations via stochastic sampling rather than global algebraic constraint resolution, effectively bypassing combinatorial explosions.

5. Significance and Impact

Bridging the Gap: SCORE addresses the critical gap in verifying high-dimensional, dense, and highly coupled nonlinear systems where sparsity cannot be exploited.
Practical Applicability: By accepting a probabilistic guarantee (e.g., 99.99% confidence) instead of a deterministic one, the framework achieves a computational speedup that makes safety certification feasible for systems previously considered intractable.
Future Directions: The authors identify the need for better Lyapunov candidate synthesis methods (as the current dictionary-based approach can be conservative) and extensions to infinite-dimensional systems (PDEs).

In summary, SCORE represents a paradigm shift in formal verification, trading absolute determinism for statistical rigor to unlock the analysis of complex, high-dimensional dynamical systems essential for modern control engineering.