A Survey on Algorithmic Developments in Optimal Transport Problem with Applications

• URL: http://arxiv.org/abs/2501.06247v1
• Date: Wed, 08 Jan 2025 18:06:30 GMT
• Title: A Survey on Algorithmic Developments in Optimal Transport Problem with Applications
• Authors: Sina Moradi,
• Abstract summary: Optimal Transport (OT) has established itself as a robust framework for quantifying differences between distributions. This paper offers a detailed examination of the OT problem, beginning with its theoretical foundations. It explores cutting-edge algorithms, including Sinkhorn iterations, primal-dual strategies, and reduction-based approaches.
• Score: 0.0
• License:
• Abstract: Optimal Transport (OT) has established itself as a robust framework for quantifying differences between distributions, with applications that span fields such as machine learning, data science, and computer vision. This paper offers a detailed examination of the OT problem, beginning with its theoretical foundations, including the classical formulations of Monge and Kantorovich and their extensions to modern computational techniques. It explores cutting-edge algorithms, including Sinkhorn iterations, primal-dual strategies, and reduction-based approaches, emphasizing their efficiency and scalability in addressing high-dimensional problems. The paper also highlights emerging trends, such as integrating OT into machine learning frameworks, the development of novel problem variants, and ongoing theoretical advancements. Applications of OT are presented across a range of domains, with particular attention to its innovative application in time series data analysis via Optimal Transport Warping (OTW), a robust alternative to methods like Dynamic Time Warping. Despite the significant progress made, challenges related to scalability, robustness, and ethical considerations remain, necessitating further research. The paper underscores OT's potential to bridge theoretical depth and practical utility, fostering impactful advancements across diverse disciplines.

Related papers

• Deep Learning Models for Physical Layer Communications [3.1727619150610837]
  This thesis aims at solving some fundamental open challenges in physical layer communications exploiting new deep learning paradigms. We mathematically formulate, under ML terms, classic problems such as channel capacity and optimal coding-decoding schemes. We design and develop the architecture, algorithm and code necessary to train the equivalent deep learning model.
  arXiv  Detail & Related papers  (2025-02-07T13:03:36Z)
• A Statistical Learning Perspective on Semi-dual Adversarial Neural Optimal Transport Solvers [65.28989155951132]
  In this paper, we establish upper bounds on the generalization error of an approximate OT map recovered by the minimax quadratic OT solver. While our analysis focuses on the quadratic OT, we believe that similar bounds could be derived for more general OT formulations.
  arXiv  Detail & Related papers  (2025-02-03T12:37:20Z)
• Differentiable Convex Optimization Layers in Neural Architectures: Foundations and Perspectives [0.0]
  The integration of optimization problems within neural network architectures represents a shift from traditional approaches to handling constraints in deep learning. A recent advance in this field has enabled the direct embedding of optimization layers as differentiable components within deep networks. This work synthesizes developments at the intersection of optimization theory and deep learning, offering insights into both current capabilities and future research directions.
  arXiv  Detail & Related papers  (2024-12-30T03:18:24Z)
• State-Space Modeling in Long Sequence Processing: A Survey on Recurrence in the Transformer Era [59.279784235147254]
  This survey provides an in-depth summary of the latest approaches that are based on recurrent models for sequential data processing. The emerging picture suggests that there is room for thinking of novel routes, constituted by learning algorithms which depart from the standard Backpropagation Through Time.
  arXiv  Detail & Related papers  (2024-06-13T12:51:22Z)
• Bridging the Gap Between Theory and Practice: Benchmarking Transfer Evolutionary Optimization [31.603211545949414]
  This paper pioneers a practical TrEO benchmark suite, integrating problems from the literature categorized based on the three essential aspects of Big Source Task-Instances: volume, variety, and velocity. Our primary objective is to provide a comprehensive analysis of existing TrEO algorithms and pave the way for the development of new approaches to tackle practical challenges.
  arXiv  Detail & Related papers  (2024-04-20T13:34:46Z)
• The Efficiency Spectrum of Large Language Models: An Algorithmic Survey [54.19942426544731]
  The rapid growth of Large Language Models (LLMs) has been a driving force in transforming various domains. This paper examines the multi-faceted dimensions of efficiency essential for the end-to-end algorithmic development of LLMs.
  arXiv  Detail & Related papers  (2023-12-01T16:00:25Z)
• Foundations and Recent Trends in Multimodal Machine Learning: Principles, Challenges, and Open Questions [68.6358773622615]
  This paper provides an overview of the computational and theoretical foundations of multimodal machine learning. We propose a taxonomy of 6 core technical challenges: representation, alignment, reasoning, generation, transference, and quantification. Recent technical achievements will be presented through the lens of this taxonomy, allowing researchers to understand the similarities and differences across new approaches.
  arXiv  Detail & Related papers  (2022-09-07T19:21:19Z)
• Low-rank Optimal Transport: Approximation, Statistics and Debiasing [51.50788603386766]
  Low-rank optimal transport (LOT) approach advocated in citescetbon 2021lowrank LOT is seen as a legitimate contender to entropic regularization when compared on properties of interest. We target each of these areas in this paper in order to cement the impact of low-rank approaches in computational OT.
  arXiv  Detail & Related papers  (2022-05-24T20:51:37Z)
• A Survey on Optimal Transport for Machine Learning: Theory and Applications [1.1279808969568252]
  Optimal Transport (OT) theory has seen an increasing amount of attention from the computer science community. We present a brief introduction and history, a survey of previous work and propose directions of future study.
  arXiv  Detail & Related papers  (2021-06-03T16:10:42Z)
• Constraint Programming Algorithms for Route Planning Exploiting Geometrical Information [91.3755431537592]
  We present an overview of our current research activities concerning the development of new algorithms for route planning problems. The research so far has focused in particular on the Euclidean Traveling Salesperson Problem (Euclidean TSP) The aim is to exploit the results obtained also to other problems of the same category, such as the Euclidean Vehicle Problem (Euclidean VRP), in the future.
  arXiv  Detail & Related papers  (2020-09-22T00:51:45Z)

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.