Entropic Regularization of the Nested Distance

arXiv2107.09864MaRDI QIDQ6373371FDOQ6373371

Authors: Zheng Qu, Benoît Tran 

Publication date: 20 July 2021

Abstract: 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(n^{3}log(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(n^2)$. In this article, we present and test numerically an entropic regularization of the Nested Distance.

Has companion code repository: https://github.com/BenoitTran/END

This page was built for publication: Entropic Regularization of the Nested Distance

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6373371)