A Riemannian Approach to Low-Rank Optimal Transport

• URL: http://arxiv.org/abs/2606.12120v1
• Date: Wed, 10 Jun 2026 14:17:08 GMT
• Title: A Riemannian Approach to Low-Rank Optimal Transport
• Abstract summary: Low-rank optimal transport (OT) mitigates the quadratic scaling of classical solvers, yet existing approaches rely heavily on first-order mirror-descent updates.<n>We propose a unified Riemannian geometric framework for low-rank OT, modeling balanced and unbalanced rank-$r$ positive factored couplings.<n>Our regularization-free first- and second-order solvers achieve faster convergence and superior performance over existing state-of-the-art low-rank OT solvers.
• Score: 10.296598409953278
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Low-rank optimal transport (OT) mitigates the quadratic scaling of classical solvers, yet existing approaches rely heavily on first-order mirror-descent updates that require careful hyperparameter tuning and ignore the optimization landscape's curvature. To address these limitations, we propose a unified Riemannian geometric framework for low-rank OT, modeling balanced and unbalanced rank-$r$ positive factored couplings as novel smooth embedded submanifolds of the positive orthant. By equipping these manifolds with the Fisher-Rao product metric, we derive tractable formulations for Riemannian projectors, retractions, and Hessian-vector products. Our cost-agnostic framework seamlessly extends to linear OT, Gromov-Wasserstein (GW), fused GW, and their unbalanced counterparts. For balanced OT, our geometric ingredients are computed via efficient conjugate-gradient and iterative Bregman updates. For the unbalanced OT, our operations elegantly reduce to closed-form scalings, completely eliminating inner iterative loops. In both regimes, per-iteration complexity scales linearly with dataset size, and we provide a rank-sufficiency certificate for global optimality verification. Extensive experiments across a range of problem sizes demonstrate that our regularization-free first- and second-order solvers achieve faster convergence and superior performance over existing state-of-the-art low-rank OT solvers.

Related papers

• Retraction-Free Optimization over the Stiefel Manifold for the LoRA Fine-Tuning [17.71677083154088]
  datasets over the Stiefel play a significant role in various machine learning tasks.<n>Existing methods either use the manifold operators, requiring costly orthonormalization for large-scale matrices, or employ manifold tuning methods.
  arXiv  Detail & Related papers  (2026-07-28T05:22:39Z)
• RODR: Riemannian Orthogonally Decoupled Regularization for Disentangled Manifold Representation [0.91963810502252]
  We introduce a generic and interpretable framework for disentangled geometric optimization in point cloud processing.<n> Experiments demonstrate that RODR reaches performance comparable to state-of-the-art baselines.
  arXiv  Detail & Related papers  (2026-07-27T03:12:14Z)
• GPU-friendly and Linearly Convergent First-order Methods for Certifying Optimal $k$-sparse GLMs [7.079949618914198]
  Branch-and-Bound (BnB) frameworks can certify optimality using perspective relaxations.<n>Existing methods for solving these relaxations are computationally intensive, limiting their scalability.<n>We develop a unified proximal framework that is both linearly convergent and computationally efficient.
  arXiv  Detail & Related papers  (2026-03-01T22:26:09Z)
• Optimal Transportation and Alignment Between Gaussian Measures [80.4634530260329]
  Optimal transport (OT) and Gromov-Wasserstein (GW) alignment provide interpretable geometric frameworks for datasets.<n>Because these frameworks are computationally expensive, large-scale applications often rely on closed-form solutions for Gaussian distributions under quadratic cost.<n>This work provides a comprehensive treatment of Gaussian, quadratic cost OT and inner product GW (IGW) alignment, closing several gaps in the literature to broaden applicability.
  arXiv  Detail & Related papers  (2025-12-03T09:01:48Z)
• LoRA meets Riemannion: Muon Optimizer for Parametrization-independent Low-Rank Adapters [43.04933165005961]
  We present a novel framework for Low-Rank Adaptation (LoRA)<n>LoRA geometrically treats low-rank adapters by optimizing them directly on the fixed-rank manifold.<n>Our framework integrates three key components to achieve this.
  arXiv  Detail & Related papers  (2025-07-16T11:17:12Z)
• Retraction-Free Decentralized Non-convex Optimization with Orthogonal Constraints [12.414718831844041]
  We propose the first decentralized version of retraction-free landing algorithm, called textbfDecentralized textbfRetraction-textbfFree textbfGradient textbfTracking (DRFGT)<n>Experiments demonstrate that DRFGT performs on par with the state-of-the-art retraction-based methods with substantially reduced computational overhead.
  arXiv  Detail & Related papers  (2024-05-19T15:50:57Z)
• Stable Nonconvex-Nonconcave Training via Linear Interpolation [51.668052890249726]
  This paper presents a theoretical analysis of linearahead as a principled method for stabilizing (large-scale) neural network training. We argue that instabilities in the optimization process are often caused by the nonmonotonicity of the loss landscape and show how linear can help by leveraging the theory of nonexpansive operators.
  arXiv  Detail & Related papers  (2023-10-20T12:45:12Z)
• 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.<n>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)
• STORM+: Fully Adaptive SGD with Momentum for Nonconvex Optimization [74.1615979057429]
  We investigate non-batch optimization problems where the objective is an expectation over smooth loss functions. Our work builds on the STORM algorithm, in conjunction with a novel approach to adaptively set the learning rate and momentum parameters.
  arXiv  Detail & Related papers  (2021-11-01T15:43:36Z)
• Unbalanced Optimal Transport through Non-negative Penalized Linear Regression [9.668391961887027]
  We show that the corresponding optimization problem can be reformulated as a non-negative penalized linear regression problem. We propose novel algorithms inspired from inverse problems and nonnegative matrix factorization. We derive for the first time an efficient algorithm to compute the regularization path of UOT with quadratic penalties.
  arXiv  Detail & Related papers  (2021-06-08T07:16:37Z)
• Balancing Rates and Variance via Adaptive Batch-Size for Stochastic Optimization Problems [120.21685755278509]
  In this work, we seek to balance the fact that attenuating step-size is required for exact convergence with the fact that constant step-size learns faster in time up to an error. Rather than fixing the minibatch the step-size at the outset, we propose to allow parameters to evolve adaptively.
  arXiv  Detail & Related papers  (2020-07-02T16:02:02Z)
• Support recovery and sup-norm convergence rates for sparse pivotal estimation [79.13844065776928]
  In high dimensional sparse regression, pivotal estimators are estimators for which the optimal regularization parameter is independent of the noise level. We show minimax sup-norm convergence rates for non smoothed and smoothed, single task and multitask square-root Lasso-type estimators.
  arXiv  Detail & Related papers  (2020-01-15T16:11:04Z)

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.