On the Convergence of Semi-Relaxed Sinkhorn with Marginal Constraint and OT Distance Gaps
This paper presents consideration of the Semi-Relaxed Sinkhorn (SR-Sinkhorn)
algorithm for the semi-relaxed optimal transport (SROT) problem, which relaxes
one marginal constraint of the standard OT problem. For evaluation of how the
constraint relaxation affects the algorithm behavior and solution, it is
vitally necessary to present the theoretical convergence analysis in terms not
only of the functional value gap, but also of the marginal constraint gap as
well as the OT distance gap. However, no existing work has addressed all
analyses simultaneously. To this end, this paper presents a comprehensive
convergence analysis for SR-Sinkhorn. After presenting the
$\epsilon$-approximation of the functional value gap based on a new proof
strategy and exploiting this proof strategy, we give the upper bound of the
marginal constraint gap. We also provide its convergence to the
$\epsilon$-approximation when two distributions are in the probability simplex.
Furthermore, the convergence analysis of the OT distance gap to the
$\epsilon$-approximation is given as assisted by the obtained marginal
constraint gap. The latter two theoretical results are the first results
presented in the literature related to the SROT problem.