In Appendix A, we introduce and recall necessary notations for the supplementary material. Regarding Sinkhorn algorithm, uk,vk are the updates of thek-th iteration. The main idea for deriving this bound comes from the geometric convergence rate (i.e. First, we represent the above difference by other quantities that are straightforward to bound. Thus, it has an unique optimal solution which could be directly calculated as Xi =B(ui,vi;Ci).

In Appendix A, we introduce and recall necessary notations for the supplementary material. Appendix D. Appendix C is devoted to the lemmas and proofs for the computational complexity of B.1 Useful Lemmas We first start with the following useful lemmas for the proof of Theorem 1. Lemma 3. The following inequalities are true for all positive x Proof of Lemma 3. (a) It follows from the assumption x This directly leads to the conclusion. The desired inequalities are equivalent to upper and lower bounds for the second term of the RHS. W e have following upper bounds for the optimal solutions of RSOT's dual form, which is Proof of Lemma 5. First, we will show that null u Finally, applying Lemma 5, we obtain the conclusion.B.2 Detailed Proof of Theorem 1 Denoting k Subsequently, the two terms in the right-hand side can be bounded separately as follows. The main idea for deriving this bound comes from the geometric convergence rate (i.e.

We consider two robust versions of optimal transport, named $\textit{Robust Semi-constrained Optimal Transport}$ (RSOT) and $\textit{Robust Unconstrained Optimal Transport}$ (ROT), formulated by relaxing the marginal constraints with Kullback-Leibler divergence. For both problems in the discrete settings, we propose Sinkhorn-based algorithms that produce $\varepsilon$-approximations of RSOT and ROT in $\widetilde{\mathcal{O}}(\frac{n^2}{\varepsilon})$ time, where $n$ is the number of supports of the probability distributions. Furthermore, to reduce the dependency of the complexity of the Sinkhorn-based algorithms on $n$, we apply Nystr\"{o}m method to approximate the kernel matrix in both RSOT and ROT by a matrix of rank $r$ before passing it to these Sinkhorn-based algorithms. We demonstrate that these new algorithms have $\widetilde{\mathcal{O}}(n r^2 + \frac{nr}{\varepsilon})$ runtime to obtain the RSOT and ROT $\varepsilon$-approximations. Finally, we consider a barycenter problem based on RSOT, named $\textit{Robust Semi-Constrained Barycenter}$ problem (RSBP), and develop a robust iterative Bregman projection algorithm, called $\textbf{Normalized-RobustIBP}$ algorithm, to solve the RSBP in the discrete settings of probability distributions. We show that an $\varepsilon$-approximated solution of the RSBP can be achieved in $\widetilde{\mathcal{O}}(\frac{mn^2}{\varepsilon})$ time using $\textbf{Normalized-RobustIBP}$ algorithm when $m = 2$, which is better than the previous complexity $\widetilde{\mathcal{O}}(\frac{mn^2}{\varepsilon^2})$ of IBP algorithm for approximating the Wasserstein barycenter. Extensive experiments confirm our theoretical results.