A Novel Approach to Sinkhorn ε-Annealing: A 3.62x Speedup for the Optimal Transport Problem

Overview

The Optimal Transport Problem arises in fields such as AI, machine learning, computer vision and biology. The problem seeks the cheapest way to transport mass between two distributions.  The Sinkhorn algorithm is the most widely used algorithm for optimal transport due to its speed. It uses ε-annealing to achieve its high speed. ε-annealing is the process of changing the parameter, ε, as the algorithm progresses to switch from fast progression to fine accuracy. Existing methods of ε-annealing predetermine a series of ε to use. To improve on prior, static methods of ε-annealing, I developed an ε-annealer that dynamically calculates the next value of ε to use, based on the numerical behavior of the Sinkhorn algorithm.  Due to the increased adaptability, the novel ε-annealer achieves a 3.62x Speedup over prior methods. This work increases the efficiency of the Sinkhorn algorithm, thus reducing computational costs and durations.

Awards (2)

• Silver Medal
• Selected for CWSF 2026

Competition history

• CWSF 2026 Digital Technology

Related projects

Closest projects by meaning, across every fair and year in the corpus.