arxiv: 2604.02953 · v1 · submitted 2026-04-03 · 📡 eess.SY · cs.SY

Recognition: 2 theorem links

· Lean Theorem

Probably Approximately Correct (PAC) Guarantees for Data-Driven Reachability Analysis: A Theoretical and Empirical Comparison

Elizabeth Dietrich , Hanna Krasowski , Murat Arcak

Authors on Pith no claims yet

Pith reviewed 2026-05-13 19:36 UTC · model grok-4.3

classification 📡 eess.SY cs.SY

keywords data-driven reachability analysisPAC guaranteesconformal predictionscenario optimizationholdout methodreachable setsprobabilistic safetysystem verification

0 comments

The pith

PAC bounds connect conformal prediction, scenario optimization and holdout for data-driven reachability but reveal they are not interchangeable due to interpretation and parameterization differences.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes a formal connection between the Probably Approximately Correct bounds produced by conformal prediction, scenario optimization, and the holdout method when these are used to certify reachable sets estimated directly from data. A reader would care because these techniques let engineers validate system safety without a full mathematical model, yet the choice of method changes how many samples are needed and how the guarantee is understood. The authors supply both the theoretical mapping and an empirical comparison on reachable-set examples that highlights concrete trade-offs in sample size and computation time. They conclude that the formal relationship does not make the methods equivalent in practice and offer guidance on selecting among them.

Core claim

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.

What carries the argument

The formal mapping between the PAC bounds of conformal prediction, scenario optimization, and the holdout method when applied to data-driven estimation of reachable sets.

If this is right

The three techniques produce formally related but not identical probabilistic statements about reachable-set coverage.
Sample size and runtime requirements differ across the methods for the same target guarantee level.
Interpretation of what the guarantee certifies varies enough that direct substitution of one method for another is not justified.
Practical selection rules can be stated once the differences in parameterization are accounted for.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

When trajectory data are serially correlated rather than i.i.d., blocking or resampling schemes would be needed to restore the validity of any of the three bounds.
The unification suggests that similar PAC comparisons could be carried out for data-driven controller verification or barrier-function synthesis.
For high-dimensional systems the empirical trade-offs may favor one method over the others once computational scaling is measured.

Load-bearing premise

The data samples are independent and identically distributed draws from the underlying system distribution.

What would settle it

A coverage-rate experiment on temporally correlated trajectory data from one long simulation run that shows at least one method falling below its predicted PAC probability while the others do not.

Figures

Figures reproduced from arXiv: 2604.02953 by Elizabeth Dietrich, Hanna Krasowski, Murat Arcak.

**Figure 2.** Figure 2: Distribution of ε’s for the holdout method and empirical conformal prediction over 50 experiments. given the calibration set—an ex ante guarantee. Scenario optimization, provides a bound on the true error of the learned object given the dataset used—an ex post guarantee. V. EMPIRICAL RESULTS The presented equivalence results hold for any set predictions with convex parameterization and can be applied to o… view at source ↗

**Figure 3.** Figure 3: Comparison of conformal prediction and scenario optimization with [PITH_FULL_IMAGE:figures/full_fig_p006_3.png] view at source ↗

read the original abstract

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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper links conformal prediction, scenario optimization, and holdout via formal PAC connections for reachability and uses experiments to show they are not interchangeable, but the i.i.d. assumption needs checking against trajectory data.

read the letter

The core point is that this work maps out how three existing PAC techniques relate for data-driven reachable set estimation and then demonstrates through both theory and a case study that the differences in guarantees and tuning make them non-swappable in practice. That formal connection between the bounds is the new piece, since the individual methods were already known. The empirical part adds value by laying out concrete trade-offs in sample complexity and runtime on reachable sets, which gives practitioners a way to pick among them rather than guessing. They close with usable advice on when to apply each one, which is the sort of thing that saves time in control applications. The math and citation pattern look standard for the area, with no obvious circularity in how the relationships are derived. The main limitation is the shared reliance on i.i.d. samples. Reachability data from dynamical systems often comes from finite trajectories, so temporal correlation is common, and the abstract gives no sign of mixing-time adjustments or other relaxations. If the full proofs and experiments do not address dependence, the coverage claims weaken for the exact use case the paper targets. That said, the central argument still holds up on its own terms for i.i.d. settings. This is a paper for people already working in data-driven safety verification who need to navigate the menu of PAC tools. It is not a breakthrough method but a clarifying comparison that organizes the literature. It deserves peer review because the connection is new enough and the practical guidance is sharp enough to be worth referee time, even if the i.i.d. point requires some revision.

Referee Report

2 major / 0 minor

Summary. The paper claims to establish a formal connection between PAC bounds from conformal prediction, scenario optimization, and the holdout method in the context of data-driven reachability analysis. Through theoretical derivations and an empirical case study on reachable sets, it illustrates computational and sample trade-offs, arguing that subtle differences in guarantee interpretation and parameterization make these methods not generally interchangeable, and provides practical advice on their usage.

Significance. If the formal connections hold and the empirical comparisons are robust, this work is significant for the field of data-driven verification in control systems, as it clarifies the relationships and trade-offs among popular PAC methods, helping researchers and practitioners select appropriate techniques for safety-critical applications.

major comments (2)

The i.i.d. assumption underlying all three PAC guarantees is not relaxed or corrected for temporal correlations in trajectory data from dynamical systems. Since reachability analysis typically involves finite-horizon trajectories that are dependent, the coverage probabilities may not hold at the stated rates, which is load-bearing for the applicability of the formal connection to the motivating use case.
The manuscript does not report error bars or statistical significance for the empirical trade-offs in the case study, making it difficult to assess the reliability of the observed differences in sample and computational requirements.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive comments. We address each major point below and have revised the manuscript accordingly where appropriate.

read point-by-point responses

Referee: The i.i.d. assumption underlying all three PAC guarantees is not relaxed or corrected for temporal correlations in trajectory data from dynamical systems. Since reachability analysis typically involves finite-horizon trajectories that are dependent, the coverage probabilities may not hold at the stated rates, which is load-bearing for the applicability of the formal connection to the motivating use case.

Authors: We agree that the PAC guarantees rely on the i.i.d. assumption, which is standard for conformal prediction, scenario optimization, and the holdout method. The formal connections derived in the paper hold precisely under this assumption. While trajectory data in dynamical systems can exhibit temporal dependence, our focus is on establishing the relationships among the methods under the common i.i.d. setting used in the literature. We will add a dedicated paragraph in the discussion section acknowledging this limitation and outlining possible extensions (e.g., via blocking or mixing conditions), without altering the core theoretical results. revision: partial
Referee: The manuscript does not report error bars or statistical significance for the empirical trade-offs in the case study, making it difficult to assess the reliability of the observed differences in sample and computational requirements.

Authors: We accept this criticism. In the revised manuscript we will augment the empirical section with error bars (standard deviations across repeated trials) on all reported sample-complexity and runtime figures. We will also include a brief statistical comparison (e.g., paired t-tests or confidence intervals) to quantify the significance of the observed differences. revision: yes

Circularity Check

0 steps flagged

No circularity in derivation of PAC connections

full rationale

The paper establishes formal relationships among three pre-existing PAC methods (conformal prediction, scenario optimization, and holdout) for data-driven reachability analysis and illustrates them with a separate empirical case study on reachable sets. No load-bearing step reduces by the paper's own equations or self-citation to a tautological input; the theoretical connections are derived from independent prior results, and the empirical evaluation uses distinct data without fitting parameters that are then renamed as predictions. The derivation chain is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on standard statistical learning assumptions without new free parameters or invented entities.

axioms (1)

domain assumption Samples are drawn i.i.d. from an unknown distribution
This underpins the PAC guarantees for all three methods in data-driven settings.

pith-pipeline@v0.9.0 · 5438 in / 1229 out tokens · 56415 ms · 2026-05-13T19:36:06.156781+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

We establish a formal connection between these PAC bounds... conformal prediction, scenario optimization, and the holdout method admit similar Probably Approximately Correct (PAC) guarantees.
IndisputableMonolith/Foundation/AbsoluteFloorClosure.lean reality_from_one_distinction unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

All three PAC bounds require i.i.d. samples... reachability analysis typically uses finite-horizon state trajectories, which are temporally correlated

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

30 extracted references · 30 canonical work pages · 1 internal anchor

[1]

Data-Driven Reachability Analysis for Gaussian Process State Space Models,

P. Griffioen and M. Arcak, “Data-Driven Reachability Analysis for Gaussian Process State Space Models,” in2023 62nd IEEE Conference on Decision and Control (CDC), 2023, pp. 4100–4105

work page 2023
[2]

Data- Driven Reachability Analysis From Noisy Data,

A. Alanwar, A. Koch, F. Allg ¨ower, and K. H. Johansson, “Data- Driven Reachability Analysis From Noisy Data,”IEEE Transactions on Automatic Control, vol. 68, no. 5, pp. 3054–3069, 2023

work page 2023
[3]

Data-driven Reachability using Christoffel Functions and Conformal Prediction,

A. Tebjou, G. Frehse, and F. Chamroukhi, “Data-driven Reachability using Christoffel Functions and Conformal Prediction,” inProceedings of the Twelfth Symposium on Conformal and Probabilistic Prediction with Applications, ser. Proceedings of Machine Learning Research, vol. 204. PMLR, 13–15 Sep 2023, pp. 194–213

work page 2023
[4]

Formal Verification and Control with Conformal Prediction,

L. Lindemann, Y . Zhao, X. Yu, G. J. Pappas, and J. V . Desh- mukh, “Formal Verification and Control with Conformal Prediction,” arXiv:2409.00536, 2025

work page arXiv 2025
[5]

Nonconvex Scenario Optimization for Data-Driven Reachability,

E. Dietrich, A. Devonport, and M. Arcak, “Nonconvex Scenario Optimization for Data-Driven Reachability,” inProceedings of the 6th Annual Learning for Dynamics & Control Conference, ser. Proceed- ings of Machine Learning Research, vol. 242. PMLR, 15–17 Jul 2024, pp. 514–527

work page 2024
[6]

Verification of neural reachable tubes via scenario optimization and conformal prediction,

A. Lin and S. Bansal, “Verification of neural reachable tubes via scenario optimization and conformal prediction,” inProceedings of the 6th Annual Learning for Dynamics Control Conference, ser. Proceedings of Machine Learning Research, vol. 242. PMLR, 15–17 Jul 2024, pp. 719–731

work page 2024
[7]

Reachability-based safe learning with Gaussian processes,

A. K. Akametalu, J. F. Fisac, J. H. Gillula, S. Kaynama, M. N. Zeilinger, and C. J. Tomlin, “Reachability-based safe learning with Gaussian processes,” in53rd IEEE Conference on Decision and Control, 2014, pp. 1424–1431

work page 2014
[8]

Data- Driven Reachability Analysis of Stochastic Dynamical Systems with Conformal Inference,

N. Hashemi, X. Qin, L. Lindemann, and J. V . Deshmukh, “Data- Driven Reachability Analysis of Stochastic Dynamical Systems with Conformal Inference,” in2023 62nd IEEE Conference on Decision and Control (CDC), 2023, pp. 3102–3109

work page 2023
[9]

Data-Driven Reachability Analysis for Nonlinear Systems,

H. Park, V . Vijay, and I. Hwang, “Data-Driven Reachability Analysis for Nonlinear Systems,”IEEE Control Systems Letters, vol. 8, pp. 2661–2666, 2024

work page 2024
[10]

A theory of the learnable,

L. G. Valiant, “A theory of the learnable,”Commun. ACM, vol. 27, no. 11, p. 1134–1142, Nov. 1984

work page 1984
[11]

A Gentle Introduction to Conformal Prediction and Distribution-Free Uncertainty Quantification

A. N. Angelopoulos and S. Bates, “A gentle introduction to con- formal prediction and distribution-free uncertainty quantification,” arXiv:2107.07511, 2022

work page internal anchor Pith review Pith/arXiv arXiv 2022
[12]

A Tutorial on Conformal Prediction,

G. Shafer and V . V ovk, “A Tutorial on Conformal Prediction,”J. Mach. Learn. Res., vol. 9, p. 371–421, Jun. 2008

work page 2008
[13]

Scenario optimization,

R. S. Dembo, “Scenario optimization,”Annals of Operations Research, vol. 30, pp. 63–80, 1991

work page 1991
[14]

Non-convex scenario optimization,

S. Garatti and M. C. Campi, “Non-convex scenario optimization,” Mathematical Programming, 2024

work page 2024
[15]

M. C. Campi and S. Garatti,Introduction to the Scenario Approach. Society for Industrial and Applied Mathematics, 2018

work page 2018
[16]

A sampling-and-discarding approach to chance-constrained optimization: Feasibility and optimality,

——, “A sampling-and-discarding approach to chance-constrained optimization: Feasibility and optimality,”Journal of Optimization Theory and Applications, vol. 148, no. 2, pp. 257–280, 2011

work page 2011
[17]

Tempo, G

R. Tempo, G. Calafiore, and F. Dabbene,Randomized Algorithms for Analysis and Control of Uncertain Systems: With Applications, 2nd ed. Springer, 2012

work page 2012
[18]

Tutorial on practical prediction theory for classification,

J. Langford, “Tutorial on practical prediction theory for classification,” Journal of Machine Learning Research, vol. 6, pp. 273–306, 2005

work page 2005
[19]

Hastie, R

T. Hastie, R. Tibshirani, and J. Friedman,The Elements of Statistical Learning: Data Mining, Inference, and Prediction, 2nd ed., ser. Springer Series in Statistics. Springer, 2009

work page 2009
[20]

Conditional validity of inductive conformal predictors,

V . V ovk, “Conditional validity of inductive conformal predictors,” inProceedings of the Asian Conference on Machine Learning, ser. Proceedings of Machine Learning Research, vol. 25. PMLR, 04–06 Nov 2012, pp. 475–490

work page 2012
[21]

Bridging conformal prediction and scenario optimization,

N. O’Sullivan, L. Romao, and K. Margellos, “Bridging conformal prediction and scenario optimization,” in2025 IEEE 64th Conference on Decision and Control (CDC), 2025, pp. 6114–6121

work page 2025
[22]

Scenario ap- proach and conformal prediction for verification of unknown systems via data-driven abstractions,

R. Coppola, A. Peruffo, L. Lindemann, and M. Mazo, “Scenario ap- proach and conformal prediction for verification of unknown systems via data-driven abstractions,” inEuropean Control Conference (ECC), 2024, pp. 558–563

work page 2024
[23]

Estimating reachable sets with scenario optimization,

A. Devonport and M. Arcak, “Estimating reachable sets with scenario optimization,” inProceedings of the 2nd Conference on Learning for Dynamics and Control, ser. Proceedings of Machine Learning Research, vol. 120. PMLR, 10–11 Jun 2020, pp. 75–84

work page 2020
[24]

Data-Driven Reachability Analysis with Christoffel Functions,

A. Devonport, F. Yang, L. El Ghaoui, and M. Arcak, “Data-Driven Reachability Analysis with Christoffel Functions,” in2021 60th IEEE Conference on Decision and Control (CDC), 2021, pp. 5067–5072

work page 2021
[25]

arXiv preprint arXiv:2411.11824 , year=

A. N. Angelopoulos, R. F. Barber, and S. Bates, “Theoretical founda- tions of conformal prediction,”arxiv:2411.11824, 2025

work page arXiv 2025
[26]

Hardt and B

M. Hardt and B. Recht,Patterns, predictions, and actions: Foundations of machine learning. Princeton University Press, 2022

work page 2022
[27]

Data-driven reach- ability with scenario optimization and the holdout method,

E. Dietrich, R. Devonport, S. Tu, and M. Arcak, “Data-driven reach- ability with scenario optimization and the holdout method,” in2025 IEEE 64th Conference on Decision and Control (CDC), 2025, pp. 3925–3931

work page 2025
[28]

Post-design verification in the scenario approach,

A. Car `e, M. C. Campi, and S. Garatti, “Post-design verification in the scenario approach,” in2025 IEEE 64th Conference on Decision and Control (CDC), 2025

work page 2025
[29]

Scenario optimization with constraint relaxation in a non-convex setup: A flexible and general framework for data-driven design,

S. Garatti and M. C. Campi, “Scenario optimization with constraint relaxation in a non-convex setup: A flexible and general framework for data-driven design,” in2023 62nd IEEE Conference on Decision and Control (CDC), 2023

work page 2023
[30]

The relationship between the binomial and F dis- tributions,

G. H. Jowett, “The relationship between the binomial and F dis- tributions,”Journal of the Royal Statistical Society. Series D (The Statistician), vol. 13, no. 1, pp. 55–57, 1963

work page 1963