Probably Approximately Correct (PAC) Guarantees for Data-Driven Reachability Analysis: A Theoretical and Empirical Comparison
This work addresses the need for reliable safety validation in systems using data-driven approaches, but it is incremental as it compares existing methods rather than introducing new ones.
The paper tackles the problem of evaluating system safety through data-driven reachability analysis by comparing PAC guarantees from methods like conformal prediction, scenario optimization, and the holdout method, finding that while they share formal connections, they are not interchangeable due to differences in interpretation and parameterization.
Reachability analysis evaluates system safety, by identifying the set of states a system may evolve within over a finite time horizon. In contrast to model-based reachability analysis, data-driven reachability analysis estimates reachable sets and derives probabilistic guarantees directly from data. Several popular techniques for validating reachable sets -- conformal prediction, scenario optimization, and the holdout method -- admit similar Probably Approximately Correct (PAC) guarantees. We establish a formal connection between these PAC bounds and present an empirical case study on reachable sets to illustrate the computational and sample trade-offs associated with these methods. We argue that despite the formal relationship between these techniques, subtle differences arise in both the interpretation of guarantees and the parameterization. As a result, these methods are not generally interchangeable. We conclude with practical advice on the usage of these methods.