On Unbalanced Optimal Transport: An Analysis of Sinkhorn Algorithm
Authors: Khiem Pham, Khang Le, Nhat Ho, Tung Pham, Hung Bui
ICML 2020 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | In this section, we provide empirical evidence to illustrate our proven complexity on both synthetic data and real images. In both examples, we vary ε such that it is small relative to the minimum value of the unregularized UOT function in equation (1) which is computed in advance by using the cvxpy library (Agrawal et al., 2018) with the splitting conic solver option. We then report the two k values: The first k, denoted by kf, follows the stopping rule in Algorithm 1. The second k, denoted by kc, is defined as the minimal kc such that for all later known iterations k kc in the experiment, Algorithm 1 returns an ε-approximation solution of the UOT problem. |
| Researcher Affiliation | Collaboration | 1Vin AI Research 2Department of EECS, University of California, Berkeley 3Faculty of Mathematics, Mechanics and Informatics, Hanoi University of Science, Vietnam National University. |
| Pseudocode | Yes | Algorithm 1 UNBALANCED SINKHORN(C, ε) Input: k = 0 and u0 = v0 = 0 and η = ε/U while k τU ε + 1 h log(8ηR + log(τ(τ + 1)) + 3 log( U do ak = B(uk, vk)1n. bk = B(uk, vk) 1n. if k is even then η + log (a) log ak ητ η + τ vk+1 = vk η + log (b) log bk ητ η + τ uk+1 = uk. end if k = k + 1. end while Output: B(uk, vk). |
| Open Source Code | No | The paper does not provide an explicit statement or link for open-sourcing the code for the described methodology. |
| Open Datasets | Yes | For the MNIST dataset1, we follow similar settings in (Dvurechensky et al., 2018; Altschuler et al., 2017). In particular, the marginals a, b are two flattened images in a pair and the cost matrix C is the matrix of ℓ1 distances between pixel locations. We also add a small constant 10 6 to each pixel with intensity 0, except we do not normalize the marginals. |
| Dataset Splits | No | The paper mentions using 'synthetic data' and 'MNIST data' for experiments and averages results over '10 randomly chosen image pairs' but does not explicitly provide specific details about training/validation/test dataset splits, percentages, or explicit splitting methodology. |
| Hardware Specification | No | The paper does not provide any specific hardware details such as GPU or CPU models, memory, or cloud resources used for running experiments. |
| Software Dependencies | No | The paper mentions the use of 'cvxpy library' but does not provide specific version numbers for any software dependencies. |
| Experiment Setup | Yes | For the simulated example, we choose n = 100 and τ = 5. The elements of the cost matrix C are drawn uniformly from the closed interval [1, 50] while those of the marginal vectors a and b are drawn uniformly from [0.1, 1] and then normalized to have masses 2 and 4, respectively. By varying ε from 1.0 to 10 4... For the MNIST dataset, we follow similar settings... We also add a small constant 10 6 to each pixel with intensity 0... We average the results over 10 randomly chosen image pairs. |