Relative Entropy-Regularized Optimal Transport on a Graph: a new algorithm and an experimental comparison
Following [21, 23], the present work investigates a new relative entropy-regularized algorithm for solving the optimal transport on a graph problem within the randomized shortest paths formalism. More precisely, a unit flow is injected into a set of input nodes and collected from a set of output nodes while minimizing the expected transportation cost together with a paths relative entropy regularization term, providing a randomized routing policy. The main advantage of this new formulation is the fact that it can easily accommodate edge flow capacity constraints which commonly occur in real-world problems. The resulting optimal routing policy, i.e., the probability distribution of following an edge in each node, is Markovian and is computed by constraining the input and output flows to the prescribed marginal probabilities thanks to a variant of the algorithm developed in [8]. In addition, experimental comparisons with other recently developed techniques show that the distance measure between nodes derived from the introduced model provides competitive results on semi-supervised classification tasks.
Code (0)
등록된 구현이 없습니다.
Methods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Convergence Rates for Regularized Optimal Transport via Quantization
We study the convergence of divergence-regularized optimal transport as the regularization parameter vanishes. Sharp rates for general divergences including relative entropy or $L^{p}$ regularization, general transport c…
QuantizationMulti-marginal optimal transport and probabilistic graphical models
We study multi-marginal optimal transport problems from a probabilistic graphical model perspective. We point out an elegant connection between the two when the underlying cost for optimal transport allows a graph struct…
Bayesian InferenceEntropy-regularized Optimal Transport Generative Models
We investigate the use of entropy-regularized optimal transport (EOT) cost in developing generative models to learn implicit distributions. Two generative models are proposed. One uses EOT cost directly in an one-shot op…
Image GenerationImitation-regularized Optimal Transport on Networks: Provable Robustness and Application to Logistics Planning
Transport systems on networks are crucial in various applications, but face a significant risk of being adversely affected by unforeseen circumstances such as disasters. The application of entropy-regularized optimal tra…
Imitation LearningEntropy Regularized Optimal Transport Independence Criterion
We introduce an independence criterion based on entropy regularized optimal transport. Our criterion can be used to test for independence between two samples. We establish non-asymptotic bounds for our test statistic and…