Designing Algorithms for Entropic Optimal Transport from an Optimisation Perspective

• URL: http://arxiv.org/abs/2507.12246v1
• Date: Wed, 16 Jul 2025 13:56:11 GMT
• Title: Designing Algorithms for Entropic Optimal Transport from an Optimisation Perspective
• Authors: Vishwak Srinivasan, Qijia Jiang,
• Abstract summary: We develop a collection of novel methods for the entropic-regularised optimal transport problem.<n>We are inspired by existing mirror interpretations of the Sinkhorn problem.<n>The broader we develop based on over the joint distributions also finds an analogue in the Schr"odinger bridge problem.
• Score: 12.343553053539976
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this work, we develop a collection of novel methods for the entropic-regularised optimal transport problem, which are inspired by existing mirror descent interpretations of the Sinkhorn algorithm used for solving this problem. These are fundamentally proposed from an optimisation perspective: either based on the associated semi-dual problem, or based on solving a non-convex constrained problem over subset of joint distributions. This optimisation viewpoint results in non-asymptotic rates of convergence for the proposed methods under minimal assumptions on the problem structure. We also propose a momentum-equipped method with provable accelerated guarantees through this viewpoint, akin to those in the Euclidean setting. The broader framework we develop based on optimisation over the joint distributions also finds an analogue in the dynamical Schr\"{o}dinger bridge problem.

Related papers

• Analyzing and Enhancing the Backward-Pass Convergence of Unrolled Optimization [50.38518771642365]
  The integration of constrained optimization models as components in deep networks has led to promising advances on many specialized learning tasks. A central challenge in this setting is backpropagation through the solution of an optimization problem, which often lacks a closed form. This paper provides theoretical insights into the backward pass of unrolled optimization, showing that it is equivalent to the solution of a linear system by a particular iterative method. A system called Folded Optimization is proposed to construct more efficient backpropagation rules from unrolled solver implementations.
  arXiv  Detail & Related papers  (2023-12-28T23:15:18Z)
• A Deep Unrolling Model with Hybrid Optimization Structure for Hyperspectral Image Deconvolution [50.13564338607482]
  We propose a novel optimization framework for the hyperspectral deconvolution problem, called DeepMix.<n>It consists of three distinct modules, namely, a data consistency module, a module that enforces the effect of the handcrafted regularizers, and a denoising module.<n>This work proposes a context aware denoising module designed to sustain the advancements achieved by the cooperative efforts of the other modules.
  arXiv  Detail & Related papers  (2023-06-10T08:25:16Z)
• Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
  This paper studies first-order algorithms for solving fully composite optimization problems convex compact sets. We leverage the structure of the objective by handling differentiable and non-differentiable separately, linearizing only the smooth parts.
  arXiv  Detail & Related papers  (2023-02-24T18:41:48Z)
• Backpropagation of Unrolled Solvers with Folded Optimization [55.04219793298687]
  The integration of constrained optimization models as components in deep networks has led to promising advances on many specialized learning tasks. One typical strategy is algorithm unrolling, which relies on automatic differentiation through the operations of an iterative solver. This paper provides theoretical insights into the backward pass of unrolled optimization, leading to a system for generating efficiently solvable analytical models of backpropagation.
  arXiv  Detail & Related papers  (2023-01-28T01:50:42Z)
• Rapid quantum approaches for combinatorial optimisation inspired by optimal state-transfer [3.591122855617648]
  We propose a new design to tackle optimisation problems, inspired by Hamiltonians for optimal state-transfer. We provide numerical evidence of the success of this new design.
  arXiv  Detail & Related papers  (2023-01-17T12:45:09Z)
• Adaptive Stochastic Optimisation of Nonconvex Composite Objectives [2.1700203922407493]
  We propose and analyse a family of generalised composite mirror descent algorithms. With adaptive step sizes, the proposed algorithms converge without requiring prior knowledge of the problem. We exploit the low-dimensional structure of the decision sets for high-dimensional problems.
  arXiv  Detail & Related papers  (2022-11-21T18:31:43Z)
• Adaptive Zeroth-Order Optimisation of Nonconvex Composite Objectives [1.7640556247739623]
  We analyze algorithms for zeroth-order entropy composite objectives, focusing on dependence on dimensionality. This is achieved by exploiting low dimensional structure of the decision set using the mirror descent method with an estimation alike function. To improve the gradient, we replace the classic sampling method based on Rademacher and show that the mini-batch method copes with non-Eucli geometry.
  arXiv  Detail & Related papers  (2022-08-09T07:36:25Z)
• Outlier-Robust Sparse Estimation via Non-Convex Optimization [73.18654719887205]
  We explore the connection between high-dimensional statistics and non-robust optimization in the presence of sparsity constraints. We develop novel and simple optimization formulations for these problems. As a corollary, we obtain that any first-order method that efficiently converges to station yields an efficient algorithm for these tasks.
  arXiv  Detail & Related papers  (2021-09-23T17:38:24Z)
• Optimization on manifolds: A symplectic approach [127.54402681305629]
  We propose a dissipative extension of Dirac's theory of constrained Hamiltonian systems as a general framework for solving optimization problems. Our class of (accelerated) algorithms are not only simple and efficient but also applicable to a broad range of contexts.
  arXiv  Detail & Related papers  (2021-07-23T13:43:34Z)
• A Contraction Theory Approach to Optimization Algorithms from Acceleration Flows [1.90365714903665]
  We use contraction theory to provide a principled methodology to design and discretize appropriate ODEs. We propose a novel system of ODEs, namely the Accelerated-Contracting-Nesterov flow. Remarkably, a simple explicit Euler discretization of this flow corresponds to the Nesterov acceleration method.
  arXiv  Detail & Related papers  (2021-05-18T21:11:37Z)
• IDEAL: Inexact DEcentralized Accelerated Augmented Lagrangian Method [64.15649345392822]
  We introduce a framework for designing primal methods under the decentralized optimization setting where local functions are smooth and strongly convex. Our approach consists of approximately solving a sequence of sub-problems induced by the accelerated augmented Lagrangian method. When coupled with accelerated gradient descent, our framework yields a novel primal algorithm whose convergence rate is optimal and matched by recently derived lower bounds.
  arXiv  Detail & Related papers  (2020-06-11T18:49:06Z)
• Distributed Averaging Methods for Randomized Second Order Optimization [54.51566432934556]
  We consider distributed optimization problems where forming the Hessian is computationally challenging and communication is a bottleneck. We develop unbiased parameter averaging methods for randomized second order optimization that employ sampling and sketching of the Hessian. We also extend the framework of second order averaging methods to introduce an unbiased distributed optimization framework for heterogeneous computing systems.
  arXiv  Detail & Related papers  (2020-02-16T09:01:18Z)

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.