Efficient Uncertainty Propagation with Guarantees in Wasserstein Distance

Eduardo Figueiredo ∗,1 , Steven Adams ∗,1 , Peyman Mohajerin Esfahani 1,2 , Luca Laurenti 1 · 2025

Read Efficient Uncertainty Propagation with Guarantees in Wasserstein Distance by Eduardo Figueiredo ∗,1 , Steven Adams ∗,1 , Peyman Mohajerin Esfahani 1,2 , Luca Laurenti 1 (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-08689.txt.

Introduction

Eduardo Figueiredo and co-authors give, in a 2025 paper, a fast way to push doubt through a curved map with a proof of the error size. The doubt is a spread of odds, scored by the Wasserstein gap. Start with a set of close-in spreads. The aim is a new set, built round a grid spread, that is sure to hold the push of any start spread. The trick: swap one start spread for a grid form whose push can be found in full. Semi-discrete transport and robust math then bound the slip.

For any set error bar, the slip can be made less. For live systems, the spread can be tracked for all time at grid form. Tests reach a 10-part bent system.

Catalog record

CREATOREduardo Figueiredo ∗,1 , Steven Adams ∗,1 , Peyman Mohajerin Esfahani 1,2 , Luca Laurenti 1
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE98 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2506-08689

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Efficient Uncertainty Propagation with Guarantees in Wasserstein Distance Thanks: ∗ Equal contribution. The authors are with (1) Delft University of Technology, and (2) the University of Toronto. Corresponding author’s email: [email protected]. This research is partially supported by the NWO (grant OCENW.M.22.056) and the ERC Starting Grant TRUST-949796. Eduardo Figueiredo ∗,1 , Steven Adams ∗,1 , Peyman Mohajerin Esfahani 1,2 , Luca Laurenti 1 Abstract . In this paper, we consider the problem of propagating an uncertain distribution by a possibly non-linear function and quantifying the resulting uncertainty. We measure the uncertainty using the Wasserstein distance, and for a given input set of distributions close in the Wasserstein distance, we compute a set of distributions centered at a discrete distribution that is guaranteed to contain the pushforward of any distribution in the input set. Our approach is based on approximating a nominal distribution from the input set to a discrete support distribution for which the exact computation of the pushforward distribution is tractable, thus guaranteeing computational efficiency to our approach. Then, we rely on results from semi-discrete optimal transport and distributional robust optimization to show that for any ϵ > 0 \epsilon>0 the error introduced by our approach can be made smaller than ϵ \epsilon . Critically, in the context of dynamical systems, we show how our results allow one to efficiently approximate the distribution of a stochastic dynamical system with a discrete support distribution for a possibly infinite horizon while bounding the resulting approximation error. We empirically investigate the effectiveness of our framework on various benchmarks, including a 10-D non-linear system, showing the effectiveness of our approach in quantifying uncertainty in linear and non-linear stochastic systems. 1. Introduction Modern cyber-physical systems are commonly affected by various sources of uncertainty . These include both the uncertainty caused by the intrinsic randomness in the system dynamics [ 38 ] and the uncertainty due to the use of statistical learning algorithms to estimate the unknown components/parameters of the system [ 28 , 41 ] . Consequently, it is common that mathematical models are not only stochastic, but the distribution of the various random variables are themselves uncertain [ 39 ] . As a result, when these models are used in safety-critical applications, the resulting uncertainty cannot be neglected [ 13 ] and must be propagated through possibly non-linear functions. For instance, this is the case for stochastic dynamical systems, where the input distribution and the distribution of the noise affecting the system are commonly estimated from data and need to be propagated through the system dynamics for multiple (possibly infinite) time steps [ 7 ] . Unfortunately, how to propagate uncertain distributions through non-linear functions is still an open question. This leads to the main question in this paper: how can we efficiently propagate an uncertain distribution through a non-linear function with formal guarantees of correctness? Propagating a distribution \mathbb{P} through a function f is equivalent to computing the push-forward distribution of \mathbb{P} by f denoted by f\#\mathbb{P} , which in the context of stochastic dynamical systems is equivalent to computing the Chapman-Kolmogorov Equation [ 33 ] . Unfortunately, in general, even when \mathbb{P} is known, computing f\#\mathbb{P} in closed form is not possible and requires approximations [ 27 ] , such as moment matching [ 14 ] or discretization-based methods [ 25 ] . Unfortunately, these techniques either come with no correctness guarantees or are too computationally demanding due to the need to discretize the full state space and do not support any uncertainty in \mathbb{P} . When \mathbb{P} is uncertain, the problem is exacerbated by the additional challenge of dealing with a possibly infinite set of distributions that must all be propagated through f . While this problem is receiving increasing interest [ 6 , 16 , 2 ] , existing approaches are either limited to linear f or lack formality and scalability. In this paper, given an uncertain distribution \mathbb{P} and a non-linear function f , we present a framework to efficiently approximate f\#\mathbb{P} via discrete distributions with formal quantification of the resulting uncertainty. To quantify the uncertainty, we rely on the Wasserstein distance [ 40 ] . This choice is motivated by the properties of the Wasserstein distance (i.e., it is a metric, it bounds the distance of the moments of the distributions, and convergence in the Wasserstein distance guarantees weak convergence) and its connection with optimal transport, which allows us to devise particularly efficient algorithms to solve our problem. Our approach is based on the fact that the Wasserstein distance between a continuous and a discrete distribution can be characterized as the solution of a semi-discrete optimal problem for which optimal solutions can be efficiently computed [ 34 ] . By using this connection and using techniques from distributional robust optimization and stochastic optimization [ 9 , 10 , 31 , 18 ] , we show that given a discrete distribution approximating \mathbb{P} , the Wasserstein distance between the pushforward of \mathbb{P} by f and of its discrete approximation can be efficiently bounded, even when \mathbb{P} is uncertain and f non-linear. The resulting bound can then be minimized by appropriately selecting the support of the approximating discrete distribution. This allows us to derive an efficient algorithmic framework that, given an uncertain distribution \mathbb{P} and a non-linear function f and a given error threshold \epsilon>0 , returns a discrete distribution whose push-forward through f is guaranteed to be closer than \epsilon to f\#\mathbb{P} . We then show how our framework can be applied to formally approximate the state distribution of stochastic dynamical systems over time. We show that in contrast to existing results [ 6 , 17 ] , our approach can be successfully applied to linear and non-linear systems and for both finite and infinite time prediction horizons. In particular, under relatively mild assumptions on f, we prove the convergence of the approximation error of our approach over time to a fixed point. To further illustrate the usefulness of our framework, we perform an empirical evaluation on various benchmarks. In particular, we consider various linear and non-linear systems, including standard control benchmarks such as the Mountain Car [ 37 ] and Dubins Car [ 8 ] , and a 10-D model of a neural network. The empirical analysis highlights how our framework can successfully approximate the push-forward distributions in both linear and non-linear cases and with relatively small discrete distributions, thus showcasing its potential to efficiently approximate complex distributions even in complex iterative prediction settings. In summary, the main contributions of this work are listed below: • Uncertainty propagation : upper-bounds on the uncertainty measured in terms of the Wasserstein distance of the pushforward of an uncertain probability distribution through a possibly non-linear function (Theorem 5.1 ), and a refined version under no ambiguity (Theorem 5.2 ); • Algorithm & convergence rate : an efficient algorithmic procedure (Algorithm 1 ) to approximate the pushforward of an uncertain probability distribution by a discrete distribution, with guaranteed convergence in \rho -Wasserstein distance (Theorem 6.2 ); • Approximation error dynamics : an application of our framework to stochastic dynamical systems for both finite and infinite prediction horizons (Theorem 7.1 ). The paper is organized as follows. We formulate the problem in

Read the complete text