# Sample Efficient Certification of Discrete-Time Control Barrier Functions

arXiv: https://arxiv.org/abs/2509.03899 · HTML: https://mlsanity.com/paper/2509.03899/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 18 of its 37 references that are in the map.
- First posted on arXiv 4 Sep 2025.

## Builds on (most cited first, 18 of 18)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Intriguing properties of neural networks](https://mlsanity.com/paper/1312.6199/) (2013)
- [Control Barrier Functions: Theory and Applications](https://mlsanity.com/paper/1903.11199/) (2019)
- [On the Effectiveness of Interval Bound Propagation for Training Verifiably Robust Models](https://mlsanity.com/paper/1810.12715/) (2018)
- [Efficient and Accurate Estimation of Lipschitz Constants for Deep Neural Networks](https://mlsanity.com/paper/1906.04893/) (2019)
- [Safe Reinforcement Learning Using Robust Control Barrier Functions](https://mlsanity.com/paper/2110.05415/) (2021)
- [Safety-Critical Model Predictive Control with Discrete-Time Control Barrier Function](https://mlsanity.com/paper/2007.11718/) (2020)
- [Learning Stability Certificates from Data](https://mlsanity.com/paper/2008.05952/) (2020)
- [Predictive control barrier functions: Enhanced safety mechanisms for learning-based control](https://mlsanity.com/paper/2105.10241/) (2021)
- [Exact Verification of ReLU Neural Control Barrier Functions](https://mlsanity.com/paper/2310.09360/) (2023)
- [Verification and Synthesis of Control Barrier Functions](https://mlsanity.com/paper/2104.14001/) (2021)
- [Safe Policy Synthesis in Multi-Agent POMDPs via Discrete-Time Barrier Functions](https://mlsanity.com/paper/1903.07823/) (2019)
- [Verification-Aided Learning of Neural Network Barrier Functions with Termination Guarantees](https://mlsanity.com/paper/2403.07308/) (2024)
- [Safety Verification and Controller Synthesis for Systems with Input Constraints](https://mlsanity.com/paper/2204.09386/) (2022)
- [Compatibility checking of multiple control barrier functions for input constrained systems](https://mlsanity.com/paper/2209.02284/) (2022)
- [Fast Verification of Control Barrier Functions via Linear Programming](https://mlsanity.com/paper/2212.00598/) (2022)
- [Computing Controlled Invariant Sets of Nonlinear Control-Affine Systems](https://mlsanity.com/paper/2304.11757/) (2023)
- [VBOC: Learning the Viability Boundary of a Robot Manipulator using Optimal Control](https://mlsanity.com/paper/2305.07535/) (2023)

## Abstract (arXiv)

Control Invariant (CI) sets are instrumental in certifying the safety of dynamical systems. Control Barrier Functions (CBFs) are effective tools to compute such sets, since the zero sublevel sets of CBFs are CI sets. However, computing CBFs generally involves addressing a complex robust optimization problem, which can be intractable. Scenario-based methods have been proposed to simplify this computation. Then, one needs to verify if the CBF actually satisfies the robust constraints. We present an approach to perform this verification that relies on Lipschitz arguments, and forms the basis of a certification algorithm designed for sample efficiency. Through a numerical example, we validated the efficiency of the proposed procedure.