EUVIMEDEUVIMED entdecken
Crossref

Robust First- and Second-Order Differentiation for Regularized Optimal Transport

Xingjie Li, Fei Lu, Molei Tao, Felix X.-F. Ye

SIAM Journal on Scientific Computing · 30.06.2025 · 47 (3) · C630-C654

DOI: 10.1137/24m1674030 ↗

Kurz gefasst

Fachartikel in der Zeitschrift SIAM Journal on Scientific Computing, online erschienen am 07.05.2025. Verfasst von Xingjie Li und 3 weiteren Autor:innen. Die Arbeit wurde bisher 2-mal zitiert (Crossref) und nennt 39 Literaturangaben. Gefördert von: University of North Carolina at Charlotte, National Science Foundation, Cullen-Peck Scholar Award.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Applications such as unbalanced and fully shuffled regression can be approached by optimizing regularized optimal transport (OT) distances, such as the entropic OT and Sinkhorn distances. A common approach for this optimization is to use a first-order optimizer, which requires the gradient of the OT distance. For faster convergence, one might also resort to a second-order optimizer, which additionally requires the Hessian. The computations of these derivatives are crucial for efficient and accurate optimization. However, they present significant challenges in terms of memory consumption and numerical instability, especially for large datasets and small regularization strengths. We circumvent these issues by analytically computing the gradients for OT distances and the Hessian for the entropic OT distance, which was not previously used due to intricate tensorwise calculations and the complex dependency on parameters within the bi-level loss function. Through analytical derivation and spectral analysis, we identify and resolve the numerical instability caused by the singularity and ill-posedness of a key linear system. Consequently, we achieve scalable and stable computation of the Hessian, enabling the implementation of the stochastic gradient descent (SGD)-Newton methods. Tests on shuffled regression examples demonstrate that the second stage of the SGD-Newton method converges orders of magnitude faster than the gradient descent-only method while achieving significantly more accurate parameter estimations. Reproducibility of computational results. This paper has been awarded the “SIAM Reproducibility Badge: Code and data available” as a recognition that the authors have followed reproducibility principles valued by SISC and the scientific computing community. Code and data that allow readers to reproduce the results in this paper are available at https://github.com/yexf308/OTT-Hessian and in the supplementary materials ( M167403_supp.pdf [272KB], OTT-Hessian.zip [3.33MB]). [Formula: see text]

Förderung

  • University of North Carolina at Charlotte
  • National Science Foundation
  • Cullen-Peck Scholar Award
  • Emory-GT AI Humanity Award
  • Simons Foundation

Zitieren

APA

Li, X., Lu, F., Tao, M., & Ye, F. X. (2025). Robust First- and Second-Order Differentiation for Regularized Optimal Transport. SIAM Journal on Scientific Computing, 47(3), C630-C654. https://doi.org/10.1137/24m1674030

Vancouver

Li X, Lu F, Tao M, Ye FX. Robust First- and Second-Order Differentiation for Regularized Optimal Transport. SIAM Journal on Scientific Computing. 2025;47(3):C630-C654. doi:10.1137/24m1674030

BibTeX
@article{Li2025,
  author = {Li, Xingjie and Lu, Fei and Tao, Molei and Ye, Felix X.-F.},
  title = {Robust First- and Second-Order Differentiation for Regularized Optimal Transport},
  journal = {SIAM Journal on Scientific Computing},
  year = {2025},
  volume = {47},
  number = {3},
  pages = {C630--C654},
  doi = {10.1137/24m1674030}
}
Kostenlos starten →