Pith. sign in

REVIEW 5 minor 66 references

On the Limits of Sampling-Based Reachability: Geometry, Dynamics, and Sample Complexity

T0 review · 0 major / 5 minor · reviewed 2026-08-01 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Sampling a reachable set to guaranteed Hausdorff accuracy has sample cost exponential in state dimension and time horizon, and no estimator avoids it.

desk verdict A solid minimax sample-complexity result for Hausdorff-accurate sampling-based reachability; the backward-well-posedness worry is a red herring, but the abstract and the experiments overstate a bit. read the letter →

arxiv 2607.18606 v1 pith:VR7JUWS3 submitted 2026-07-21 cs.RO

Jixian Liu , Ihab Tabbara , Hussein Sibai , Enrique Mallada This is my paper · ORCID
classification cs.RO MSC 93B0362G0562C20
keywords reachabilityanalysissamplecomplexityHausdorffdistancesupportestimationpositivereachLipschitzdynamicsminimaxlowerboundautonomousdynamicalsystems
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper asks how many endpoint samples are needed to approximate the reachable set of an autonomous dynamical system in Hausdorff distance, not just in probability mass. It defines a problem family where the initial set has positive reach, the dynamics are Lipschitz, and sampling density is bounded below, and proves that under these conditions a probability-mass guarantee upgrades to an r-accurate Hausdorff guarantee. The sample complexity is exponential in state dimension and time horizon: roughly (e^{LT}/r)^n trajectories are necessary on some instance, and slightly more, (e^{3LT}/r)^n up to log factors, are sufficient. The lower bound is worst-case over the family, so the exponential scaling is intrinsic to the problem class, not an artifact of any particular estimator. The paper also shows experimentally that adversarial sampling improves constants but cannot change this scaling.

What carries the argument

The load-bearing object is the local endpoint probability lower bound Γ_T(r) = ρ 2^{-n} e^{-3nLT} (r/R)^n, which says every r-ball centered at a reachable point carries at least this much probability mass. It is assembled from three ingredients: positive reach of the initial set's complement gives local volume thickness; L-Lipschitz flow gives bi-Lipschitz distortion and volume preservation up to e^{-nLT}; and the density lower bound converts volume into probability. The upper bound follows by covering the reachable set with r/2-balls and applying a union bound. The lower bound uses two nearly identical admissible instances whose endpoint supports are separated by more than 2r, so any accura

What would settle it

A counterexample would be an admissible instance in the problem family where some r-ball around a reachable point carries less than the promised probability mass Γ_T(r), despite positive reach, Lipschitz dynamics, and uniform density. One can test this by numerically integrating the flow on a contracting system and checking whether inf_y P_T(B_r(y)∩S_T) stays above ρ 2^{-n} e^{-3nLT} (r/R)^n for all r ≤ e^{LT} r0; if it fails, the upper bound overstates the true sample requirement.

Watch

Extended reading notes

Core claim

The central claim is a characterization, matching up to constants in the exponent, of sampling-based reachable-set recovery. For any estimator whose output contains all sampled endpoints, N ≥ c (e^{3LT} R/r)^n (log(...)+log(1/δ)) samples suffice for every point of the true reachable set to lie within r of the estimate, provided the initial complement has positive reach r0, the vector field is L-Lipschitz, and the sampling density is bounded below by ρ/|S0|. Conversely, a minimax lower bound shows that if N < (e^{LT} R/r)^n / (2^{n+1}) log(1/(2δ)), there exists an admissible instance for which every estimator fails with probability > δ. The flow factor e^{nLT} appears because the dynamics dis

Load-bearing premise

The argument needs the time-T flow map to be injective with an e^{LT}-Lipschitz inverse on the reachable set; if backward trajectories from some endpoint fail to exist or uniqueness fails over the horizon, the volume lower bound that anchors the sample-complexity claim can break down.

Editorial extensions

If this is right

  • If the paper is right, any method that promises Hausdorff-accurate reachable-set certificates must spend at least Ω((e^{LT}/r)^n) trajectories on some admissible problem, so high-dimensional safety verification cannot rely on sampling alone.
  • Probability-mass coverage guarantees, the common form of finite-sample reachability results, can be upgraded to geometric accuracy only when local thickness, Lipschitz regularity, and a uniform density lower bound are present; without them a thin low-probability region can be missed while the mass error stays small.
  • The upper bound gives a concrete estimator-agnostic sample budget for inner coverage: for accuracy r, it is sufficient that every r/2-ball centered on the reachable set receives a sample, and the required N is dominated by (e^{3LT} R/(ρ^{1/n} r))^n.
  • Smarter sampling schemes such as adversarial sampling can lower constants and improve finite-sample error, but cannot alter the dimension-dependent exponent.
  • The paper explicitly limits its results to autonomous or closed-loop dynamics; open-loop reachable sets, where reachability is a union over a control set, are outside the scope of the volume-distortion and density-propagation arguments.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • A natural extension of the worst-case bound is an instance-dependent version: the effective exponent should be e^{Λ_T}, where Λ_T is the maximum log volume expansion of the flow over the initial set, so systems whose dynamics contract or preserve volume may require far fewer samples than the worst-case e^{nLT}.
  • For robotic systems with low-dimensional structure, such as manipulators moving near a manifold, the relevant dimension in the r^{-n} factor may be the intrinsic dimension of the uncertainty set rather than the ambient state dimension; this could be tested by measuring sample complexity along the manifold.
  • A concrete testable extension: compute the infimum endpoint local mass γ_T(r) on a given system and check whether the sample requirement tracks 1/γ_T(r) rather than the global worst-case bound; the paper hints at this but does not develop it.
  • The minimax construction uses uniform distributions on two sets differing by a small hole; for non-uniform or strongly adaptive sampling laws the overlap argument would need reworking, so it remains open whether any adaptive law can do more than improve constants.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

0 major / 5 minor

Summary. This paper studies the finite-sample Hausdorff recovery of reachable sets S_T = φ(T, S_0) from N i.i.d. endpoint samples. It defines a problem family F_{R,L,r0,ρ} requiring bounded initial sets of volume ω_n R^n, positive reach of the complement of S_0, L-Lipschitz autonomous dynamics, and a uniform lower bound ρ on the initial sampling density. The main results are: (i) local Lebesgue-mass and endpoint-probability lower bounds (Propositions 1–3, Corollaries 1–2); (ii) an upper bound (Theorem 1) showing that N ≥ 2^{2n} e^{3nLT} R^n/(ρ r^n) [log(2^{3n} e^{nLT} R^n/r^n) + log(1/δ)] samples suffice for r-inner coverage by any estimator containing its samples, with Corollary 3 giving a Hausdorff guarantee under an additional outer-deviation condition; and (iii) a minimax lower bound (Theorem 2) showing that any estimator requires N ≥ e^{nLT} R^n/(2^{n+1} r^n) log(1/(2δ)) samples on some admissible instance. The lower bound uses two punctured-ball initial sets with F(x)=Lx and an overlap/ testing argument. Experiments on a non-Lipschitz 2D example and MuJoCo robot arms illustrate the predicted dimension/horizon scaling.

Significance. If the results are correct, the paper makes a substantial contribution. It converts a previously informal intuition — that probability-mass guarantees do not imply geometric accuracy — into a precise sufficient condition (positive reach plus Lipschitz dynamics plus density lower bound) under which Hausdorff recovery is possible, and it proves that exponential dependence on state dimension and time horizon is not an artifact of a particular algorithm. The lower-bound construction is elegant and satisfies all conditions of the problem family. I specifically checked the flagged concern about Proposition 4: the reverse-time trajectory η_a(s) := φ(T−s, a) is simply the forward trajectory from a evaluated at time T−s, so its existence and uniqueness are already guaranteed by the standing forward well-posedness convention and by L-Lipschitzness of F. No additional backward well-posedness axiom is introduced. The paper provides detailed appendix proofs and reproducible code. The main caveat is that the upper and lower rates differ by a factor e^{2nLT}, so the exact minimax rate is not settled; nevertheless the central qualitative claim is well supported.

minor comments (5)
  1. [Section 2, Definition 2] The condition supp(P0)=S0 is not consistent with the usual measure-theoretic definition of support for an open set, since a measure whose density is positive exactly on an open set has support equal to its closure. Please either define an 'essential support' or write supp(P0)=bar{S0} and adjust Lemma 1 and the statements of S_T accordingly.
  2. [Appendix B.1 / B.4, Prop. 1 and Lemma 2] Proposition 1 is stated for x in S0, but Lemma 2 applies it to centers z_j in a maximal β-separated subset of bar{S0}, which may lie on the boundary. The mass bound does extend to the closure, either by a density/continuity argument or by a rolling-ball argument with the center at distance r0 along the inward normal; please state this explicitly so that the covering-number proof is airtight as written.
  3. [Abstract and Section 6] The upper and lower bounds differ by e^{2nLT}, not merely by constants and logarithmic factors. The phrase 'matching upper- and lower-bound perspectives' in the conclusion should be softened; the paper establishes a sandwich, not an exact minimax rate.
  4. [Throughout] There are several presentation issues: 'an minimax' in the abstract and Section 1; 'And Let R denotes' in Section 1; the proof of Theorem 2 refers to a condition '(B.4)' that is not labeled; Table 2 headings 'Dimension 4/6/8' should be explicitly tied to the state dimension 2n of the n-link arm to avoid confusion.
  5. [Appendix C.3] The fitted relation N ≳ (A_n/r)^{a n^b + c} is based on slopes at only three dimensions (n=2,3,4 links, i.e., state dimensions 4,6,8) and a chosen functional form. It should be described as an empirical trend rather than a tested scaling law, especially because the theoretical bounds leave room for dimension-dependent constants.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the theorem chain is self-contained; the flagged backward-well-posedness concern is resolved by the forward flow convention and standard ODE uniqueness.

full rationale

The paper's derivation is self-contained from explicitly stated assumptions (positive reach reach(S0^c) ≥ r0, L-Lipschitz dynamics, density lower bound ρ/|S0|). Proposition 1 derives a static volume lower bound from [26, Lemma 4.8] (external standard geometry), and Propositions 2–4 propagate it via Gronwall's inequality [56] and the Lipschitz inverse-flow bound, both standard external results. The injectivity claim in Proposition 4 is not an imported uniqueness theorem from the authors: given φ(T,a)=φ(T,b), the curves η_a(s)=φ(T−s,a) and η_b(s)=φ(T−s,b) are two solutions of η' = −F(η) with the same initial value, and uniqueness for Lipschitz ODEs gives a=b. This uses only the paper's standing forward well-posedness convention (φ(t,·) defined and unique for t∈[0,T]) plus standard ODE theory, so the reader-flagged backward-well-posedness gap is not load-bearing. Theorem 1 is a direct random-covering argument driven by Corollary 2; Theorem 2 constructs hard instances (punctured balls propagated by F(x)=Lx) inside the problem family and reduces to binary testing with explicit overlap, not to any fitted or previously assumed target scaling. The e^{nLT}r^{-n} scaling emerges from the construction, and no empirical quantity is fitted and then renamed as a prediction. The experimental log-log slopes in Section C.3 are post-hoc data summaries used for illustration only. Self-citations (e.g., [11], [12], [15]) appear in related-work and experimental context but are not used as proofs or to impose assumptions. The Limitations section honestly restricts claims to autonomous dynamics, which is a scope boundary rather than a circularity.

Assumptions & free parameters 0 free parameters · 9 assumptions · 0 invented entities

The theory rests on standard measure-theoretic tools and the explicitly stated problem-family conditions. The free parameters R, L, r0, ρ are inputs to the problem class, not fitted values. The experimental slope fits (Table 3) are data summaries, not theory inputs. No new physical or mathematical entities are postulated beyond the problem-family definition itself.

assumptions (9)
  • standard math Gronwall's inequality: if v(s) ≤ v(0) + L∫₀ˢ v(σ)dσ then v(s) ≤ v(0)e^{Ls}
    Used in Proposition 4 (Appendix B.3) to show the time-T map is e^{LT}-Lipschitz.
  • standard math Lipschitz maps change Lebesgue volume by at most K^n (Evans [57, Thm 2.8])
    Used to bound |φ(T,A)| ≤ e^{nLT}|A| and to derive |A| ≥ e^{-nLT}|B| in Propositions 4 and 3 (Appendix B.3).
  • standard math Rolling-ball opening property: reach(S0^c) ≥ r0 implies S0 = (S0 ⊖ B_{r0}) ⊕ B_{r0} (Rataj–Zähle [26, Lemma 4.8])
    Basis for the local thickness bound |B_r(x) ∩ S0| ≥ ω_n 2^{-n} r^n in Proposition 1 (Appendix B.1).
  • domain assumption Standing well-posedness: solution φ(t,·) is unique on relevant initial states for t ∈ [0,T]; implicitly requires backward flow existence on S_T for injectivity
    Proposition 4(1) proves injectivity using reverse-time flow; if backward solutions leave X or are non-unique, the volume-distortion lower bound |R_T(A)| ≥ e^{-nLT}|A| can fail, invalidating the upper bound.
  • domain assumption Initial sampling density lower bound p0 ≥ ρ/|S0| with ρ ∈ (0,1]
    Converts the local volume lower bound into a local sampling-probability lower bound (Corollary 1, Proposition 3). Appendix C.3 shows that vanishing density near the boundary destroys uniform coverage.
  • domain assumption Positive reach of the initial complement reach(S0^c) ≥ r0 > 0
    Rules out thin cusps and sharp corners, giving local thickness at all scales ≤ r0. Sharp-cornered boxes in n ≥ 2 have zero reach and are excluded; the robot-arm experiment in C.1 uses a rounded opening of the box to satisfy this.
  • domain assumption F is L-Lipschitz on X
    Needed for the Gronwall/bi-Lipschitz flow estimates and the e^{nLT} degradation factor. The non-Lipschitz example in §5.1 violates this and shows worse-than-exponential scaling.
  • standard math Reach of a separated union (Lemma 4): reach(A∪B) ≥ min(reach(A), reach(B), 1/2 dist(A,B))
    Used in the lower-bound proof (Theorem 2) to verify reach(S0^c) ≥ r0 for the punctured-ball hard instance.
  • standard math Testing lower bound via overlap (Lemma 5): P(ψ=1)+Q(ψ=0) ≥ ∫ min{dP,dQ}
    Used in Theorem 2's minimax reduction to lower-bound the error probability by the overlap of the two candidate endpoint distributions.

how reviews work

0 comments
Cite this review

Pith. "Pith review of On the Limits of Sampling-Based Reachability: Geometry, Dynamics, and Sample Complexity." pith.science (2026). https://pith.science/paper/VR7JUWS3

@misc{pith2026260718606,
  author       = {Pith},
  title        = {Pith review of: On the Limits of Sampling-Based Reachability: Geometry, Dynamics, and Sample Complexity},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/VR7JUWS3}},
  note         = {Machine review of arXiv:2607.18606}
}
abstract

Reachability analysis is central to safety-critical control, robotics, and neural network verification, but classical computational methods, such as Hamilton--Jacobi reachability and set propagation, scale poorly with state dimension. Sampling-based methods have emerged as a promising alternative, often providing finite-sample guarantees that bound the probability-mass left uncovered. However, an explicit account of how the geometry of the initial set, the dynamics, and the sampling law affect the accuracy of the estimator is not fully available in the literature. We study this by casting sampling-based reachable-set recovery as geometric support estimation over a family of problems specified by an initial set, its dynamics, and a sampling law. First, we identify two regularity properties, positive reach of the initial set's complement and Lipschitz continuity of the dynamics, that together make recovery well-posed: a probability-mass coverage guarantee can be upgraded to accuracy $r$ in Hausdorff distance. Second, we bound the resulting sample complexity: recovery is achievable with $\tilde{\mathcal{O}}\big((e^{3LT}/r)^n\big)$ samples, exponential in both the state dimension and the time horizon. Third, we show that neither can be removed: an minimax lower bound of $\Omega\big((e^{LT}/r)^n\big)$ holds for every estimator, so the exponential dependence on dimension and the degradation over the horizon are both intrinsic, not artifacts of a particular method. Experiments on nonlinear systems confirm that adversarial sampling improves constants but not the scaling.

Figures

Figures reproduced from arXiv: 2607.18606 by the authors.

Figure 1
Figure 1. Reachable-set approximation under the autonomous dy [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Hausdorff error versus time for y˙ = 0, x˙ = x 2 and y˙ = 0, x˙ = x using different sampling methods. Solid and dashed curves denote uniform and adversarial sampling. To isolate the effect of flow regularity, we also compare with the Lipschitz linear system y˙ = 0, x˙ = x under the same initial-set configurations [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗
Figure 3
Figure 3. Hausdorff error versus sample size for robot-arm uncer [PITH_FULL_IMAGE:figures/full_fig_p008_3.png] view at source ↗
Figures from the paper (7 more)
Figure 4
Figure 4. Figure 4: Local ball inclusion used in the proof of Proposition [PITH_FULL_IMAGE:figures/full_fig_p015_4.png]
Figure 5
Figure 5. Figure 5: A finite covering of a bounded set. Lemma 2 (Covering number of the reachable set). Let (S0, F, P0) ∈ FR,L,r0,ρ. Then, for every h ∈ (0, eLT r0], N (ST , h) ≤ 2 2ne nLT Rn h n . In particular, N (ST , r/2) ≤ 2 3ne nLT R n rn whenever r ∈ (0, 2e LT r0]. Proof. Since the…
Figure 6
Figure 6. Figure 6: Reachable-set approximation error for sampling distributions with the same support but [PITH_FULL_IMAGE:figures/full_fig_p030_6.png]
Figure 7
Figure 7. Figure 7: Fitted dimension-dependent empirical slopes for robot-arm uncertainty propagation. The [PITH_FULL_IMAGE:figures/full_fig_p031_7.png]
Figure 8
Figure 8. Figure 8: Hausdorff error versus time under uniform sampling [PITH_FULL_IMAGE:figures/full_fig_p033_8.png]
Figure 9
Figure 9. Figure 9: Hausdorff error versus time for Convexhull reachable-set approximation of the au [PITH_FULL_IMAGE:figures/full_fig_p034_9.png]
Figure 10
Figure 10. Figure 10: Hausdorff error versus time for Christoffel reachable-set approximation of the au [PITH_FULL_IMAGE:figures/full_fig_p035_10.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

66 extracted references · 2 linked inside Pith

  1. [1]

    P. D. Holmes, S. Kousik, B. Zhang, D. Raz, C. Barbalata, M. Johnson-Roberson, and R. Va- sudevan. Reachable sets for safe, real-time manipulator trajectory design. InProceedings of Robotics: Science and Systems, 2020

    2020

  2. [2]

    Y . Meng, D. Sun, Z. Qiu, M. T. B. Waez, and C. Fan. Learning density distribution of reachable states for autonomous systems. InConference on Robot Learning, pages 124–136. PMLR, 2022

    2022

  3. [3]

    Ivanov, T

    R. Ivanov, T. Carpenter, J. Weimer, R. Alur, G. Pappas, and I. Lee. Verisig 2.0: Verification of neural network controllers using taylor model preconditioning. InInternational Conference on Computer Aided Verification, pages 249–262. Springer, 2021

    2021

  4. [4]

    J. Wu, H. Zhang, and Y . V orobeychik. Verified safe reinforcement learning for neural network dynamic models.Advances in Neural Information Processing Systems, 37:117762–117783, 2024

    2024

  5. [5]

    Bansal, M

    S. Bansal, M. Chen, S. Herbert, and C. J. Tomlin. Hamilton-jacobi reachability: A brief overview and recent advances. In2017 IEEE 56th annual conference on decision and control (CDC), pages 2242–2253. IEEE, 2017

    2017

  6. [6]

    Chen and C

    M. Chen and C. J. Tomlin. Hamilton–jacobi reachability: Some recent theoretical advances and applications in unmanned airspace management.Annual Review of Control, Robotics, and Autonomous Systems, 1(1):333–358, 2018

    2018

  7. [7]

    A. Girard. Reachability of uncertain linear systems using zonotopes. InHybrid Systems: Computation and Control, 2005

    2005

  8. [8]

    A. B. Kurzhanski and P. Varaiya. Ellipsoidal techniques for reachability analysis. InHybrid Systems: Computation and Control, 2000

    2000

Show all 66 references
  1. [9]

    Selim, A

    M. Selim, A. Alanwar, S. Kousik, G. Gao, M. Pavone, and K. H. Johansson. Safe reinforcement learning using black-box reachability analysis.IEEE Robotics and Automation Letters, 7(4): 10665–10672, 2022

    2022

  2. [10]

    Ganai, Z

    M. Ganai, Z. Gong, C. Yu, S. Herbert, and S. Gao. Iterative reachability estimation for safe re- inforcement learning.Advances in Neural Information Processing Systems, 36:69764–69797, 2023

    2023

  3. [11]

    Liu and E

    J. Liu and E. Mallada. Recurrent control barrier functions: A path towards nonparametric safety verification. In2025 IEEE 64th Conference on Decision and Control (CDC), pages 7721–7727. IEEE, 2025

    2025

  4. [12]

    Ouyang, J

    Z. Ouyang, J. Liu, and E. Mallada. Symplectic inductive bias for data-driven target reachability in hamiltonian systems.arXiv preprint arXiv:2604.17213, 2026

    2026 arXiv

  5. [13]

    Williams, P

    G. Williams, P. Drews, B. Goldfain, J. M. Rehg, and E. A. Theodorou. Information-theoretic model predictive control: Theory and applications to autonomous driving.IEEE Transactions on Robotics, 34(6):1603–1622, 2018

    2018

  6. [14]

    C. Pan, Z. Yi, G. Shi, and G. Qu. Sampling-based methods for optimal control: Theory, algorithms, and applications. In2025 IEEE 64th Conference on Decision and Control (CDC), pages 3775–3793. IEEE, 2025. 9

    2025

  7. [15]

    Castellano, S

    A. Castellano, S. Pan, and E. Mallada. Data-driven acceleration of mpc with guarantees.arXiv preprint arXiv:2511.13588, 2025

    2025 arXiv

  8. [16]

    Liebenwein, C

    L. Liebenwein, C. Baykal, I. Gilitschenski, S. Karaman, and D. Rus. Sampling-based ap- proximation algorithms for reachability analysis with provable guarantees. InProceedings of Robotics: Science and Systems, 2018

    2018

  9. [17]

    Devonport, F

    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), pages 5067–5072. IEEE, 2021

    2021

  10. [18]

    Devonport, F

    A. Devonport, F. Yang, L. El Ghaoui, and M. Arcak. Data-driven reachability and support estimation with christoffel functions.IEEE Transactions on Automatic Control, 68(9):5216– 5229, 2023

    2023

  11. [19]

    Lew and M

    T. Lew and M. Pavone. Sampling-based reachability analysis: A random set theory approach with adversarial sampling. InConference on Robot Learning, pages 2055–2070. PMLR, 2021

  12. [20]

    T. Lew, L. Janson, R. Bonalli, and M. Pavone. A simple and efficient sampling-based algorithm for general reachability analysis. InLearning for Dynamics and Control Conference, pages 1086–1099. PMLR, 2022

    2022

  13. [21]

    Devroye and G

    L. Devroye and G. L. Wise. Detection of abnormal behavior via nonparametric estimation of the support.SIAM Journal on Applied Mathematics, 38(3):480–488, 1980

    1980

  14. [22]

    A. Cuevas. Set estimation: Another bridge between statistics and geometry.Bolet ´ın de Es- tad´ıstica e Investigaci´on Operativa, 25(2):71–85, 2009

    2009

  15. [23]

    A. P. Korostelev and A. B. Tsybakov.Minimax Theory of Image Reconstruction, volume 82 of Lecture Notes in Statistics. Springer, New York, 1993

    1993

  16. [24]

    Arias-Castro, B

    E. Arias-Castro, B. Pateiro-L ´opez, and A. Rodr´ıguez-Casal. Minimax estimation of the volume of a set under the rolling ball condition.Journal of the American Statistical Association, 114 (527):1162–1173, 2019

    2019

  17. [25]

    H. Federer. Curvature measures.Transactions of the American Mathematical Society, 93(3): 418–491, 1959

    1959

  18. [26]

    Rataj and M

    J. Rataj and M. Z ¨ahle.Curvature measures of singular sets. Springer, 2019

    2019

  19. [27]

    Raissi, P

    M. Raissi, P. Perdikaris, and G. E. Karniadakis. Physics-informed neural networks: A deep learning framework for solving forward and inverse problems involving nonlinear partial dif- ferential equations.Journal of Computational physics, 378:686–707, 2019

    2019

  20. [28]

    Duong and N

    T. Duong and N. Atanasov. Hamiltonian-based neural ode networks on the se(3) manifold for dynamics learning and control. InProceedings of Robotics: Science and Systems, July 2021

    2021

  21. [29]

    Singh, B

    S. Singh, B. Landry, A. Majumdar, J.-J. Slotine, and M. Pavone. Robust feedback motion planning via contraction theory.The International Journal of Robotics Research, 42(9):655– 688, 2023

    2023

  22. [30]

    Greydanus, M

    S. Greydanus, M. Dzamba, and J. Yosinski. Hamiltonian neural networks.Advances in neural information processing systems, 32, 2019

    2019

  23. [31]

    Djeumou, C

    F. Djeumou, C. Neary, and U. Topcu. How to learn and generalize from three minutes of data: Physics-constrained and uncertainty-aware neural stochastic differential equations. In Proceedings of The 7th Conference on Robot Learning, pages 577–601. PMLR, 2023

    2023

  24. [32]

    G. C. Calafiore and M. C. Campi. The scenario approach to robust control design.IEEE Transactions on Automatic Control, 51(5):742–753, 2006. 10

    2006

  25. [33]

    M. C. Campi and S. Garatti. The exact feasibility of randomized solutions of uncertain convex programs.SIAM Journal on Optimization, 19(3):1211–1230, 2008

    2008

  26. [34]

    Devonport and M

    A. Devonport and M. Arcak. Estimating reachable sets with scenario optimization. InProceed- ings of the 2nd Conference on Learning for Dynamics and Control, volume 120 ofProceedings of Machine Learning Research, pages 75–84. PMLR, 2020

    2020

  27. [35]

    Dietrich, R

    E. Dietrich, R. Devonport, S. Tu, and M. Arcak. Data-driven reachability with scenario op- timization and the holdout method. In2025 IEEE 64th Conference on Decision and Control (CDC), pages 3925–3931. IEEE, 2025

    2025

  28. [36]

    Sartipizadeh, A

    H. Sartipizadeh, A. P. Vinod, B. Ac ¸ikmes ¸e, and M. Oishi. V oronoi partition-based scenario reduction for fast sampling-based stochastic reachability computation of linear systems. In 2019 American Control Conference (ACC), pages 37–44. IEEE, 2019

    2019

  29. [37]

    Dietrich, A

    E. Dietrich, A. Devonport, and M. Arcak. Nonconvex scenario optimization for data-driven reachability. In6th Annual Learning for Dynamics & Control Conference, pages 514–527. PMLR, 2024

    2024

  30. [38]

    Hewing and M

    L. Hewing and M. N. Zeilinger. Scenario-based probabilistic reachable sets for recursively feasible stochastic model predictive control.IEEE Control Systems Letters, 4(2):450–455, 2019

    2019

  31. [39]

    S. Dean, N. Matni, B. Recht, and V . Ye. Robust guarantees for perception-based control. In Proceedings of the 2nd Annual Conference on Learning for Dynamics and Control, volume 120 ofProceedings of Machine Learning Research, pages 350–360. PMLR, 2020

    2020

  32. [40]

    C. Fan, B. Qi, S. Mitra, and M. Viswanathan. DryVR: Data-driven verification and compo- sitional reasoning for automotive systems. InComputer Aided Verification, pages 441–461. Springer, 2017

    2017

  33. [41]

    S. A. Gruenbacher, M. Lechner, R. Hasani, D. Rus, T. A. Henzinger, S. A. Smolka, and R. Grosu. Gotube: Scalable statistical verification of continuous-depth models. InProceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 6755–6764, 2022

    2022

  34. [42]

    R. T. Q. Chen, Y . Rubanova, J. Bettencourt, and D. K. Duvenaud. Neural ordinary differential equations. InAdvances in Neural Information Processing Systems, volume 31, 2018

    2018

  35. [43]

    Fazlyab, A

    M. Fazlyab, A. Robey, H. Hassani, M. Morari, and G. J. Pappas. Efficient and accurate es- timation of lipschitz constants for deep neural networks. InAdvances in Neural Information Processing Systems, volume 32, 2019

    2019

  36. [44]

    Latorre, P

    F. Latorre, P. Rolland, and V . Cevher. Lipschitz constant estimation of neural networks via sparse polynomial optimization. InInternational Conference on Learning Representations, 2020

    2020

  37. [45]

    Shafer and V

    G. Shafer and V . V ovk. A tutorial on conformal prediction.Journal of Machine Learning Research, 9:371–421, 2008

    2008

  38. [46]

    Lindemann, Y

    L. Lindemann, Y . Zhao, X. Yu, G. J. Pappas, and J. V . Deshmukh. Formal verification and control with conformal prediction: Practical safety guarantees for autonomous systems.IEEE Control Systems, 45(6):72–122, 2025

    2025

  39. [47]

    Z. Mei, A. Dixit, M. Booker, E. Zhou, M. Storey-Matsutani, A. Z. Ren, O. Shorinwa, and A. Majumdar. Perceive with confidence: Statistical safety assurances for navigation with learning-based perception.The International Journal of Robotics Research, 45(6):938–967, 2026. 11

    2026

  40. [48]

    J. Yao, X. Zhang, Y . Xia, Z. Wang, A. Roy-Chowdhury, and J. Li. Towards generalizable safety in crowd navigation via conformal uncertainty handling. In9th Annual Conference on Robot Learning, 2025

    2025

  41. [49]

    Tabbara, Y

    I. Tabbara, Y . Yang, and H. Sibai. Statistically assuring safety of control systems using ensem- bles of safety filters and conformal prediction.arXiv preprint arXiv:2511.07899, 2025

    2025

  42. [50]

    Lindemann, M

    L. Lindemann, M. Cleaveland, G. Shim, and G. J. Pappas. Safe planning in dynamic environ- ments using conformal prediction.IEEE Robotics and Automation Letters, 8(8):5116–5123, 2023

    2023

  43. [51]

    Tebjou, G

    A. Tebjou, G. Frehse, and F. Chamroukhi. Data-driven reachability using christoffel func- tions and conformal prediction. InProceedings of the Twelfth Symposium on Conformal and Probabilistic Prediction with Applications, volume 204 ofProceedings of Machine Learning Research, ...

    2023

  44. [52]

    Bansal and C

    S. Bansal and C. J. Tomlin. Deepreach: A deep learning approach to high-dimensional reach- ability. In2021 IEEE International Conference on Robotics and Automation (ICRA), pages 1817–1824. IEEE, 2021

    2021

  45. [53]

    Lin and S

    A. Lin and S. Bansal. Verification of neural reachable tubes via scenario optimization and conformal prediction. In6th Annual Learning for Dynamics & Control Conference, pages 719–731. PMLR, 2024

    2024

  46. [54]

    Hashemi, X

    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), pages 3102–3109. IEEE, 2023

    2023

  47. [55]

    Hashemi, L

    N. Hashemi, L. Lindemann, and J. V . Deshmukh. Pca-ddreach: Efficient statistical reachability analysis of stochastic dynamical systems via principal component analysis. InProceedings of the International Conference on Neuro-symbolic Systems, volume 288, pages 693–707. PMLR, 2025

    2025

  48. [56]

    Bullo.Contraction Theory for Dynamical Systems

    F. Bullo.Contraction Theory for Dynamical Systems. Kindle Direct Publishing, 1.2 edition,

  49. [57]

    L. C. Evans.Measure theory and fine properties of functions. Chapman and Hall/CRC, 2025

    2025

  50. [58]

    Goodfellow, J

    I. Goodfellow, J. Shlens, and C. Szegedy. Explaining and harnessing adversarial examples. In International Conference on Learning Representations, 2015

    2015

  51. [59]

    Y . Dong, F. Liao, T. Pang, H. Su, J. Zhu, X. Hu, and J. Li. Boosting adversarial attacks with momentum. InProceedings of the IEEE conference on computer vision and pattern recognition, pages 9185–9193, 2018

    2018

  52. [60]

    Rodriguez-Casal and P

    A. Rodriguez-Casal and P. Saavedra-Nieves. A data-adaptive method for estimating density level sets under shape conditions.The Annals of Statistics, 50(3):1653–1668, 2022. 12 Appendix The Appendix is organized as follows. Section A provides additional related work on sampling-...

    2022

  53. [62]

    the mapx7→φ(T, x)from S0 to ST is injective; 16

  54. [63]

    for all x, y∈ S0,∥φ(T, x)−φ(T, y)∥ ≤eLT ∥x−y∥

  55. [64]

    for all x, y∈ S0,∥φ(T, x)−φ(T, y)∥ ≥e−LT ∥x−y∥, equivalently, the inverse mapφ(T,·) −1 : ST → S0 ise LT -Lipschitz

  56. [65]

    First, we prove the upper Lipschitz bound

    for every Lebesgue measurable set A⊆ S0,|R T (A)| ≥e−nLT |A|.(3) Proof of Proposition 4.We prove the four claims in such an order: 2→1→3→4. First, we prove the upper Lipschitz bound. Fixx, y∈ S0. Since(S 0, F, P0)∈ FR,L,r0,ρ, the vector fieldFis L-Lipschitz onX. Hence, for all...

  57. [66]

    Hence sup ℓ∈{0,1} (P (ℓ) T )N dH ( bSN , S(ℓ) T )> r ≥ 1 2 exp −2N h R n = 1 2 exp −2N(2 +α) ne−nLT r R n

    Usinglog(1−u)≥ −2u,0≤u≤ 1 2, we obtain 1− h R n N = exp Nlog 1− h R n ≥exp −2N h R n . Hence sup ℓ∈{0,1} (P (ℓ) T )N dH ( bSN , S(ℓ) T )> r ≥ 1 2 exp −2N h R n = 1 2 exp −2N(2 +α) ne−nLT r R n . By (B.4),2N(2 +α) ne−nLT r R n <log 1 2δ . Therefore, sup ℓ∈{0,1} (P (ℓ) T )N dH (...

  58. [2024]

    URLhttps://fbullo.github.io/ctds

    ISBN 979-8836646806. URLhttps://fbullo.github.io/ctds

Pith tools

Reviewed August 1, 2026 · model on record in the stance chip above.