Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: In this paper, the authors consider the problem of optimal partial transport. In this problem some fraction of a mass distribution over a set of supply nodes, needs to be transported and distributed to a subset of the demand nodes. The amount of mass supplied or demanded by each node as well as the per unit transportation cost between a pair of nodes are given. The goal is to find the optimal way to transport a fraction $\alpha$ of the supply mass to demand nodes. 
The authors are interested to find the so called "optimal transport profile" $\omega(\alpha)$ which is the optimal transport as a function of this parameter $\alpha$. The proposed algorithm is a modification of an algorithm by Lahn at' al (LMR algorithm) also using ideas from the Hungarian algorithm like augmenting paths. The modification is needed so that the optimal transport cost if found as a function of $\alpha$ rather than for a fixed value of it. The running time of the algorithm is output sensitive and proportional to the number of linear parts of the output $\omega$, which is shown to be a piecewise-linear function. In particular, the running time is $O(n^2\cdot K)$, where $n$ is the total number of nodes and $K$ the number of linear parts of $\omega$. They also provide a $\delta$-approximation algorithm that outputs an approximate profile $\bar{\omega}$ that has O(1/\delta) linear parts and can be computed in $O(n^2/\delta + n\delta^2)$ time. 
The applications mentioned in the paper for these algorithms are Outlier detection and PU learning. The reason why the optimal transport algorithm could be used for the former, is that the existence of outliers would result in a "sudden jump" in the OT-profile $\omega$ since for some sufficiently large value of $\alpha$, some mass has to also be transported through the "outliers". 
strength_and_weaknesses: Strengths:

-This paper slightly generalizes and appropriately adapts an algorithm for partial optimal transport. This is further used to improve performance in a couple of real-world applications. 

Weaknesses:
- The algorithms and techniques seem to be similar and heavily dependent on prior work.
- Regarding prior work, even though the most relevant work is mentioned, the paper is missing a wider overview of prior work on this topic.

Minor comments:
- In lines 1 and 2 of the Introduction I think $A$ and $B$ should be swapped. $A$ should be the support of $\mu$ and $B$ the support of $\nu$
- Page 2, 4th paragraph,1st line: "$\alpha$-approximate"-> "$\delta$-approximate"   
- Last paragraph of section 3, line 1: the proof of Lemma 1.1 is not presented there. A reference to the Appendix is missing. 
clarity,_quality,_novelty_and_reproducibility: Apart from some notation issues, the writing is quite clear. As I mentioned, I don't find the work very novel, at least in the theoretical part. 
summary_of_the_review: Although it's an interesting adaptation of prior work, I believe the algorithms and techniques are not novel enough to recommend acceptance.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: In the optimal transport problem, we are given two mass distributions $\mu$ and $\nu$ and the goal is to transport a mass of $\alpha$ from $\nu$ to $\mu$ using a minimal cost with respect to a certain distance such as $\ell_1$. In this paper, the authors look at the problem of computing an optimal OT profile for any particular fixing of $\alpha$ when the underlying distributions are discrete.

The authors first show that the OT profile is a piecewise linear function with a non-decreasing convex function. They first give an exact algorithm of time complexity $n^2K$ where $n$ is the support size of the distributions and $K$ is the number of pieces of the OT profile. Then for any $\delta>0$ they give a $1/\delta$-factor approximate algorithm for the OT profile using $n^2/\delta+n/\delta^2$ time. For designing this approximation algorithm, they use an existing algorithm by Lahn et al.

Then they apply the OT-profile computation to the detection of outliers under a certain reasonable assumption of the outliers. They conduct experiments on the MNIST dataset with outliers and show evidence that their algorithms better the existing algorithm in achieving a better accuracy of detecting outliers.
strength_and_weaknesses: Strength: the OT problem is non-trivial and has a rich history. The authors give theoretical guarantees of their algorithm before giving experimental evidence of the superiority of their algorithm in detecting outliers.

Weakness: A high-level idea of their theoretical algorithm would have improved the presentation. I think the n^2K bound may be expensive in practice due to a large value of K. The approximation algorithm looks like a straightforward application of Lahn et al.
clarity,_quality,_novelty_and_reproducibility: The paper is well-written and clear. The results as a whole look novel and non-trivial.

Minor comments:
- does your algorithm give a $(1\pm\epsilon)$-factor approximation scheme?
- please define what is $n$ in the abstract as well.

summary_of_the_review: Due to novelty of the algorithm design and the experimental evidence, I tend to accept the paper.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper studies the optimal transport (OT) profile. That is, the dependence of the OT cost on the amount of mass being transported from the source measure. The main result gives a characterization of the OT profile as a piecewise-linear function. This characterization gives rise to an approximation algorithm that allows to numerically approximate the entire OT profile. The paper also explores a potential application for outlier detection.
strength_and_weaknesses: The proof of the main result goes by a standard dual characterization of OT solutions. The authors then demonstrate a procedure that takes an OT solution that transports total mass $\alpha_1$ from the source measure and produces an OT solution of total mass $\alpha_2$ with $\alpha_1 < \alpha_2$. Moreover, it is shown that for any $\alpha \in (\alpha_1, \alpha_2)$ the OT profile linearly interpolates between the values at $\alpha_1$  and $\alpha_2$. Under a slightly restrictive (but probably necessary) assumption of having all costs rational, the above two properties give a complete description of the OT profile. Relaxing the duality condition affords an approximation algorithm for the OT profile.

Strength:
- The paper studies a relevant problem.
- The introduced algorithms are practical.

Weakness:
- The method is not very novel, even if the results are.

Some comments:
- I would be happy to see a formal definition of combinatorial complexity instead of a footnote. After all, it is a central concept for the algorithms.
- The fact that the involved probabilities need to be rational should be emphasized, maybe in the Theorem's statement.
- In the preliminaries section: "Consider any transport plan $\sigma$ transporting mass from $\nu$ to $\mu$." I think the paper adopts the convention that mass is transported from $\mu$ to $\nu$.
- Section 3, first step: I don't think $\ell_t$ was properly defined.
clarity,_quality,_novelty_and_reproducibility: Full disclosure: I previously reviewed this paper for NeurIPS, where, for various reasons, I was hesitant to recommend acceptance. I feel like the current version is much improved, more streamlined, and easier to follow. I appreciate the authors' efforts, and this is reflected in my recommendation.
summary_of_the_review: I feel that the results are new and interesting. Lately, the Machine Learning community has shown an increasing interest in optimal transport methods, and it is likely that some parts of the community will find the paper interesting and relevant. This is especially true given the more practical nature of some of the results. I am therefore inclined to recommend acceptance.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses:  
The paper introduces a new analysis of the optimal transport (OT) profile. 
They look at the dependence of the OT cost on the amount of mass being transported from the source measure to the target one.
One of their key results is to show that the OT profile is a piecewise-linear function. Based on this characterization,
they are able to derive an efficient approximation algorithm for computing the entire OT profile. 
This algorithm is numerically analyzed and applied for outlier detection.

All reviewers agree that the paper propose a novel and interesting contribution and as such can be accepted for
publication 
 			
justification_for_why_not_higher_score:  				
 Experiments are carried out on  bit toyish problems (like MNIST or UCI datasets). It would have strongly
supported the paper to have experiments on real-world outlier detection data.     
 				
justification_for_why_not_lower_score: The paper proposes a new algorithm for computing all the partial optimal transport. This is a novel and interesting contribution
Decision: Accept: poster