# Entropic Regularization of the Nested Distance

arXiv: https://arxiv.org/abs/2107.09864 · HTML: https://mlsanity.com/paper/2107.09864/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Jul 2021.

## Built on by (most cited first, 1 of 1)

- [Barycentric Weak Inner-Product Gromov-Wasserstein](https://mlsanity.com/paper/2608.25145/) (2026)

## Abstract (arXiv)

In 2012, Pflug and Pichler proved, under regularity assumptions, that the value function in Multistage Stochastic Programming (MSP) is Lipschitz continuous w.r.t. the Nested Distance, which is a distance between scenario trees (or discrete time stochastic processes with finite support). The Nested Distance is a refinement of the Wasserstein distance to account for proximity of the filtrations of discrete time stochastic processes. The computation of the Nested Distance between two scenario trees amounts to the computation of an exponential (in the horizon T) number of optimal transport problems between smaller conditional probabilities of size n, where n is less than maximal number of children of each node. Such optimal transport problems can be solved by the auction algorithm with complexity O(n3log(n)). In 2013, Cuturi introduced Sinkhorn's algorithm, an alternating projection scheme which solves an entropic regularized optimal transport problem. Sinkhorn's algorithm converges linearly and each iteration has a complexity of O(n2). In this article, we present and test numerically an entropic regularization of the Nested Distance.