PINS: Proximal Iterations with Sparse Newton and Sinkhorn for Optimal Transport

• URL: http://arxiv.org/abs/2502.03749v1
• Date: Thu, 06 Feb 2025 03:21:48 GMT
• Title: PINS: Proximal Iterations with Sparse Newton and Sinkhorn for Optimal Transport
• Authors: Di Wu, Ling Liang, Haizhao Yang,
• Abstract summary: We introduce Proximal Iterations with Sparse Newton and Sinkhorn methods to efficiently compute highly accurate solutions for large-scale OT problems. A reduced computational complexity through overall sparsity and global convergence are guaranteed by rigorous theoretical analysis. Our approach offers three key advantages: it achieves accuracy comparable to exact solutions, progressively accelerates each iteration for greater efficiency, and enhances robustness by reducing sensitivity to regularization parameters.
• Score: 12.551419304993209
• License:
• Abstract: Optimal transport (OT) is a critical problem in optimization and machine learning, where accuracy and efficiency are paramount. Although entropic regularization and the Sinkhorn algorithm improve scalability, they frequently encounter numerical instability and slow convergence, especially when the regularization parameter is small. In this work, we introduce Proximal Iterations with Sparse Newton and Sinkhorn methods (PINS) to efficiently compute highly accurate solutions for large-scale OT problems. A reduced computational complexity through overall sparsity and global convergence are guaranteed by rigorous theoretical analysis. Our approach offers three key advantages: it achieves accuracy comparable to exact solutions, progressively accelerates each iteration for greater efficiency, and enhances robustness by reducing sensitivity to regularization parameters. Extensive experiments confirm these advantages, demonstrating superior performance compared to related methods.

Related papers

• A Novel Unified Parametric Assumption for Nonconvex Optimization [53.943470475510196]
  Non optimization is central to machine learning, but the general framework non convexity enables weak convergence guarantees too pessimistic compared to the other hand. We introduce a novel unified assumption in non convex algorithms.
  arXiv  Detail & Related papers  (2025-02-17T21:25:31Z)
• An inexact Bregman proximal point method and its acceleration version for unbalanced optimal transport [16.12354882333828]
  The Unbalanced Optimal Transport (UOT) problem plays increasingly important roles in computational biology, computational imaging and deep learning. Scaling algorithm is widely used to solve UOT due to its convenience and good convergence properties. We address this challenge by developing an inexact Bregman proximal point method for solving UOT.
  arXiv  Detail & Related papers  (2024-02-26T19:25:21Z)
• 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)
• 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)
• 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)
• Reducing the Variance of Gaussian Process Hyperparameter Optimization with Preconditioning [54.01682318834995]
  Preconditioning is a highly effective step for any iterative method involving matrix-vector multiplication. We prove that preconditioning has an additional benefit that has been previously unexplored. It simultaneously can reduce variance at essentially negligible cost.
  arXiv  Detail & Related papers  (2021-07-01T06:43:11Z)
• Efficient Optimal Transport Algorithm by Accelerated Gradient descent [20.614477547939845]
  We propose a novel algorithm to further improve the efficiency and accuracy based on Nesterov's smoothing technique. The proposed method achieves faster convergence and better accuracy with the same parameter.
  arXiv  Detail & Related papers  (2021-04-12T20:23:29Z)
• Efficient Hyperparameter Tuning with Dynamic Accuracy Derivative-Free Optimization [0.27074235008521236]
  We apply a recent dynamic accuracy derivative-free optimization method to hyperparameter tuning. This method allows inexact evaluations of the learning problem while retaining convergence guarantees. We demonstrate its robustness and efficiency compared to a fixed accuracy approach.
  arXiv  Detail & Related papers  (2020-11-06T00:59:51Z)
• 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)
• Approximate Dynamics Lead to More Optimal Control: Efficient Exact Derivatives [0.0]
  We show here that the computational feasibility of meeting this accuracy requirement depends on the choice of propagation scheme and problem representation. This methodology allows numerically efficient optimization of very high-dimensional dynamics.
  arXiv  Detail & Related papers  (2020-05-20T10:02:19Z)
• Scalable Hyperparameter Optimization with Lazy Gaussian Processes [1.3999481573773074]
  We present a novel, highly accurate approximation of the underlying Gaussian Process. The first experiments show speedups of a factor of 162 in single node and further speed up by a factor of 5 in a parallel environment.
  arXiv  Detail & Related papers  (2020-01-16T10:15:55Z)

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.