###
A Study of Performance of Optimal Transport (Richard Peng)

Abstract

This talk will discuss recent progresses on computing optimal transport (OT) distances, which are equivalent to node-capacitated min-cost max-flows in bipartite graphs. OT, or Wasserstein, distances between probability distributions have direct applications to learning and clustering, and have recently gained momentum in natural language processing and image retrieval.

The first half of this talk will survey various methods for computing OT, including combinatorial graph algorithms such as network simplex and auction, as well as the widely used Sinkhorn iteration. We then present a new combinatorial algorithm that improves upon the classical Kuhn-Munkres algorithm in the low accuracy regime by leveraging sparsity of the admissible arcs.

The second half of the talk will revolve around theoretical analogs of such sparsity based speedups. We will describe an algorithm that computes exact optimal transport on graphs with n vertices and integer edge weights between [1,W] in randomized O(n^{2 + o(1)} logW) time. This also gives the first runtime improvement for dense bipartite matching in over 30 years. This algorithm is based on combining second-order/interior point methods with dynamic graph sparsification data structures.

Time

2020-07-10 10:00 ~ 12:00

Speaker

Richard Peng, Georgia Institute of Technology

Room

Zoom ID: 61330583950; PW: 123456