Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: Authors in this paper flattened the matrix-form unbalanced OT and reformulated it as a linear regression regularized by either the KL divergence or $\ell_2$ between the transport plan and two marginals. Then the problem converts to an MM problem and the authors derived the optimization steps for solving them, especially the one with $\ell_2$ in which case the authors proposed an algorithm to regress the optimal combinations of the transport plan and the regularization strength. Numerical results show that the new formulation leads to faster computation.
main_review: +
The proposed method is novel and all the claims in the paper seem well supported by theoretical and empirical results.

-
Reformulating $\ell_2$-regularized UOT to a Lasso regression inevitably promotes sparsity. Adding the transportation cost $c^Tt$, the resulting transporting map $t^k$ concentrates on the nearest samples of the two domains like what $Figure\ 2$ shows, especially when $\lambda$ is small. When $\lambda_1 = \lambda_2$, it becomes more apparent that $Algorithm\ 1$ is selecting a subset of the samples and finding a balanced transport. Although it still aligns with the original formulation of unbalanced OT (Benamou, 2003), but my understanding of the practicality of unbalanced OT is that it still transports all the mass but allows the mass to grow or shrink during transport. Now, the proposed method seems more like to transport a subset of mass controlled by $\lambda$. 

I am also reluctant to accept the wording that $\lambda \rightarrow \infty$ recovers a balanced OT because balanced OT requires the mass on both sides to equal, i.e. $ \mathbb{1}a =  \mathbb{1}b$ and such a T does not exist when $\lambda \rightarrow \infty$ and $ \mathbb{1}a \neq  \mathbb{1}b$. In this sense, the experiment in Figure 2 feels cheesy to me because the two marginals are balanced, and $Algorithm\ 1$ feels more like gradually finding a balanced OT by including more samples and excluding fewer outliers from the two domains. 

The motivation behind computing the "regularization path" is not clear in the beginning of the paper. Only when I saw the application to unbalanced DA did I get to know its usage but I'm still not sure what motivated the authors to get such as path. It seems the paper has a very similar motivation to those of Mukherjee et al. (line 416) and Balaji et al.

Balaji, Yogesh and Chellappa, Rama and Feizi, Soheil, Robust Optimal Transport with Applications in Generative Modeling and Domain Adaptation, Advances in Neural Information Processing Systems, 2020

limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The authors propose to reformulate the unbalanced Optimal Transport (e.g., Kullback-Leibler and $\ell_2$-regularization) and non-negative penalized linear regression with $\ell_1$-regularization. For $\ell_2$-regularized UOT, the authors derive the regularization path.

main_review: It is interesting to reformulate the UOT as a non-negative penalized linear regression with $\ell_1$ regularization and leverage the tools in Lasso problem to derive the regularization path.

The majorization-minimization (MM) algorithmic approach for UOT seems elegant with the multiplicative update (naturally handing the non-negative constraint). However, there is no theoretical analysis to compare this MM algorithmic approach for the proposed reformulation with approaches in the literature (for KL/$\ell_2^2$ regularized UOT). Although the authors did the empirical comparison in Figure 3 (and recall that the complexity of L-BFGS is about $O(n^2)$), it seems unclear why the proposed MM algorithmic approach gives more advantages. It is better in case the authors elaborate with more details.

The regularization path for $\ell_2$-penalized UOT is interesting. However, it seems that the authors may need to discuss Algorithm 1 in more detail. For examples,
+ Can the stoping condition in the while-loop be obtained?
+ How to update the set A? (How to compute the set $A_{k+1}$?

For the right plot in Figure 1 (left), it may mislead the readers for the curve between $\lambda_7$ and $\infty$? (monotonically increasing?)
+ Do the authors compute the standard OT at $\infty$ or use Algorithm 1?

In line 290-292, the authors discuss the contribution with the SInkhorn-like multiplicative algorithm for UOT? However, it is unclear why the Sinkhorn-like algorithm is important and favoring? What is its advantage to compare with the L-BFGS (e.g., in Blondel et al.)

Overall, I think the submission is interesting. However, there are some points (as mentioned above) that may be needed further elaboration. Besides the regularization path results (for $\ell_2$ regularization), it is still unclear yet about the advantage of the MM algorithmic approach for the proposed reformulation with approaches in the literature.

---------After the rebuttal-----------

I thank the authors for the response. Overall, I think the proposed reformulated UOT to connect with the LASSO problem is interesting. I hope that the authors address those raised concerns, especially those about the MM algorithm in the updated version. So, I keep learning on the positive side. 
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper proposes a new method for Unbalanced Optimal Transport (UOT) without a regularization term. The solution consists of two steps; (i) formulate the UOT as a non-negative penalized linear regression problem (ii) solve it using the Majorization-Minimization (MM) algorithm. The authors derive specific algorithms for several penalty functions. Furthermore, a regularization path tracking method based on the relationship between the proposed formulation and lasso is proposed. The authors validate the effectiveness of the proposed method by numerical experiments using synthetic datasets and the MNIST dataset.
main_review: ### Strengths

* The idea of formulating UOT as a non-negative penalized linear regression problem and applying the MM algorithm is very interesting.

* Also, there is originality in the regularized path tracking algorithm based on the above formulation.

* This paper is well-written; the problems, the backgrounds, and the contributions are clearly stated with appropriate citations. 

### Weaknesses

* The analysis of the time complexity is insufficient both theoretically and experimentally. The theoretical analysis of the time complexity for each iteration and convergence is not sufficiently done for any of the methods, and the superiority of the proposed method cannot be judged. As for the experiments, the scalability of the proposed method cannot be judged from the experimental results because the comparison with the existing methods is made only when \lambda is changed, and there is no comparison when n or m is changed. Although the authors do not claim that the computation time is an advantage of the proposed method, these analyses are necessary to understand the characteristics of the proposed method. 

* In the introduction, the authors state that one of the advantages of the proposed method is fast computation by GPUs, but this claim has not been verified theoretically or experimentally.

* In the introduction, the ease of implementation is mentioned as an advantage of the proposed method, but since the L-BFGS method can also be easily implemented by using scipy, there seems to be no significant difference.

### Other comments

* Regularized path in OT is interesting, but it is a bit unclear how it can be useful. I would like to know if there are any specific use cases.

* In the experiments, the authors compare their method with the BFGS method in Blondel et al. (2018).  Blondel et al. (2018) propose two methods in the paper, one for solving the dual and one for solving the semi-dual.  Which method is used in the experiment? In addition, Blondel et al. (2018) also describe an optimization method using alternating minimization. Because this method resembles the proposed method, shouldn't it be compared with this method as well?

* Section 5 contains various speed-up proposals for the proposed algorithm.  A thorough theoretical and experimental evaluation of these proposals will make this paper more interesting.
limitations_and_societal_impact: The limitation of this paper is that it has little advantage over existing methods in terms of computation time, as the authors also state in the checklist.  The societal impacts are fully discussed at the end of Section 5.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: In this work, the authors propose to phrase the Unbalanced Optimal Transport problem under general Bregman divergence penalty as a non-negative penalized linear regression problem. They exploit an existing algorithm in Non-negative Matrix Factorization problem (NMF), namely Majorization-Minimization, in order to solve the obtained problem. In the case of KL-penalized UOT, the obtained algorithm is a variation of the Sinkhorn algorithm. However, this algorithm solves a different algorithm than Sinkhorn, namely KL-penalized UOT as opposed to OT with KL penalized transport plan.  For the l2-penalized UOT, the authors design an algorithm, based on LARS, that solves the problem for all values of lambda, from 0 to infinity.

The running time of different variants of their proposed algorithm are compared on a toy problem versus the current state-of-the-art method that uses BFGS. Overall, for l2-penalized UOT, the proposed method is significantly faster than BFGS. For KL-penalized UOT, it depends on the value of lambda.

main_review: pros:
- The connection made between UOT and non-negative linear regression allows for the use of well-studied efficient algorithms.
For KL-penalized UOT, the algorithm solves the problem without needing to regularize the transport plan, as opposed to using Sinkhorn divergence for UOT as done in [1].
- For l2-regularized UOT, the proposed algorithm can be solved once for all values of the regularization parameter, and is shown to be faster than the state-of-the-art method that uses BFGS.

cons:
- The improved performance of the algorithm is shown only in the case of l2-penalized UOT, whose practical interest is not clear compared to KL-penalized UOT, which is more commonly seen in the literature.
- In the case of KL-penalized UOT, I expected a deeper analysis of the connection with the Sinkhorn algorithm and the Sinkhorn divergence based UOT of [1], e.g., how similar do they become for asymptotic values of lambda and epsilon (epsilon being the reg. parameter for the entropy of the transport plan).

Typos:

l.319 balanced OT 

[1] Sinkhorn Divergences for Unbalanced Optimal Transport, Séjourné et al.

limitations_and_societal_impact: The authors adequately addressed the limitations and potential negative societal impact.
review_title: null

Meta-review: The authors consider the unbalanced optimal transport (OT) problem and its semi-relaxed variants. They then consider various optimization approaches that come from the mirror descent family by choosing an appropriate Bregman divergence. In particular, they consider the entropic and the ell2 mirror maps. 

In the ell2 case, the authors connect the optimization problem to the LARS optimization, which has been quite successful in the sparse recovery literature. They propose a regularization path or homotopy algorithm for the unbalanced OT plans and demonstrate its performance numerically.

The developments in the paper mostly rely on recognizing the LASSO structure in the unbalanced OT problem and then applying existing techniques to it. In the worst case, this approach has exponential complexity but the authors argue that the [Mairal and Yu 2012] approach can be applied to obtain eps-approximate primal dual gap as an afterthought. Unfortunately, there is also no follow up to back up how this epsilon guarantee to the quality of the OT map. 




Decision: Accept (Poster)