CS Paper Radar

Fundamental Limits of Sampling-Based Reachability: Geometry and Flow Distortion

Jixian Liu, Ihab Tabbara, Hussein Sibai, Enrique Mallada

eess.SY cs.RO ·submitted 2026-10-29 17:08 UTC · v1
theorycode/data

Abstract

Sampling-based reachability estimates reachable sets from finitely many simulated trajectory endpoints. Existing guarantees often control missed probability mass or approximation error relative to the convex hull of the reachable set, leaving the geometric error relative to the reachable set incompletely characterized. We study this error as a problem of support estimation under flow distortion. Our assumptions combine a uniform lower bound on the local volume density of the initial set, a lower bound on the sampling density, and a one-sided Lipschitz constant $μ$ for the vector field. These conditions admit initial sets with corners and dynamics that may expand or contract. In the fine-accuracy regime, $\tilde{\mathcal O}\bigl(2^ne^{nμT}(R/r)^n/(ρκ)\bigr)$ independent endpoint samples suffice for Hausdorff accuracy $r$ using the endpoint cloud. Here, $n$ is the state dimension, $T$ is the horizon, $R$ is the volume-equivalent radius, and $ρ$ and $κ$ quantify sampling density and local volume density. For $n\ge2$ and sufficiently small $κ$, a minimax lower bound over all estimators based only on independent endpoints matches these dependencies up to a dimension-dependent factor $2\cdot4^n$ and logarithmic factors, within the stated parameter range and when the state domain accommodates the construction. The exponential burden in dimension, and in the horizon for expanding systems, is therefore intrinsic to this observation model. Planar experiments illustrate the predicted effects of corners and contraction; robot-arm experiments show how empirical accuracy deteriorates with dimension.

Comment
16 pages, 9 figures, 3 tables. Extended version of the CoRL 2026 paper; submitted to IEEE Transactions on Automatic Control. Code: https://github.com/JeanLew01/reachapprox

Closest papers

Nearest neighbours by meaning across the whole index.

Estimating the Volume of a Union of Convex Bodies

cs.DS ·2026-11-04 ·Eeshan Banerjee, Aranya Kumar Bal, Debabrota Basu, Sourav Chakraborty, Debarshi Chanda +1 more
similarity 0.61
Abstract

The \textit{Union Volume Estimation problem}, i.e. yielding an $(\varepsilon, δ)$-approximation of the volume of the union of convex bodies, is a classical problem in computational geometry and formal methods. In this paper, we first detect where and why the efficient union volume estimators with approximate sampling and PAC volume estimation oracles fail. Specifically, we show that having only TV-distance guarantees on the approximate sampler does not suffice, and demonstrate this bottleneck by constructing the sunflower families of convex bodies. In this context, we propose the concept of \textit{tail-controlled samplers} that can yield with high-probability almost-$\ell_{\infty}$ closeness. Secondly, we leverage this concept to propose a generic algorithmic framework \texttt{Alpona} that properly combines a PAC volume computation and approximate point sampling oracles with tail-controls to yield an $(\varepsilon, δ)$-estimate of the union volume for any collection of convex bodies. We show that \texttt{Alpona} needs only linear (in number of convex bodies) oracle calls to be $(\varepsilon, δ)$-correct. Finally, we provide a tail-controlled analysis of the Hit-and-Run sampler~\citep{lovasz2006fast}. We further provide a novel geometric analysis to improve the required walk length of Hit-and-Run. We further instantiate \texttt{Alpona}'s correctness for the sparse frequency streams of convex bodies: a special case of the union volume estimation problem where no convex body intersects more than $τ$ many other bodies.

0.10

Particle Dynamics of Flow Matching and Classifier-Free Guidance from a Stagewise Geometry Perspective

cs.LG ·2026-09-07 ·Jian-Feng Cai, Zhengyi Su, Chao Wang
similarity 0.59
Abstract · 78 pages, 14 figures

Flow matching, together with classifier-free guidance (CFG), is widely used in generative modeling, yet much of the theoretical understanding remains distribution-wise. Since practical sampling follows individual trajectories, distribution-level guarantees alone do not fully capture how trajectories interact with the data geometry or how guidance reshapes it. To overcome this limitation, we establish a unified stagewise geometric theory of attraction and absorption for both continuous dynamics and explicit Euler discretization. Specifically, with $t\in[0,1]$ running from noise to data, we show that unconditional flow trajectories are successively attracted toward a neighborhood of the global mean, the data convex hull, and a neighborhood of a possibly nonconvex local cluster. Across these stages, the corresponding distance satisfies a common contraction estimate, yielding an ${O}(1-t)$ decay of the distance in the final stage. For CFG, the same structure persists with an extrapolated mean, an inflated conditional convex hull, and, near the target cluster, the restored local geometry of conditional flow matching. We further show that a general time schedule $a(t)$ replaces the $O(1-t)$ decay by $O(1-a(t))$. Together, these results provide a unified particle-level geometric account of flow matching and CFG across continuous and discrete sampling.

0.42

Sampling Design and Confidence Tubes for Integral Curves on Riemannian Manifolds

cs.LG stat.ML ·2026-10-31 ·Xiaotian Chang, Qirui Hu, Cyrus Mostajeran
theory similarity 0.57
Abstract

We estimate the integral curve of an unknown vector field from noisy tangent vector field on a known compact Riemannian manifold. We consider two sampling settings: independent observations at random locations that have already been collected, and a fixed response budget that allows subsequent locations to be chosen using pilot information. Under suitable regularity assumptions, the passive kernel estimator has curve error of order $n^{-2/(d+3)}$ in probability, with sample size $n$ and manifold dimension $d$. Its functional central limit theorem has a limit characterized by a linear stochastic differential equation. For active sampling, an independent pilot directs one new batch of measurements to neighborhoods of the target curve. Under localization, smoothness and design conditions, this concentration yields expected maximum curve error of order $N^{-1/2}$, including the pilot in the total response budget $N$. Both methods provide simultaneous geodesic confidence tubes with asymptotically exact coverage under mild conditions. Simulations show narrower active tubes in most reported settings, with improved small-sample coverage in some three-dimensional examples. Ocean-drifter observations illustrate mean-flow reconstruction on the sphere, and a canopy-flow LDA application uses retrospective active sampling to quantify lateral and vertical departures of local mean streamlines.

0.28

ConicFlow: constrained Inference-time optimal control for flow matching models

cs.AI cs.CVcs.LGeess.SY ·2026-10-09 ·Shervin Khalafi, Kasra Fallah, Sung Cho, Dongsheng Ding, James Anderson +1 more
similarity 0.57
Abstract

We propose ConicFlow, which frames constrained sampling from a flow matching model at inference time as an optimal control problem that balances deviation from the pretrained trajectory against reward, subject to hard terminal constraints. We discretize this problem and adapt receding-horizon control, optimizing only a short window of the trajectory at each step for computational tractability. We address the resulting sequence of receding-horizon subproblems with a receding-horizon primal-dual algorithm. Its dual multipliers capture the difficulty of satisfying each constraint and are refined throughout sampling, steering generation toward feasible final samples. We further propose a terminal-estimate variant that avoids accumulating local truncation errors by evaluating the reward and constraints at the predicted terminal point rather than at the end of the current horizon. Under standard regularity assumptions, we establish finite-horizon guarantees on suboptimality. Under convex-affine structure, we derive a sharper bound that scales linearly with omitted horizon length, and we show that the terminal-estimate variant is provably tighter when the flow dynamics change slowly. Experiments in both low- and high-dimensional settings with a recent large-scale flow matching model show that ConicFlow achieves high reward and strong constraint satisfaction while deviating less from the pretrained flow than recent baselines.

0.23

Near-Linear Accuracy Bounds for Moreau--Yosida Unadjusted Langevin Sampling

cs.LG ·2026-09-30 ·Yuchen Xin, Zhihua Zhang
similarity 0.56
Abstract

We establish near-linear accuracy bounds for the classical Moreau--Yosida unadjusted Langevin algorithm (MYULA). The target is $π\propto e^{-f-g}$, where $f\in C^2(\mathbb{R}^d)$ is $m$-strongly convex with Lipschitz gradient and $g$ is convex and globally Lipschitz. Under an explicit parameter-dependent step-size condition, we bound the invariant-measure bias relative to the Moreau-smoothed target by $\widetilde O(h)$, with only logarithmic dependence on the inverse smoothing parameter in the error coefficient. Combining this estimate with the Moreau approximation bias and Wasserstein contraction gives $\widetilde O(\varepsilon^{-1})$ iterations to make the $N$th-iterate law $μ_N$ satisfy $\sqrt m\,W_2(μ_N,π)\le\varepsilon$, for fixed model parameters and initialization. We bound the stationary error directly, without assuming third derivatives or a Lipschitz Hessian. Each iteration uses one gradient evaluation and one exact proximal evaluation. The key idea in our analysis is to convert a second-order stationary residual into a Wasserstein bound using a Poisson-based estimate.

0.07

Sampling and Curvature in First-Exit Comparisons for Momentum SGD

cs.LG ·2026-10-18 ·Haiyi Li
similarity 0.56
Abstract · 84 pages, including references and appendices

First-exit prediction for momentum SGD depends on sampling information that pointwise gradient laws omit. Strongly convex finite pools with identical pointwise laws and matched iid momentum dynamics can have different reshuffled exits; even analytic pools with uniformly close pointwise laws can have separated exit probabilities. For persistent sampling in one dimension, we establish an explicit $O(h)$ mean-exit comparison with a finite-rate switching process under nonvanishing component velocities and step-size conditions; iid sampling instead averages to an ODE. Retaining realized minibatches and sampled curvature yields finite-window exit brackets beyond this regime. In 32 trained ridge-logistic runs, 29 meet prespecified targets with rounding-certified brackets; an enclosure control explains most of the width advantage. Exact-real certificates establish finite means at the original tested radii for three ResNet-18 checkpoints and give local finite-mean conditions for tanh and ViT networks; their upper bounds remain loose, and original-radius ViT mean guarantees remain unresolved despite 128 fresh continuation paths. A two-network replication gives 32/32 successful seeds in each of four finite-path persistence comparisons. Independent equal-length controls retain slower exits after refresh resets than without resets, but the refresh-versus-random ordering reverses with update length at both networks. These interventions do not causally decompose raw momentum SGD. Neural step-size scaling does not validate the switching limit.

0.31

Displacement Moments and Path-Terminal Separation in Brownian Interpolant Sampling

cs.LG math.PR ·2026-10-27 ·Zhong Han
theory similarity 0.55
Abstract · 51 pages, 2 figures, including an 8-page main text. Revised exposition and streamlined appendices

We prove early-stopped, target-to-output KL guarantees for Brownian interpolant Euler sampling from the true source under arbitrary Borel couplings, even with nonintegrable endpoints. At fixed stopping time and noise level, a fourth displacement moment yields an $O(N^{-1})$ discretization term. A second moment suffices for fixed-law convergence with grid refinement and vanishing drift error. For one fixed coupling with no displacement moment above two, the original and comparison paths have KL of orders one and $1/\log N$ relative to the exact-drift Euler path. On the same geometric grid, terminal KL is at most $C/N^2$. The path decomposition identifies the information about the source discarded by Markov projection. When the original bridge is Markov, current-state Euler sampling has an $O((M_2+d)/N)$ discretization term. We prove expected stopped-output KL consistency for a learner trained on iid endpoint pairs with fresh true-source initialization. In a spatial image control, iterative sampling has worse fair energy scores than direct prediction with resampled residuals. Uniform terminal rates for general second-moment couplings remain open.

0.29

Conformal Prediction Regions for Continuous-Time Trajectories under Random Sampling

eess.SY ·2026-08-30 ·Joaquin Alvarez, Matteo Sesia, Jyotirmoy V. Deshmukh, Lars Lindemann
similarity 0.55
Abstract

Uncertainty quantification for continuous-time trajectories is a prerequisite in many safety-critical engineering domains. However, a major challenge in data-driven uncertainty quantification is that calibration trajectories are sampled only at discrete, often sparse, and random intervals. Standard conformal prediction methods typically fail to provide guarantees in between sampling times. In this work, we introduce a new technique to obtain valid conformal prediction regions for continuous-time trajectories that are sampled at discrete and possibly random times. To accomplish this goal, we make three contributions: (1) we provide an algorithm that leverages regularity properties of the underlying trajectories to obtain valid prediction regions in between samples, (2) we provide methods that estimate valid bounds on the aforementioned regularity properties from an additional high-frequency calibration dataset, and (3) we introduce and compare several algorithms to deal with random sampling times. Finally, we present experiments where we validate that our methods achieve valid coverage across the entire continuous trajectory.

0.26