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.

arXiv comment38 pages, 11 figures, 5 tables

References in corpus (33)

• Complexity in Strongly Correlated Electronic Systems
• Fast Computation of Wasserstein Barycenters
• Optimal-transport formulation of electronic density-functional theory
• Block-Coordinate Frank-Wolfe Optimization for Structural SVMs
• A Statistical Perspective on Algorithmic Leveraging
• A Fast Proximal Point Method for Computing Exact Wasserstein Distance
• Computational Optimal Transport: Complexity by Accelerated Gradient Descent Is Better Than by Sinkhorn's Algorithm
• Towards the Kantorovich dual solution for strictly correlated electrons in atoms and molecules
• Numerical methods for a Kohn-Sham density functional model based on optimal transport
• A Note on Element-wise Matrix Sparsification via a Matrix-valued Bernstein Inequality
• Provable Bregman-divergence based Methods for Nonconvex and Non-Lipschitz Problems
• Near-Optimal Entrywise Sampling for Data Matrices
• Massively scalable Sinkhorn distances via the Nyström method
• Approximation of Optimal Transport problems with marginal moments constraints
• Multilevel Optimal Transport: a Fast Approximation of Wasserstein-1 distances
• Inertial Stochastic PALM (iSPALM) and Applications in Machine Learning
• On the Efficiency of Random Permutation for ADMM and Coordinate Descent
• Large-scale optimal transport map estimation using projection pursuit
• Conditional Gradient Methods
• Optimal Distributed Subsampling for Maximum Quasi-Likelihood Estimators with Massive Data
• Multi-block Bregman proximal alternating linearized minimization and its application to orthogonal nonnegative matrix factorization
• Optimal Transport losses and Sinkhorn algorithm with general convex regularization
• Extended ADMM and BCD for Nonseparable Convex Minimization Models with Quadratic Coupling Terms: Convergence Analysis and Insights
• Semidefinite relaxation of multi-marginal optimal transport for strictly correlated electrons in second quantization
• Accelerating Inexact Successive Quadratic Approximation for Regularized Optimization Through Manifold Identification
• Importance Sparsification for Sinkhorn Algorithm
• The Convergence Properties of Infeasible Inexact Proximal Alternating Linearized Minimization
• A Global Optimization Approach for Multi-Marginal Optimal Transport Problems with Coulomb Cost
• Convex relaxation approaches for strictly correlated density functional theory
• The Exactness of the ${\ell }_1$ Penalty Function for a Class of Mathematical Programs with Generalized Complementarity Constraints
• The strong-interaction limit of density functional theory
• Efficient Approximation of Gromov-Wasserstein Distance Using Importance Sparsification
• Near-Optimal Entrywise Sampling of Numerically Sparse Matrices