cuRegOT: A GPU-Accelerated Solver for Entropic-Regularized Optimal Transport

• URL: http://arxiv.org/abs/2605.08793v1
• Date: Sat, 09 May 2026 08:27:39 GMT
• Title: cuRegOT: A GPU-Accelerated Solver for Entropic-Regularized Optimal Transport
• Abstract summary: cuRegOT is a high-performance GPU solver tailored for entropic-regularized OT.<n>We introduce a suite of algorithmic and architectural optimizations, including an amortized symbolic analysis strategy to mitigate CPU bottlenecks.<n>CuRegOT achieves significant speedups over state-of-the-art GPU-based solvers across a variety of benchmark tasks.
• Score: 8.189956090077677
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Optimal transport (OT) has emerged as a fundamental tool in modern machine learning, yet its computational cost remains a significant bottleneck for large-scale applications. While harnessing the massive parallelism of modern GPU hardware is critical for efficiency, the de facto standard Sinkhorn algorithm, despite its ease of parallelization, often suffers from slow convergence in challenging problems. More recently, the sparse-plus-low-rank quasi-Newton method offers a balance between convergence rate and per-iteration complexity; however, its efficiency on GPUs is severely hindered by the serial nature of sparse matrix symbolic analysis and irregular memory access patterns. To bridge this gap, we present cuRegOT, a high-performance GPU solver tailored for entropic-regularized OT. We introduce a suite of algorithmic and architectural optimizations, including an amortized symbolic analysis strategy to mitigate CPU bottlenecks, an asynchronous Sinkhorn iterates generation mechanism, and a fused kernel for bandwidth-efficient gradient evaluation. These strategies are backed by rigorous theoretical guarantees ensuring algorithmic convergence. Extensive numerical experiments demonstrate that cuRegOT achieves significant speedups over state-of-the-art GPU-based solvers across a variety of benchmark tasks.

Related papers

• Accelerated Decoding of Centroid Positional Encoding for Instance Segmentation [49.97373153077311]
  We investigate the decoding overhead associated with a centroid encoding for Instance, in which each pixel regresses a positional embedding of its instance centroid.<n>Our solution significantly reduces decoding overhead and improves Endto-End latency, outperforming both CPU-based approaches and naive GPU implementations.
  arXiv  Detail & Related papers  (2026-09-15T09:05:17Z)
• Fine-Grain GPU Parallelization of the Generalized Partition Crossover for Large-Scale Traveling Salesman Problems [1.160208922584163]
  The Traveling Salesman Problem (TSP) is one of the most extensively studied NP-hard optimization problems.<n>The proposed approach reformulates GPX as a graph-parallel problem using coalesced memory layouts, ghost-node transformations, and connected-node analysis.<n>The proposed GPU achieves speedups between 48x and 625x while significantly reducing memory overhead.
  arXiv  Detail & Related papers  (2026-08-21T15:42:05Z)
• Fast Log-Domain Sinkhorn Optimal Transport with Warp-Level GPU Reductions [1.6679662639178268]
  We present FastSinkhorn, a lightweight, native implementation of the log-domain Sinkhorn algorithm.<n>Our solver operates entirely in the log-domain, enabling computation for regularization parameters as small as epsilon = 10-4 where standard-domain methods fail.<n>We validate our solver on image color transfer, 3D point cloud matching, and convergence analysis, demonstrating that native kernels with careful numerical treatment provide a practical and efficient foundation for large-scale optimal transport.
  arXiv  Detail & Related papers  (2026-04-04T16:06:27Z)
• Parallel-in-Time Nonlinear Optimal Control via GPU-native Sequential Convex Programming [2.8852807790754618]
  We introduce a fully GPU-native trajectory optimization framework that combines sequential convex programming with a consensus-based alternating direction method of multipliers.<n>We validate the solver on a quadrotor agile flight task and a Mars powered descent problem using an on-board edge computing platform.<n> Benchmarks reveal a sustained 4x throughput speedup and a 51% reduction in energy consumption over a heavily optimized 12-core CPU baseline.
  arXiv  Detail & Related papers  (2026-03-11T12:39:14Z)
• Fully Tensorized GPU-accelerated Multi-population Evolutionary Algorithm for Constrained Multiobjective Optimization Problems [12.480139972771964]
  This paper proposes a GPU-accelerated multi-population evolutionary algorithm, termed GMPEA.<n>We first analyze the performance bottlenecks of representative CMOEAs when implemented in a GPU environment.<n>To address the trade-off between computational speed and solution performance, GMPEA introduces a decomposition-based multi-population approach that is fully parallelized across its entire workflow.
  arXiv  Detail & Related papers  (2025-09-24T07:06:14Z)
• A Truncated Newton Method for Optimal Transport [13.848861021326755]
  We introduce a specialized truncated Newton algorithm for entropic-regularized optimal transport (OT) solvers.<n>Our algorithm exhibits exceptionally favorable runtime performance, achieving high precision orders of magnitude faster than many existing alternatives.<n>The scalability of the algorithm is showcased on an extremely large OT problem with $n approx 106$, solved approximately under weak entopric regularization.
  arXiv  Detail & Related papers  (2025-04-02T19:00:24Z)
• Scalable Signature Kernel Computations for Long Time Series via Local Neumann Series Expansions [46.685771141109306]
  The signature kernel is a recent state-of-the-art tool for analyzing high-dimensional sequential data.<n>We present a novel method for efficiently computing the signature kernel of long, high-dimensional time series.<n>This method achieves substantial performance improvements over state-of-the-art approaches for computing the signature kernel.
  arXiv  Detail & Related papers  (2025-02-27T18:59:20Z)
• Fast, Scalable, Warm-Start Semidefinite Programming with Spectral Bundling and Sketching [53.91395791840179]
  We present Unified Spectral Bundling with Sketching (USBS), a provably correct, fast and scalable algorithm for solving massive SDPs. USBS provides a 500x speed-up over the state-of-the-art scalable SDP solver on an instance with over 2 billion decision variables.
  arXiv  Detail & Related papers  (2023-12-19T02:27:22Z)
• Stochastic Optimization for Non-convex Problem with Inexact Hessian Matrix, Gradient, and Function [99.31457740916815]
  Trust-region (TR) and adaptive regularization using cubics have proven to have some very appealing theoretical properties. We show that TR and ARC methods can simultaneously provide inexact computations of the Hessian, gradient, and function values.
  arXiv  Detail & Related papers  (2023-10-18T10:29:58Z)
• Implementation of Parallel Simplified Swarm Optimization in CUDA [2.322689362836168]
  In optimization computing, intelligent swarm algorithms (SIAs) method is suitable for parallelization. This paper proposed a GPU-based Simplified Swarm Algorithm Optimization (PSSO) based on the platform considering computational ability and versatility. As the results showed, the time complexity has successfully reduced by an order of magnitude of N, and the problem of resource preemption was avoided entirely.
  arXiv  Detail & Related papers  (2021-10-01T00:15:45Z)
• Distributed stochastic optimization with large delays [59.95552973784946]
  One of the most widely used methods for solving large-scale optimization problems is distributed asynchronous gradient descent (DASGD) We show that DASGD converges to a global optimal implementation model under same delay assumptions.
  arXiv  Detail & Related papers  (2021-07-06T21:59:49Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  We propose two single-timescale single-loop algorithms that require only one data point each step. Our results are expressed in a form of simultaneous primal and dual side convergence.
  arXiv  Detail & Related papers  (2020-08-23T20:36:49Z)
• Kernel methods through the roof: handling billions of points efficiently [94.31450736250918]
  Kernel methods provide an elegant and principled approach to nonparametric learning, but so far could hardly be used in large scale problems. Recent advances have shown the benefits of a number of algorithmic ideas, for example combining optimization, numerical linear algebra and random projections. Here, we push these efforts further to develop and test a solver that takes full advantage of GPU hardware.
  arXiv  Detail & Related papers  (2020-06-18T08:16:25Z)

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.