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 theoretical 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 ¢(τ) ≤ ¢(τ * ) + ε in n O(d) log ∆ ε time; here, τ * is the optimal transport plan, ∆ 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 L p -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

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 L p 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 ¢

here, σ * is an optimal discrete transport plan and we assume that the spread of the supports of µ and ν is polynomially bounded.