Optimal Transport (OT) is dedicated to solving how to transform one measure to another with least cost. OT has gained wide applications in machine learning. However, the heavy computation burden of primal OT distance makes it prohibitive for prevalent high-dimensional problems. Recent work imposes an entropic regularization term on primal OT, obtaining a strictly convex problem that can be addressed with stochastic optimization. We focus on the optimization methods for discrete OT and semi-discrete OT with regularization. Instead of the initial SAG method for discrete OT, we apply SAGA, which solves the biased gradient estimation problem, and SVRG, which solves the memory problem. Besides, we define the regret in semi-discrete OT problem and solve it from the perspective of online learning. Our study, to our best knowledge, is the first effort to solve the semi-discrete OT problem with follow-the-regularized-leader thought. Our FTRL-\textit{current} algorithm shows faster convergence than existing algorithms for solving semi-discrete OT problem.

In this paper we study the well-known greedy coordinate descent (GCD) algorithm to solve $\ell_1$-regularized problems and improve GCD by the two popular strategies: Nesterov's acceleration and stochastic optimization. Firstly, we propose a new rule for greedy selection based on an $\ell_1$-norm square approximation which is nontrivial to solve but convex; then an efficient algorithm called ``SOft ThreshOlding PrOjection (SOTOPO)'' is proposed to exactly solve the $\ell_1$-regularized $\ell_1$-norm square approximation problem, which is induced by the new rule. Based on the new rule and the SOTOPO algorithm, the Nesterov's acceleration and stochastic optimization strategies are then successfully applied to the GCD algorithm. The resulted algorithm called accelerated stochastic greedy coordinate descent (ASGCD) has the optimal convergence rate $O(\sqrt{1/\epsilon})$; meanwhile, it reduces the iteration complexity of greedy selection up to a factor of sample size. Both theoretically and empirically, we show that ASGCD has better performance for high-dimensional and dense problems with sparse solution.