Kernel-Based Learning of Safety Barriers

Oliver Schön, Zhengang Zhong, Sadegh Soudjani

TL;DR

This paper introduces a data-driven framework to verify the safety of "black-box" stochastic systems, such as robots controlled by neural networks. By combining kernel methods with Fourier analysis, the authors transform the mathematically daunting task of finding safety certificates into a scalable linear program that is robust to model uncertainty.

What Problem Does This Paper Address?

As AI is integrated into safety-critical domains like autonomous driving and healthcare, we need formal guarantees that these systems won't fail. Traditional formal verification usually requires a precise mathematical model of the system (a "white-box"). However, modern AI controllers are often "black-boxes," and real-world dynamics are plagued by stochastic noise and unknown variables.

Existing methods to solve this usually fall into two traps:

  1. The Curse of Dimensionality: Methods that partition the world into a grid (abstraction-based) become exponentially slower as the system grows more complex.
  2. Restrictive Assumptions: "Abstraction-free" methods often require the system to be linear or polynomial, which doesn't fit complex neural network controllers.

The authors seek a middle ground: a way to prove safety using only observed data trajectories, without needing a perfect model or oversimplified assumptions.

Methods

The researchers utilize Control Barrier Certificates (CBCs)—mathematical functions that act as a "shield," proving that a system's state will remain within a safe region. To learn these from data, they employ several sophisticated tools:

  • Conditional Mean Embeddings (CMEs): Instead of trying to estimate complex probability densities, they embed the system's transition dynamics into a Reproducing Kernel Hilbert Space (RKHS). This allows them to treat probabilistic expectations as simple linear operations (inner products).
  • RKHS Ambiguity Sets: To handle the fact that data is finite and noisy, they construct a "ball" of possible models around their estimate. This makes the safety guarantee distributionally robust, meaning it holds even if the real system deviates slightly from the training data.
  • Spectral Barrier Solution: This is the paper's "secret sauce." Finding a CBC is usually a "semi-infinite" optimization problem (infinitely many constraints over a continuous space). The authors use a finite Fourier expansion to represent the barrier function. By moving into the frequency domain, they can use the Fast Fourier Transform (FFT) to turn the problem into a standard, solvable Linear Program (LP).

Datasets

The authors evaluated their approach on two primary benchmarks:

  1. Nonlinear Stochastic System: A 2D system (based on the Barr3 benchmark) with added Gaussian noise.
  2. Autonomous Overtaking Scenario: A high-fidelity simulation of a car overtaking another vehicle.
  3. The Controller: A neural network trained via Reinforcement Learning (specifically, the Twin-Delayed Deep Deterministic policy gradient, or TD3).
  4. Data: For both cases, the authors used 1,000 i.i.d. samples (trajectories) collected from the unknown system to "learn" the safety barrier.

Key Insights and Ideas

  • Spectral Abstraction: Much like how JPEG compression uses Fourier transforms to represent images efficiently, the authors use Fourier features to represent safety barriers. This avoids the need for an "exponential number of spatial support vectors," making the method much more memory-efficient for high-dimensional systems.
  • Robustness as a "Safety Margin": By inflating the ambiguity set (the $\epsilon$ radius), the user can trade off the "certified safety probability" for "robustness." A larger $\epsilon$ means the system is safer against unexpected "out-of-distribution" behavior, but the guaranteed probability of success might look lower.
  • Bridging Logic and Control: The paper shows that this isn't just for simple "stay in the lines" safety. By using Streett supermartingales, the framework can be extended to complex temporal logic (e.g., "Always do A, and eventually do B, but never do C").

Key Results

  • Scalability: The Fourier-based approach successfully handled a neural network controller where traditional SMT (Satisfiability Modulo Theories) solvers and global optimizers often struggle or time out.
  • Improved Certification: In the 2D nonlinear benchmark, increasing the richness of the Fourier basis (from 35 to 99 wavenumbers) allowed the authors to increase the certified safety probability from 36.3% to 50.0%.
  • Robustness in Action: In the vehicle overtaking scenario, the empirical safety probability was 53.7%. When they "robustified" the barrier to account for model uncertainty, they could still provide a formal (albeit lower) safety guarantee of 5.07% even under worst-case distribution shifts.

Limitations and Future Work

  • Verification vs. Synthesis: The current method is excellent for verifying if an existing controller is safe. However, synthesizing (creating) a safe controller from scratch is harder because the math becomes non-linear when the control input is unknown.
  • Sample Complexity: While the Fourier approach mitigates the curse of dimensionality for the barrier itself, the number of samples required to provide high-confidence statistical bounds still grows with the system's dimensions.
  • Hyperparameter Tuning: The performance depends on choosing the right kernel lengthscales and the number of Fourier features, which currently requires manual tuning or optimization. The authors suggest "kernel herding" as a potential future fix for computational complexity.

Summary updated

Abstract

The rapid integration of AI algorithms in safety-critical applications such as autonomous driving and healthcare is raising significant concerns about the ability to meet stringent safety standards. Traditional tools for formal safety verification struggle with the black-box nature of AI-driven systems and lack the flexibility needed to scale to the complexity of real-world applications. In this paper, we present a data-driven approach for safety verification and synthesis of black-box systems with discrete-time stochastic dynamics. We employ the concept of control barrier certificates, which can guarantee safety of the system, and learn the certificate directly from a set of system trajectories. We use conditional mean embeddings to embed data from the system into a reproducing kernel Hilbert space (RKHS) and construct an RKHS ambiguity set that can be inflated to robustify the result to out-of-distribution behavior. We provide the theoretical results on how to apply the approach to general classes of temporal logic specifications beyond safety. For the data-driven computation of safety barriers, we leverage a finite Fourier expansion to cast a typically intractable semi-infinite optimization problem as a linear program. The resulting spectral barrier allows us to leverage the fast Fourier transform to generate the relaxed problem efficiently, offering a scalable yet distributionally robust framework for verifying safety. Our work moves beyond restrictive assumptions on system dynamics and uncertainty, as demonstrated on two case studies including a black-box system with a neural network controller.
BibTeX
@misc{schon2026kernel,
  author = {Oliver Schön and Zhengang Zhong and Sadegh Soudjani},
  title = {{Kernel-Based Learning of Safety Barriers}},
  year = {2026},
  eprint = {2601.12002},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2601.12002},
}
Figure