Combinatorics and Computing Weekly Seminar
Algorithmic Optimal Transport in High Dimensions
Algorithmic Optimal Transport in High Dimensions
Omid Etesami, IPM
9 OCT 2024
14:00 - 15:00
Optimal transport is the problem of moving a mass of objects from an initial mass distribution to a final mass distribution with minimum cost. The input to the problem is the initial and final distributions, as well as the distance metric or cost of transportation between each initial position and each final position. We should match points in the initial mass with points in the final mass so as to minimize the total cost. This problem was first proposed in the context of economics and recently in the context of machine learning to compare and transform probability distributions. I shall mainly talk about these applications.
If I have time, in the second part of the lecture, I will talk about a new method for computing transportations between distributions in high dimensions. This approach is different from previous works in that it does not assume that the distributions are given explicitly. Rather, it assumes that we can just query or sample the distribution (through what is often called an oracle in the computer science literature.) This allows the method to work for inputs that may be exponentially larger than explicitly given inputs. The simple main technique behind our method is to change the components in the initial vector point one by one and as little as possible, while making sure we attain the final distribution. Our method can be turned into a specific algorithm for some parameterized classes of distributions and distance metrics. For each class, our method only guarantees that the transportation cost is not worse than the optimal transport of a worst-case instance among that class up to a constant multiplicative factor. This work is related to previous work on computational concentration of measure, which appeared in the context of adversarial machine learning. The second part of this talk is joint work with Salman Beigi, Mohammad Mahmoody, and Amir Najafi and is work in progress.
Zoom room information:
https://us06web.zoom.us/j/85237260136?pwd=MFSZoKdmRXAjfaSaBzbf19lTaaKglf.1
Meeting ID: 852 3726 0136
Passcode: 362880
Venue: Niavaran, Lecture Hall 1