Fast and Accurate Approximations of the Optimal Transport in Semi-Discrete and Discrete Settings
Given a d-dimensional continuous (resp. discrete) probability distribution µ and a discrete distribution ν, the semi-discrete (resp. discrete) optimal transport (OT) problem asks for computing a minimum-cost plan to transport mass from µ to ν; we assume n to be the number of points in the support of the discrete distributions. In this paper, we present three approximation algorithms for the OT problem with strong provable guarantees. (i) Additive approximation for semi-discrete OT: For any parameter ε > 0, we present an algorithm that computes a semi-discrete transport plan τ̃ with cost (equation presented) time; here, τ∗ is the optimal transport plan, D is the diameter of the supports of µ and ν, and we assume we have access to an oracle that outputs the mass of µ inside a constant-complexity region in O(1) time. Our algorithm works for several ground distances including the Lp-norm and the squared-Euclidean distance. (ii) Relative approximation for semi-discrete OT: For any parameter ε > 0, we present an algorithm that computes a semi-discrete transport plan τ̃ with cost ¢(τ̃) ≤ (1 + ε)¢(τ∗) in nlog(n) · (ε−1 log log n)O(d) expected time; here, τ∗ is the optimal transport plan, and we assume we have access to an oracle that outputs the mass of µ inside an orthogonal box in O(1) time, and the ground distance is any Lp norm. (iii) Relative approximation for discrete OT: For any parameter ε > 0, we present a Monte-Carlo algorithm that computes a transport plan τ̃ with an expected cost ¢(τ̃) ≤ (1 + ε)¢(τ∗) under any Lp norm in (Equation presented) time; here, τ∗ is an optimal transport plan and we assume that the spread of the supports of µ and ν is polynomially bounded.
