On the Convergence of Projected Alternating Maximization for Equitable and Optimal Transport

• URL: http://arxiv.org/abs/2109.15030v2
• Date: Fri, 1 Oct 2021 01:00:36 GMT
• Title: On the Convergence of Projected Alternating Maximization for Equitable and Optimal Transport
• Authors: Minhui Huang, Shiqian Ma and Lifeng Lai
• Abstract summary: This paper studies the equitable and optimal transport (EOT) problem, which has many applications. In the discrete distributions case, the EOT problem can be formulated as a linear program (LP) Since this LP is prohibitively large for general solvers, Scetbon etal citescetbonequitable suggests to perturb the problem by adding an entropy regularization. They proposed a projected alternating algorithm (PAM) to solve the dual of the entropy regularized EOT.
• Score: 36.97843660480747
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper studies the equitable and optimal transport (EOT) problem, which has many applications such as fair division problems and optimal transport with multiple agents etc. In the discrete distributions case, the EOT problem can be formulated as a linear program (LP). Since this LP is prohibitively large for general LP solvers, Scetbon \etal \cite{scetbon2021equitable} suggests to perturb the problem by adding an entropy regularization. They proposed a projected alternating maximization algorithm (PAM) to solve the dual of the entropy regularized EOT. In this paper, we provide the first convergence analysis of PAM. A novel rounding procedure is proposed to help construct the primal solution for the original EOT problem. We also propose a variant of PAM by incorporating the extrapolation technique that can numerically improve the performance of PAM. Results in this paper may shed lights on block coordinate (gradient) descent methods for general optimization problems.

Related papers

• Towards Efficient Pareto-optimal Utility-Fairness between Groups in Repeated Rankings [7.6275971668447005]
  We tackle the problem of computing a sequence of rankings with the guarantee of the Pareto-optimal balance between consumers and producers of items. We introduce a novel approach to the above problem by using the Expohedron - a permutahedron whose points represent all exposures of items. We further propose an efficient method by relaxing our optimization problem on the Expohedron's circumscribed $n$-sphere, which significantly improve the running time.
  arXiv  Detail & Related papers  (2024-02-22T05:48:54Z)
• Energy-Guided Continuous Entropic Barycenter Estimation for General Costs [95.33926437521046]
  We propose a novel algorithm for approximating the continuous Entropic OT (EOT) barycenter for arbitrary OT cost functions. Our approach is built upon the dual reformulation of the EOT problem based on weak OT.
  arXiv  Detail & Related papers  (2023-10-02T11:24:36Z)
• Moreau-Yoshida Variational Transport: A General Framework For Solving Regularized Distributional Optimization Problems [3.038642416291856]
  We consider a general optimization problem of minimizing a composite objective functional defined over a class probability distributions. We propose a novel method, dubbed as Moreau-Yoshida Variational Transport (MYVT), for solving the regularized distributional optimization problem.
  arXiv  Detail & Related papers  (2023-07-31T01:14:42Z)
• Safe Screening for Unbalanced Optimal Transport [17.489075240435348]
  We demonstrate the feasibility of applying Safe Screening to the UOT problem with $ell$-penalty and KL-penalty. We specifically propose a novel approximate projection, an elliptical safe region, and a two-hyperplane relaxation method. These enhancements significantly improve the screening efficiency for the UOT's without altering the algorithm's complexity.
  arXiv  Detail & Related papers  (2023-07-01T06:22:14Z)
• Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
  Efficient computation of the optimal transport distance between two distributions serves as an algorithm that empowers various applications. This paper develops a scalable first-order optimization-based method that computes optimal transport to within $varepsilon$ additive accuracy.
  arXiv  Detail & Related papers  (2023-01-30T15:46:39Z)
• Entropic Neural Optimal Transport via Diffusion Processes [105.34822201378763]
  We propose a novel neural algorithm for the fundamental problem of computing the entropic optimal transport (EOT) plan between continuous probability distributions. Our algorithm is based on the saddle point reformulation of the dynamic version of EOT which is known as the Schr"odinger Bridge problem. In contrast to the prior methods for large-scale EOT, our algorithm is end-to-end and consists of a single learning step.
  arXiv  Detail & Related papers  (2022-11-02T14:35:13Z)
• A Dual Approach to Constrained Markov Decision Processes with Entropy Regularization [7.483040617090451]
  We study entropy-regularized constrained Markov decision processes (CMDPs) under the soft-max parameterization. Our theoretical analysis shows that its Lagrangian dual function is smooth and the Lagrangian duality gap can be decomposed into the primality gap and the constraint violation.
  arXiv  Detail & Related papers  (2021-10-17T21:26:40Z)
• Two-Stage Stochastic Optimization via Primal-Dual Decomposition and Deep Unrolling [86.85697555068168]
  Two-stage algorithmic optimization plays a critical role in various engineering and scientific applications. There still lack efficient algorithms, especially when the long-term and short-term variables are coupled in the constraints. We show that PDD-SSCA can achieve superior performance over existing solutions.
  arXiv  Detail & Related papers  (2021-05-05T03:36:00Z)
• Variational Optimization for the Submodular Maximum Coverage Problem [11.734438054316147]
  We provide the first variational approximation for this problem based on the Nemhauser divergence. We empirically evaluate it on a number of public data sets and several application tasks.
  arXiv  Detail & Related papers  (2020-06-10T00:50:25Z)
• Joint Wasserstein Distribution Matching [89.86721884036021]
  Joint distribution matching (JDM) problem, which aims to learn bidirectional mappings to match joint distributions of two domains, occurs in many machine learning and computer vision applications. We propose to address JDM problem by minimizing the Wasserstein distance of the joint distributions in two domains. We then propose an important theorem to reduce the intractable problem into a simple optimization problem, and develop a novel method to solve it.
  arXiv  Detail & Related papers  (2020-03-01T03:39:00Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.