Efficient Algorithms for Robust and Partial Semi-Discrete Optimal Transport

The sensitivity of optimal transport (OT) to noise has motivated the study of robust variants. In this paper, we study two such formulations of semi-discrete OT in R d : (i) the α-optimal partial transport, which minimizes the cost of transporting a mass of α; and (ii) the λ-robust optimal transport, which regularizes the OT problem using the total variation (TV) distance. First, we provide a novel characterization of the optimal solutions in these settings, showing they can be represented as a restricted Laguerre diagram. Second, we exploit this characterization to establish a strong algorithmic connection between the two problems, showing that any solver for one can be adapted to solve the other with comparable precision. Third, we overcome key challenges posed in extending the cost-scaling paradigm to compute these variants of OT and present an algorithm that computes the exact solution up to log(1/ε) bits of precision in n O(d) log(1/ε) time, where n is the support size of the discrete distribution. Finally, we present an n 1+o(1) ε -O(d) time approximation algorithm for the above variants of OT.

Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? Answer: [Yes] . Justification: We provided the novel characterizations of α-SDOPT and λ-SDROT in Section 2, the algorithmic connection between the two problems in Section 3, the highprecision algorithm in Section 4, and the near-linear time approximation algorithm in the appendix.

Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes] Justification: Our algorithms require the existence of an oracle that returns the amount of continuous mass inside any given triangle. This assumption is stated clearly in Theorem 4.4 and in Section 5. Another limitation is the exponential dependence of the running time of our algorithm in Section 4 on the dimension, which we overcame by presenting a near-linear algorithm (with a lower precision) as our final contribution. The exponential dependence on the dimension and the assumption of the existence of the oracle are also present in previous work.

Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof? Answer: [Yes] Justification: All of the lemmas and theorems are stated including the full set of assumptions, and the complete proof of all lemmas is included in the appendix.

Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)? Answer: [Yes] . Justification: The experimental setup is discussed in Appendix B. 5. Open access to data and code Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material? Answer: [Yes] . Justification: As mentioned in Section 4.3, the code is available at https://github.com/pouyansh/Efficient_Partial_and_Robust_SDOT. 6. Experimental setting/details Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results? Answer: [Yes] . Justification: The experimental setup is discussed in Appendix B. 7. Experiment statistical significance Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments? Answer: [NA] . Justification: the paper does not include results that require statistical analysis. 8. Experiments compute resources Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments? Answer: [NA] . Justification: the experimental sections does not include any resource specific results, such as running times. 9. Code of ethics Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines? Answer: [Yes] Justification: the research conducted in the paper does not involve human participants, does not include any datasets, and there are no known potential harmful consequences. 10. Broader impacts Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed? Answer: [NA] . Justification: None of the categories described by the NeurIPS Code of Ethics, namely, safety, security, discrimination, surveillance, deception and harassment, environment, human rights, and bias and fairness is impacted by the research conducted in this paper. 11. Safeguards Question: Does the paper describe safeguar