betaFeedback

WorksMathematics

Sampling-Based Methods for Multi-Block Optimization Problems over Transport Polytopes

Abstract

This paper focuses on multi-block optimization problems over transport polytopes, which underlie various applications including strongly correlated quantum physics and machine learning. Conventional block coordinate descent-type methods for the general multi-block problems store and operate on the matrix variables directly, resulting in formidable expenditure for large-scale settings. On the other hand, optimal transport problems, as a special case, have attracted extensive attention and numerical techniques that waive the use of the full matrices have recently emerged. However, it remains nontrivial to apply these techniques to the multi-block, possibly nonconvex problems with theoretical guarantees. In this work, we leverage the benefits of both sides and develop novel sampling-based block coordinate descent-type methods, which are equipped with either entropy regularization or Kullback-Leibler divergence. Each iteration of these methods solves subproblems restricted on the sampled degrees of freedom. Consequently, they involve only sparse matrices, which amounts to considerable complexity reductions. We explicitly characterize the sampling-induced errors and establish convergence and asymptotic properties for the methods equipped with the entropy regularization. Numerical experiments on typical strongly correlated electron systems corroborate their superior scalability over the methods utilizing full matrices. The advantage also enables the first visualization of approximate optimal transport maps between electron positions in three-dimensional contexts.

Introduction

In this work, we consider multi-block optimization problems over transport polytopes as follows:

minimize⁡(min⁡)f(X1,…,XN),subject to⁡(s.t.⁡)Xi∈U(ai,bi), i=1,…,N,(1)\begin{aligned} \operatorname{minimize}\quad&(\operatorname{min})\quad f(X_1,\ldots,X_N),\\ \operatorname{subject\ to}\quad&(\operatorname{s.t.})\quad X_i\in\mathcal{U}(a_i,b_i),\ i=1,\ldots,N, \tag*{(1)} \end{aligned}

where, for any i∈{1,…,N}i\in\{1,\ldots,N\} (1≤N∈N1\leq N\in\mathbb{N}), ai∈R+mia_i\in\mathbb{R}_{+}^{m_i}, bi∈R+nib_i\in\mathbb{R}_{+}^{n_i},

U(ai,bi):={T∈R+mi×ni∣T1ni=ai, TT1mi=bi}\mathcal{U}(a_i,b_i):=\left\{T\in\mathbb{R}_{+}^{m_i\times n_i}\mid T\mathbf{1}_{n_i}=a_i,\ T^{\mathsf{T}}\mathbf{1}_{m_i}=b_i\right\}

is called the transport polytope. The notation “1n1_n” refers to the all-ones vector in Rn\mathbb{R}^n. The unknown matrix variables are Xi∈Rmi×niX_i \in\mathbb{R}^{m_i \times n_i} (i=1,…,Ni = 1,\ldots,N). The objective function f:∏i=1NRmi×ni→Rf : \prod_{i=1}^{N} \mathbb{R}^{m_i \times n_i} \to\mathbb{R} is assumed to be block Lipschitz smooth over ∏i=1NU(ai,bi)\prod_{i=1}^{N} \mathcal{U}(a_i,b_i) (for the definition see § 4), possibly nonconvex. Problem (1) finds its applications in several fields. For example, in quantum physics, it provides a promising route for treating the elusive strongly correlated electron systems (e.g., transition metal oxides [29]), describing the electron-electron correlation explicitly [23, 42]. It can also act as a subproblem in finding the Wasserstein barycenter among several discrete probability distributions [21], which has gained popularity so far in statistics [13] and machine learning [28], as well as in label distribution learning [84], which reflects the relative importance of different labels in supervised learning [39].

For solving general multi-block optimization problems, block coordinate descent (BCD)-type methods rank among the top choices. These methods fully exploit the separability of the feasible region, in that each subproblem involves only one variable block and is much easier to solve than the original problem. Representatives of the BCD-type methods are the block coordinate descent (BCD) methods [12, 35, 78], block conditional gradient (BCG) methods [9, 16], proximal alternating linearized minimization (PALM) methods [14, 43], as well as their stochastic versions [9, 22, 31, 40, 51, 74], where randomness is introduced to the gradient calculations or update order. Nevertheless, for the specific problem (1), all the existing BCD-type methods store and operate on the matrix variables directly, requiring at least quadratically growing complexities per iteration. This forms formidable memory and computation burdens when {mi}i=1N\{m_i\}_{i=1}^{N} and/or {ni}i=1N\{n_i\}_{i=1}^{N} are of large magnitude. Taking the aforementioned quantum physics application [42] for instance, mim_i (=ni= n_i) stands for the number of grid points and can be of order 10410^4 or 10510^5 even for crude discretization.

When NN equals one (mi=mm_i = m, ni=nn_i = n) and ff is affine, problem (1) reduces to the Kantorovich formulation of the classical optimal transport (OT) problem [75]. The exploration of this problem dates back to Monge’s pioneering work in the 18th century [64], followed by Kantorovich’s relaxation in the 20th century [45]. Since then, a plethora of numerical methods for solving OT problems have been constantly emerging. Traditional ones solve differential equations [10, 19] or turn to linear programming solvers [66, 68], resulting in unacceptable cubic complexities. Nowadays, the widest usage may go to the entropy regularization-based methods [27, 67], which allow the approximations of solutions in O(tmax⁡mn)\mathcal{O}(t_{\max}mn) scaling time with the Sinkhorn algorithm [73], where tmax⁡t_{\max} is the number of iterations; see § 2.3 for more discussions. In recent years, motivated by the need in large-scale contexts, there have been works dedicated to alleviating the per-iteration quadratic costs by the conventional Sinkhorn algorithm; for example, the low-rank approximation-based [7] and the entrywise sampling-based [53] variants of the Sinkhorn algorithm. Remarkably, the latter variant essentially deals with a restricted OT problem:

min⁡X ⟨C^,X⟩,s.t. X∈U(a,b), XIc=0,(2)\min_{X} \ \langle\widehat{C}, X\rangle,\quad\text{s.t. } X \in\mathcal{U}(a,b),\ X_{\mathcal{I}^c}=0, \tag*{(2)}

where C^∈Rm×n\widehat{C} \in\mathbb{R}^{m \times n} is an effective cost matrix (defined later), X∈Rm×nX \in\mathbb{R}^{m \times n}, a∈Rma \in\mathbb{R}^m, b∈Rnb \in\mathbb{R}^n, I⊆{(j,k)∣j=1,…,m, k=1,…,n}\mathcal{I} \subseteq\{(j,k) \mid j = 1,\ldots,m,\ k = 1,\ldots,n\} contains the indices sampled from the beginning according to some probability distribution related to aa and bb, and Ic\mathcal{I}^c denotes its complementary set. The constraint “XIc=0X_{\mathcal{I}^c}=0” enforces the entries in XX indexed by Ic\mathcal{I}^c to be zero, which distinguishes the algorithm from the well-known stochastic optimization methods. As a result, only ∣I∣|\mathcal{I}| entries in XX get involved in the calculations and updates, leading to a nice scaling when ∣I∣=o(mn)|\mathcal{I}| = o(mn). However, it remains unclear whether the sampling technique can be adapted to handle the multi-block, possibly nonconvex problem (1), while maintaining favorable convergence properties. One possible way is to integrate the sampling technique into the BCD-type methods and to solve restricted subproblems like (2) in each iteration. Analyzing the accumulation of errors induced by sampling will then become subtle.

Contributions and organization.

We develop in this paper sampling-based BCD-type methods for problem (1), which are equipped with either entropy regularization or Kullback-Leibler divergence. In particular, importance samplings are performed conforming to the probability distributions associated with the previous iterates and each iteration solves subproblems restricted over sampled supports. Consequently, only o(mini)o(m_i n_i) entries in XiX_i (i=1,…,Ni=1,\ldots,N) take part in the updates and derivatives calculations, which amounts to considerable computational saving in large-scale contexts.

Following the theoretical results about randomized matrix sparsification, we analyze the convergence and asymptotic properties for the methods equipped with entropy regularization. We explicitly characterize the sampling-induced errors and establish upper bounds for the average stationarity violations. The average violation is further shown to vanish in the limit ∑i=1N(mi+ni)→+∞\sum_{i=1}^{N}(m_i+n_i)\to+\infty (with probability going to 1). Notably, to the best of our knowledge, our work is the first attempt in applying the matrix entrywise sampling technique to multi-block nonconvex settings with theoretical guarantees.

We demonstrate the efficiency of the newly designed methods via numerical simulations of typical strongly correlated electron systems. Their better scalability enables the first visualization of the approximate OT maps between electron positions in three-dimensional contexts.

The paper is organized as follows. We provide preliminaries in section 2 and elaborate on the algorithmic developments in section 3. Section 4 contains our theoretical results, whose proofs are deferred to the appendix. Numerical experiments and results are described in section 5. Finally, we conclude in section 6.

Preliminaries

This section offers some preliminaries, including notations, tools from OT, and bibliographical notes on entrywise matrix sparsification.

Notations

This paper presents scalars, vectors, and matrices by regular-font, bold lower-case, and upper-case letters, respectively. We denote the rounding down operation by “⌊⋅⌋\lfloor\cdot\rfloor”. The notation “1n\mathbf{1}_n” stands for the all-ones vector in Rn\mathbb{R}^n. The notations “⟨⋅,⋅⟩\langle\cdot,\cdot\rangle” and “∥⋅∥\|\cdot\|” calculate, respectively, the standard inner product and norm of vectors or matrices in the ambient Euclidean space. We use “∥⋅∥2\|\cdot\|_2” particularly for the 2-norm of matrices. The notation “κ(⋅)\kappa(\cdot)” refers to the spectral condition number of a matrix. We use “Diag⁡(⋅)\operatorname{Diag}(\cdot)” to form a diagonal matrix with the input vector. We denote the entries or sub-blocks of vectors by single subscripts (e.g., qkq_k or ai\mathbf{a}_i), the sub-blocks of matrices by single subscripts (e.g., XiX_i), and the entries of matrices by double subscripts (e.g., xi,jkx_{i,jk}). A matrix with a set subscript refers to the entries indexed by the set (e.g., XIX_{\mathcal{I}}). Sometimes, we make abbreviations for the aggregation of the sub-blocks of a matrix (e.g., X≤i:=(X1,…,Xi)X_{\leq i}:=(X_1,\ldots,X_i), X>i:=(Xi+1,…,XN)X_{>i}:=(X_{i+1},\ldots,X_N)). These abbreviations become null if the index sets in the subscripts are empty. The entrywise product and division of two vectors or matrices are denoted by “⊙\odot” and “⊘\oslash”, respectively. Univariate functions, such as “exp⁡(⋅)\exp(\cdot)” and “log⁡(⋅)\log(\cdot)”, are extended to vectors and matrices as entrywise operations.

For a multivariate function gg, ∇g\nabla g is the gradient of gg at the points where gg is differentiable. We add a subscript to indicate the block with respect to which the derivative is taken (e.g., ∇ig\nabla_i g).

We use R++\mathbb{R}_{++} to denote the set of positive real numbers. Given a set, its measure or cardinality is represented using “∣⋅∣|\cdot|. We use “×\times” or “×\times” to refer to the Cartesian product of sets or spaces (e.g., ∏i=1NRmi×ni\prod_{i=1}^{N}\mathbb{R}^{m_i\times n_i} or Rmi×Rni\mathbb{R}^{m_i}\times\mathbb{R}^{n_i}), use exponents to represent the Cartesian product of identical sets or spaces (e.g., (RK×K)Nε−1(\mathbb{R}^{K\times K})^{N_\varepsilon-1}). The complementary set is noted with a superscript “c” (e.g., Ic\mathcal{I}^c).

When describing algorithms, we use superscripts within brackets to refer to the iteration numbers (e.g., Xi(t)X_i^{(t)}).

Negative entropy and Kullback-Leibler divergence

Definition 1 ([49, 72]). For any T=(tij)∈R+m×nT=(t_{ij})\in\mathbb{R}_{+}^{m\times n}, its negative entropy is defined as h(T):=∑ijtij(log⁡tij−1)h(T):=\sum_{ij}t_{ij}(\log t_{ij}-1). Given any T=(tij), T′=(tij′)∈R+m×nT=(t_{ij}),\ T'=(t'_{ij})\in\mathbb{R}_{+}^{m\times n}, the Kullback-Leibler (KL) divergence between TT and T′T' is defined as

KL⁡(T;T′):=∑i,j[tij(log⁡tij−log⁡tij′)−(tij−tij′)].(3)\operatorname{KL}(T;T'):=\sum_{i,j}\left[t_{ij}(\log t_{ij}-\log t'_{ij})-(t_{ij}-t'_{ij})\right]. \tag*{(3)}

If tij>0t_{ij}>0 and tij′=0t'_{ij}=0 for some pair (i,j)(i,j), then KL⁡(T;T′)=+∞\operatorname{KL}(T;T')=+\infty.

The negative entropy has been adopted in thermodynamics as a measure of disorder in a system, or a measure of uncertainty in information theory. The KL divergence can be treated as the Bregman distance [18] associated with the negative entropy; it has been used as a measure of the disparity between probability distributions [67].

Entropy regularized optimal transport

The Kantorovich formulation of the discrete OT problem is in general

min⁡T ⟨W,T⟩,s.t. T∈U(p,q),(4)\min_T\ \langle W,T\rangle,\quad\text{s.t. }T\in\mathcal{U}(\mathbf{p},\mathbf{q}), \tag*{(4)}

where T=(tij)∈Rm×nT=(t_{ij})\in\mathbb{R}^{m\times n} is the transport plan, W=(wij)∈Rm×nW=(w_{ij})\in\mathbb{R}^{m\times n} is the cost matrix, and p∈Rm\mathbf{p}\in\mathbb{R}^{m}, q∈Rn\mathbf{q}\in\mathbb{R}^{n} are discrete probability distributions. The solution to problem (4) is referred to as the OT plan, which achieves minimal transportation efforts. Nowadays, OT has attracted extensive attention from applications (e.g., [8, 60, 63, 81]).

The computational complexity of directly solving problem (4) as a linear programming usually grows cubically as mm and nn increase, which severely hinders the wide applications of OT. To approximate the solution efficiently within certain tolerance, the author of [27] adds a (negative) entropy regularization penalty, obtaining

References

  1. [1]D. Achlioptas, Z. S. Karnin, and E. Liberty, Near-optimal entrywise sampling for data matrices, Advances in Neural Information Processing Systems (C. J. Burges, L. Bottou, M. Welling, Z. Ghahramani, and K. Q. Weinberger, eds.), Vol. 26, Curran Associates, Inc., 2013, pp. 1565–1573.arxiv.org/abs/1311.4643
  2. [2]D. Achlioptas and F. McSherry, Fast computation of low-rank matrix approximations, J. ACM 54 (2007), no. 2, Art. 9, 19, DOI 10.1145/1219092.1219097.DOI
  3. [3]M. Ahookhosh, L. T. K. Hien, N. Gillis, and P. Patrinos, Multi-Block Bregman proximal alternating linearized minimization and its application to orthogonal nonnegative matrix factorization, Comput. Optim. Appl. 79 (2021), no. 3, 681–715, DOI 10.1007/s10589-021-00286-3.DOI
  4. [4]M. Ai, F. Wang, J. Yu, and H. Zhang, Global variable subsampling for large-scale quantile regression, J. Complex. 62 (2021), 101512, DOI 10.1016/j.jco.2020.101512.DOI
  5. [5]A. Alfonsi, R. Coyaud, and V. Ehrlacher, Constrained overdamped Langevin dynamics for symmetric multimarginal optimal transportation, Math. Models Methods Appl. Sci. 32 (2022), no. 03, 403–455, DOI 10.1142/S0218202522500105.DOI
  6. [6]A. Alfonsi, R. Coyaud, V. Ehrlacher, and D. Lombardi, Approximation of optimal transport problems with marginal moments constraints, Math. Comp. 90 (2021), no. 328, 689–737, DOI 10.1090/mcom/3568.DOI
  7. [7]J. Altschuler, F. Bach, A. Rudi, and J. Niles-Weed, Marginally scalable Sinkhorn distances via the Nuström method, Advances in Neural Information Processing Systems (H. Wallach, H. Larochelle, A. Beygelzimer, F. d’Alché-Buc, E. Fox, and R. Garnett, eds.), Vol. 32, Curran Associates, Inc., 2019, pp. 4427–4437.DOI
  8. [8]M. Arjovsky, S. Chintala, and L. Bottou, Wasserstein generative adversarial networks, Proceedings of the 34th International Conference on Machine Learning (D. Precup and Y. W. Teh, eds.), Proceedings of Machine Learning Research, vol. 70, PMLR, 2017, pp. 214–223.
  9. [9]A. Beck, E. Pauwels, and S. Sabach, The cyclic block conditional gradient method for convex optimization problems, SIAM J. Optim. 25 (2015), no. 4, 2024–2049, DOI 10.1137/15M1008397.DOI
  10. [10]J.-D. Benamou, Y. Brenier, and K. Guittet, The Monge-Kantorovitch mass transfer and its computational fluid mechanics formulation, Internat. J. Numer. Methods Fluids 40 (2002), no. 1-2, 21–30, DOI 10.1002/fld.264. ICFD Conference on Numerical Methods for Fluid Dynamics (Oxford, 2001).DOI
  11. [11]J.-D. Benamou, G. Carlier, and L. Nenna, A numerical method to solve multi-marginal optimal transport problems with Coulomb cost, Splitting Methods in Communication, Imaging, Science, and Engineering (R. Glowinski, S. J. Osher, and W. Yin, eds.), Sci. Comput., Springer, Cham, 2016, pp. 577–601.DOI
  12. [12]D. P. Bertsekas, Nonlinear Programming, 3rd ed., Athena Scientific Optimization and Computation Series, Athena Scientific, Belmont, MA, 2016.
  13. [13]J. Bigot and T. Klein, Consistent estimation of a population barycenter in the Wasserstein space, arXiv: 1212.2562 (math.ST), 2012.
  14. [14]J. Bolte, S. Sabach, and M. Teboulle, Proximal alternating linearized minimization for nonconvex and nonsmooth problems, Math. Program. 146 (2014), no. 1-2, 459–494, DOI 10.1007/s10107-013-0701-9.DOI
  15. [15]A. Borzì and J. Hohenester, Multigrid optimization schemes for solving Bose-Einstein condensate control problems, SIAM J. Sci. Comput. 30 (2008), no. 1, 441–462, DOI 10.1137/070866135.DOI
  16. [16]G. Braun, A. Carderera, C. W. Combettes, H. Hassani, A. Karbasi, A. Mokhtari, and S. Pokutta, Conditional gradient methods, arXiv: 2211.14103 [math.OC], 2022.arxiv.org/abs/2211.14103
  17. [17]V. Braverman, R. Krauthgamer, A. R. Krishnan, and S. Sapir, Near-optimal entrywise sampling of numerically sparse matrices, Proceedings of the 34th Conference on Learning Theory (M. Belkin and S. Kpotufe, eds.), Proceedings of Machine Learning Research, vol. 134, PMLR, 2021, pp. 759–773.arxiv.org/abs/2011.01777
  18. [18]L. M. Bregman, A relaxation method of finding a common point of convex sets and its application to the solution of problems in convex programming, Ž. Vyčisl. Mat. i Mat. Fiz. 7 (1967), 620–631 (Russian).DOI
  19. [19]Y. Brenier, A homogenized model for vortex sheets, Arch. Rational Mech. Anal. 138 (1997), no. 4, 319–353, DOI 10.1007/s002050050044.DOI
  20. [20]G. Buttazzo, L. De Pascale, and P. Gori-Giorgi, Optimal-transport formulation of electronic density-functional theory, Phys. Rev. A 85 (2012), no. 6, 062502, DOI 10.1103/PhysRevA.85.062502.DOI
  21. [21]G. Carlier, A. Oberman, and E. Oudet, Numerical methods for matching for teams and Wasserstein barycenters, ESAIM Math. Model. Numer. Anal. 49 (2015), no. 6, 1621–1642, DOI 10.1051/m2an/2015033.DOI
  22. [22]C. Chen, M. Li, X. Liu, and Y. Ye, Extended ADMM and BCD for nonseparable convex minimization models with quadratic coupling terms: Convergence analysis and insights, Math. Program. 173 (2019), no. 1-2, 37–77, DOI 10.1007/s10107-017-1205-9.
  23. [23]H. Chen, G. Friesecke, and C. B. Mendl, Numerical methods for a Kohn-Sham density functional model based on optimal transport, J. Chem. Theory Comput. 10 (2014), no. 10, 4360–4368, DOI 10.1021/ct500586g.DOI
  24. [24]J. Chen and C. J. García-Cervera, An efficient multigrid strategy for large-scale molecular mechanics optimization, J. Comput. Phys. 342 (2017), 29–42, DOI 10.1016/j.jcp.2017.04.035.DOI
  25. [25]M. Colombo, L. De Pascale, and S. Di Marino, Multimarginal optimal transport maps for one-dimensional repulsive costs, Canad. J. Math. 67 (2015), no. 2, 350–368, DOI 10.4153/CJM-2014-011-x.DOI
  26. [26]C. Cotar, G. Friesecke, and C. Klüppelberg, Density functional theory and optimal transportation with Coulomb cost, Comm. Pure Appl. Math. 66 (2013), no. 4, 548–599, DOI 10.1002/cpa.21437.DOI
  27. [27]M. Cuturi, Sinkhorn distances: Lightspeed computation of optimal transport, Advances in Neural Information Processing Systems (C. J. Burges, L. Bottou, M. Welling, Z. Ghahramani, and K. Q. Weinberger, eds.), Vol. 26, Curran Associates, Inc., 2013, pp. 2292–2300.
  28. [28]M. Cuturi and A. Doucet, Fast computation of Wasserstein barycenters, Proceedings of the 31st International Conference on Machine Learning (E. P. Xing and T. Jebara, eds.), Proceedings of Machine Learning Research, vol. 32, PMLR, 2014, pp. 685–693.arxiv.org/abs/1310.4375
  29. [29]E. Dagotto, Complexity in strongly correlated electronic systems, Science 309 (2005), no. 5732, 257–262, DOI 10.1126/science.1107559.DOI
  30. [30]S. Di Marino and A. Gerolin, Optimal transport losses and Sinkhorn algorithm with general convex regularization, arXiv: 2007.00976 [math.OC], 2020.arxiv.org/abs/2007.00976
  31. [31]D. Driggs, J. Tang, J. Liang, M. Davies, and C.-B. Schönlieb, A stochastic proximal alternating minimization for nonsmooth and nonconvex optimization, SIAM J. Imaging Sci. 14 (2021), no. 4, 1932–1970, DOI 10.1137/20M1387213.DOI
  32. [32]P. Drineas and A. Zou zias, A note on element-wise matrix sparsification via a matrix-valued Bernstein inequality, Inform. Process. Lett. 111 (2011), no. 8, 385–389, DOI 10.1016/j.ipl.2011.01.010.DOI
  33. [33]P. Dvurechensky, A. Gasnikov, and A. Kroshnin, Computational optimal transport: Complexity by accelerated gradient descent is better than by Sinkhorn’s algorithm, Proceedings of the 35th International Conference on Machine Learning (J. Dy and A. Krause, eds.), Proceedings of Machine Learning Research, vol. 80, PMLR, 2018, pp. 1367–1376.arxiv.org/abs/1802.04367
  34. [34]V. Elvira and L. Martino, Advances in importance sampling, Wiley Statist. Ref. Stat. Ref. Online, posted on 2021, 1–14, DOI 10.1002/9781118445112.stat08284.DOI
  35. [35]O. Fercoq and P. Richtárik, Optimization in high dimensions via accelerated, parallel, and proximal coordinate descent, SIAM Rev. 58 (2016), no. 4, 739–771, DOI 10.1137/16M1085905.DOI
  36. [36]M. Filatov, Spin-restricted ensemble-referenced Kohn-Sham method: Basic principles and application to strongly correlated ground and excited states of molecules, Wiley Interdiscip. Rev. Comput. Mol. Sci. 5 (2015), no. 1, 146–167, DOI 10.1002/wcms.1209.DOI
  37. [37]G. Friesecke, A. Gerolin, and P. Gori-Giorgi, The strong-interaction limit of density functional theory, Density Functional Theory: Modeling, Mathematical Analysis, Computational Methods, and Applications (E. Cancès and G. Friesecke, eds.), Mathematics and Molecular Modeling, Springer, 2023, pp. 183–266, DOI 10.1007/978-3-031-22340-2_4.DOI
  38. [38]G. Friesecke, A. S. Schulz, and D. Vögler, Genetic column generation: Fast computation of high-dimensional multimarginal optimal transport problems, SIAM J. Sci. Comput. 44 (2022), no. 3, A1632–A1654, DOI 10.1137/21M147032X.arxiv.org/abs/2103.12624
  39. [39]X. Geng, Label distribution learning, IEEE Trans. Knowl. Data Eng. 28 (2016), no. 7, 1734–1748, DOI 10.1109/TKDE.2016.2545658.DOI
  40. [40]J. Hertrich and G. Steidl, Inertial stochastic PALM and applications in machine learning, Sampl. Theory Signal Process. Data Anal. 20 (2022), no. 1, Paper No. 4, 33, DOI 10.1007/s43670-022-00021-x.DOI
  41. [41]B. Hosseini and S. Steinerberger, Intrinsic sparsity of Kantorovich solutions, C. R. Math. Acad. Sci. Paris 360 (2022), 1173–1175, DOI 10.5802/crmath.392 (English, with English and French summaries).DOI
  42. [42]Y. Hu, H. Chen, and X. Liu, A global optimization approach for multi-marginal optimal transport problems with Coulomb cost, SIAM J. Sci. Comput. 45 (2023), no. 3, A1214–A1238, DOI 10.1137/21M1455164.DOI
  43. [43]Y. Hu and X. Liu, The convergence properties of infeasible inexact proximal alternating linearized minimization, Sci. China Math. 66 (2023), no. 10, 2385–2410, DOI 10.1007/s11425-022-2074-7.DOI
  44. [44]———, The exactness of the ℓ₁ penalty function for a class of mathematical programs with generalized complementarity constraints, Fundam. Res., posted on 2023, in press, DOI 10.1016/j.fmre.2023.04.006.DOI
  45. [45]L. V. Kantorovich, On the translocation of masses, C. R. (Doklady) Acad. Sci. URSS (N.S.) (1942), 199–201.
  46. [46]T. Kerdoncuff, R. Emonet, and M. Sebban, Sampled Gromov Wasserstein, Mach. Learn. 110 (2021), no. 8, 2151–2186, DOI 10.1007/s10994-021-06035-1.DOI
  47. [47]Y. Khoo, L. Lin, M. Lindsey, and L. Ying, Semidefinite relaxation of multimarginal optimal transport for strictly correlated electrons in second quantization, SIAM J. Sci. Comput. 42 (2020), no. 6, B1462–B1489, DOI 10.1137/20M1310977.DOI
  48. [48]Y. Khoo and L. Ying, Convex relaxation approaches for strictly correlated density functional theory, SIAM J. Sci. Comput. 41 (2019), no. 4, B773–B795, DOI 10.1137/18M1207478.DOI
  49. [50]A. Kundu, P. Drineas, and M. Magdon-Ismail, Recovering PCA and sparse PCA via a hybrid-(ℓ₁, ℓ₂) sparse sampling of data elements, J. Mach. Learn. Res. 18 (2017), no. 75, 1–34.DOI
  50. [51]S. Lacoste-Julien, M. Jaggi, M. Schmidt, and P. Pletscher, Block-coordinate Frank-Wolfe optimization for structural SVMs, Proceedings of the 30th International Conference on Machine Learning (S. Dasgupta and D. McAllester, eds.), Proceedings of Machine Learning Research, vol. 28, PMLR, 2013, pp. 53–61.
  51. [52]C.-P. Lee, Accelerating inexact successive quadratic approximation for regularized optimization through manifold identification, Math. Program. 201 (2023), no. 1-2, 599–633, DOI 10.1007/s10107-022-01916-2.DOI
  52. [53]M. Li, J. Yu, T. Li, and C. Meng, Importance sparsification for Sinkhorn algorithm, J. Mach. Learn. Res. 24 (2023), no. 247, 1–44.arxiv.org/abs/2306.06581
  53. [54]M. Li, J. Yu, H. Xu, and C. Meng, Efficient approximation of Gromov-Wasserstein distance using importance sparsification, J. Comput. Graph. Statist. 32 (2023), no. 4, 1512–1523, DOI 10.1080/10618600.2023.2165500.DOI
  54. [55]Q. Li, Z. Zhu, G. Tang, and M. B. Wakin, Provable Bregman-divergence based methods for nonconvex and non-Lipschitz problems, arXiv: 1904.09712 [math.OC], 2019.arxiv.org/abs/1904.09712
  55. [56]J. S. Liu, Metropolized independent sampling with comparisons to rejection sampling and importance sampling, Stat. Comput. 6 (1996), no. 2, 113–119, DOI 10.1007/BF00162521.DOI
  56. [57]———, Monte Carlo Strategies in Scientific Computing, Springer Series in Statistics, Springer, New York, 2008.
  57. [58]J. Liu, W. Yin, W. Li, and Y. T. Chow, Multilevel optimal transport: A fast approximation of Wasserstein-1 distances, SIAM J. Sci. Comput. 43 (2021), no. 1, A193–A220, DOI 10.1137/18M1219813.DOI
  58. [59]Z.-Q. Luo and P. Tseng, On the convergence rate of dual ascent methods for linearly constrained convex minimization, Math. Oper. Res. 18 (1993), no. 4, 846–867, DOI 10.1287/moor.18.4.846.DOI
  59. [60]M. Ma, X. Wang, Y. Duan, S. H. Frey, and X. Gu, Optimal mass transport based brain morphometry for patients with congenital hand deformities, Vis. Comput. 35 (2019), 1311–1325, DOI 10.1007/s00371-018-1543-5.DOI
  60. [61]P. Ma, M. Mahoney, and B. Yu, A statistical perspective on algorithmic leveraging, Proceedings of the 31st International Conference on Machine Learning (E. P. Xing and T. Jebara, eds.), Proceedings of Machine Learning Research, vol. 32, PMLR, 2014, pp. 91–99.arxiv.org/abs/1306.5362
  61. [62]C. B. Mendl and L. Lin, Kantorovich dual solution for strictly correlated electrons in atoms and molecules, Phys. Rev. B 87 (2013), no. 12, 125106, DOI 10.1103/PhysRevB.87.125106.DOI
  62. [63]C. Meng, Y. Ke, J. Zhang, M. Zhang, W. Zhong, and P. Ma, Large-scale optimal transport map estimation using projection pursuit, Advances in Neural Information Processing Systems (H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, eds.), Vol. 32, Curran Associates, Inc., 2019, pp. 8118–8129.
  63. [64]G. Monge, Mémoire sur la théorie des déblais et des remblais, Histoire de l’Académie Royale des Sciences (1781), 666–704.
  64. [65]A. B. Owen, Monte Carlo Theory, Methods and Examples, Stanford University, 2013.
  65. [66]O. Pele and M. Werman, Fast and robust earth mover’s distances, IEEE 12th International Conference on Computer Vision, IEEE, 2009, pp. 460–467, DOI 10.1109/ICCV.2009.5459199.DOI
  66. [67]G. Peyré and M. Cuturi, Computational optimal transport: With applications to data science, Found. Trends Mach. Learn. 11 (2019), no. 5-6, 355–607, DOI 10.1561/2200000073.
  67. [68]Y. Rubner, L. J. Guibas, and C. Tomasi, The earth mover’s distance, multi-dimensional scaling, and color-based image retrieval, Proceedings of the ARPA Image Understanding Workshop, ARPA, 1997, pp. 661–668.
  68. [69]M. Seidl, Strong-interaction limit of density-functional theory, Phys. Rev. A 60 (1999), no. 6, 4387, DOI 10.1103/PhysRevA.60.4387.DOI
  69. [70]M. Seidl, J. P. Perdew, and S. Kurth, Simulation of all-order density-functional perturbation theory, using the second order and the strong-correlation limit, Phys. Rev. Lett. 84 (2000), no. 22, 5070, DOI 10.1103/PhysRevLett.84.5070.DOI
  70. [71]M. Seidl, J. P. Perdew, and M. Levy, Strictly correlated electrons in density-functional theory, Phys. Rev. A 59 (1999), no. 1, 51, DOI 10.1103/PhysRevA.59.51.DOI
  71. [73]R. Sinkhorn and P. Knopp, Concerning nonnegative matrices and doubly stochastic matrices, Pacific J. Math. 21 (1967), no. 2, 343–348, DOI 10.2307/2314570.
  72. [74]R. Sun, Z.-Q. Luo, and Y. Ye, On the efficiency of random permutation for ADMM and coordinate descent, Math. Oper. Res. 45 (2020), no. 1, 233–271, DOI 10.1287/moor.2019.0990.DOI
  73. [75]C. Villani, Topics in Optimal Transportation, Vol. 58, American Mathematical Society, 2003.DOI
  74. [76]H. Wang and J. Zou, A comparative study on sampling with replacement vs Poisson sampling in optimal sub-sampling, Proceedings of the 24th International Conference on Artificial Intelligence and Statistics (A. Banerjee and K. Fukumizu, eds.), Proceedings of Machine Learning Research, vol. 130, PMLR, 2021, pp. 289–297.
  75. [77]J. Wang, J. Zou, and H. Wang, Sampling with replacement vs Poisson sampling: A comparative study in optimal subsampling, IEEE Trans. Inform. Theory 68 (2022), no. 10, 6605–6630.
  76. [78]S. J. Wright, Coordinate descent algorithms, Math. Program. 151 (2015), no. 1, 3–34, DOI 10.1007/s10107-015-0892-3.DOI
  77. [79]Q. Xia and T. Shi, A cascadic multilevel optimization algorithm for the design of composite structures with curvilinear fiber based on Shepard interpolation, Compos. Struct. 188 (2018), 209–219, DOI 10.1016/j.compstruct.2018.01.013.
  78. [80]Y. Xie, X. Wang, R. Wang, and H. Zha, A fast proximal point method for computing exact Wasserstein distance, Proceedings of the 35th Uncertainty in Artificial Intelligence Conference (R. P. Adams and V. Gogate, eds.), Proceedings of Machine Learning Research, vol. 115, PMLR, Jul. 22, pp. 433–453.
  79. [81]L. Xu, H. Sun, and Y. Liu, Learning with batch-wise optimal transport loss for 3D shape recognition, Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, IEEE, Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2019, pp. 3333–3342.
  80. [82]L. Yang and K.-C. Toh, Bregman proximal point algorithm revisited: A new inexact version and its inertial variant, SIAM J. Optim. 32 (2022), no. 3, 1523–1554, DOI 10.1137/20M1360748.DOI
  81. [83]J. Yu, H. Wang, M. Ai, and H. Zhang, Optimal distributed subsampling for maximum quasi-likelihood estimators with massive data, J. Amer. Statist. Assoc. 117 (2022), no. 537, 265–276, DOI 10.1080/01621459.2020.1773832.DOI
  82. [84]P. Zhao and Z. Zhou, Label distribution learning by optimal transport, Proceedings of the AAAI Conference on Artificial Intelligence (S. A. McIlraith and K. Q. Weinberger, eds.), Vol. 32, AAAI Press, 2018, pp. 4506–4513, DOI 10.1609/aaai.v32i1.11609.DOI

Paper details

vlnc:W_jzg7ybrd
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents