Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper studies optimal transport with prescribed sparsity. Specifically, based on the well known quadratic regularized optimal transport, the paper further constrains the cardinality of non-zeros entries of each column of the optimal plan. The problem of optimal transport with constrained sparsity is well motivated from expert assignment problem, and based on weak duality of the proposed optimization problem, efficient algorithm is proposed, with experiments provided.
strength_and_weaknesses: The paper has the following strengths:
1. The paper answers, in some sense, the question of how to make optimal transport plan more sparse, especially with proposition 3 where the paper introduces the k-support norm, which is of general interest and is a more principled way to enforce sparsity.
2. The most notable result in the reviewer's opinion, is that it reveals the relations between the k-support norm regularization, and the sparsity of the OT plan. Though the strong duality does not hold, the sparsity constraint is still nicely carried from the original primal problem into the dual solution.
3. The paper provides pretty strong application motivation of the sparsity-constrained optimal transport, e.g. the sparse mixture of experts.

Some weaknesses:
1. Though the paper claim it proposed a 'constrained' problem, it does not solve the primal constrained problem exactly. In fact, the paper finds feasible solution(s) to the original problem through minimax principle, but no approximate optimality is provided. It would be more natural if some tightness result between primal and dual formulations can be provided, as for the current paper the 'constraint' point of view is more of a heuristic formulation rather than a problem solved in the paper. (Maybe considering the tightness between $\ell_2$ and $\Psi$ can lead to it.)
2. The paper claimed that the proposed formulation has increased smoothness when the constraint is looser, but the reviewer didn't find a concrete characterization of the increase of smoothness except for a figure illustrating this phenomenon. This point would be more valid and clear if some concrete measurement of smoothness can be added, and even a formal proof of such increase of smoothness.

Minor comment: the paper claimed in [section 3][computation] that the entropic formulation is not smooth, which is unclear to the reviewer, since it is well known that the dual of entropic OT is sum of exponentiation of dual potentials which is very smooth, and the whole quantity is even smooth in marginals, see e.g. https://arxiv.org/pdf/2207.08683.pdf , https://arxiv.org/pdf/2207.07427.pdf .
clarity,_quality,_novelty_and_reproducibility: Clarity: The paper is overall well-written, with clear structure and plenty of discussion. Some unclear points are listed in weaknesses.
Quality: The paper is of decent quality, where the writing is consistent and the presentation is not hard to follow.
Novelty: The paper contains some novel combination of interesting ideas, and provides notable results that offers new insight to the sparse OT problem.
Reproducibility: the experiments can be reproduced.
summary_of_the_review: The paper is overall well written and organized. Notable results are proven, with novel regularization that leads to a desired level of sparsity. Some weaknesses are listed for possible improvement. In summary The paper is a solid contribution to the sparse optimal transport problem.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: In this paper, the authors propose to add a non-convex sparsity constraint to the $l^2$ regularized discrete OT problem. In such a way, they can control the sparsity of the OT plan. Though the sparsity constraint makes the original problem nonconvex, it is still tractable through the dual and semi-dual problem. With the k-sparse projection, the proposed problem can be solved by L-BFGS or ADAM. Furthermore, to obtain the approximate OT plan, they turn to the convex bi-conjugate problem. Experiments show that the proposed method successfully induce a controlled sparse solution.
strength_and_weaknesses: Strength
- It is novel to add the k-sparsity constraint to the regularized OT problem and use the k-sparse projection to make the solution tractable.
- To reconstruct the OT plan, the use of bi-conjugate tech is interesting.
- The extensive experiments help show the performance of the proposed method.

Weakness
- Is there any guarantee for the sparsity of the reconstructed OT plan through bi-conjugate?
- Since the authors are trying to solve an OT problem, it is necessary to investigate the influence of $\gamma$ in equation (8). I am extremely curious about the convergence/performance with a small $\gamma$. Ablation study is needed here.
- Besides sparsity, the accuracy of the propose method should also be reported. With small scale problems like $784\times 784$, the authors can use linear programming to obtain the groundtruth and make the comparison.
- It is important to report the scale of the problems in the experiments. For small scale problems, linear programming may be more efficient.
- Lack of important reference paper "An et al. Efficient Optimal Transport Algorithm by Accelerated Gradient descent, AAAI 2022". The authors may also try the accelerated gradient decent method to see if it helps improve the performance.
clarity,_quality,_novelty_and_reproducibility: Generally, the paper is clear and easy to follow. Different sections are well organized and help support each other. The proposed method is novel and there is no reproducibility problem. 
summary_of_the_review: The paper propose a novel method to solve the discrete OT problem with controlled sparsity. Experiments show that the proposed method work well. To make the results more convincible
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper proposes an optimization algorithm for sparse optimal transport. The optimal transport is a linear program with additional regularization on the columns on the transportation plan matrix. In this work, the authors add further constraints to ensure each column has no more than k non-zeroes. They then propose using gradient based optimizers to directly solve the non-convex problem. 
strength_and_weaknesses: Strengths:

-- Largely well written and the relevant works are well-cited. 
-- The duality connection is well-explained, albeit is standard for solving such problems. Similarly, the section explaining the development of the dual specific to the sparsity constrained problem is also well-explained.

Weaknesses:

-- I have concerns for novelty. Given enormous progress already made with iterative hard thresholding and its variants, I am not sure if they optimal transport setup adds enough novelty above that. I suggest the authors look at works of Anastasios Kyrillidis (one of whose papers the authors have cited) to look at iterative hard thresholding methods that are directly employed on the primal. Given those works, I am unfortunately not excited about this paper.

-- Similarly the section on double conjugate mentioning what problem is solved when solving the dual and the relationship with k-support norms is known. 

-- There are limited empirical evaluations, especially considering the relevance to this conference. 


clarity,_quality,_novelty_and_reproducibility: Very clear, writing is high quality, no concerns about reproducibility but concerns in novelty as explained in the weaknesses section.
summary_of_the_review: After the rebuttal and reading other reviews, I am updating my score. I seem to have misunderstood the paper's contributions earlier.

Solving non-convex problems using convex duals is not new, the paper explains the setup for sparse constrained optimization in context of optimal transport. I have concerns for novelty, limited empirical evaluation and the relevance to the iclr community.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: Optimal transport (OT) distances (a.k.a. Wasserstein's distances) are a powerful computational tool to compare probability distributions and they play an increasingly preponderant role in machine learning, statistics, and computer vision. Since computing OT distances involves a linear program, which takes super-cubic time in the data size, its large-scale applications have mainly been hampered by its high computational cost. A classical and popular approach to tackling this problem consists in adding an entropic regularization that can be solved using Sinkhorn iterations. Comparing to the (unregularized) OT that produces a sparse transport plan, the entropic penalty blurs the OT solution, namely, it entails a dense transport plan being undesirable for interpretability. Towards realizing a sparse solution, Blondel et al. 2018 (ICML) proposed to substitute the entropy penalty with the squared-$2$norm.

In this spirit of obtaining a sparse OT, this paper proposes a novel approach by working on a nonconvex penalty with control of the sparsity. In other words, the authors define the $k$-cardinality constraint penalty that controls the cardinality of non-zeros elements in each column of the transport plan. The idea is quite "nice" and seems interesting for many applications involving OT metrics. 
strength_and_weaknesses: ### Strength ###
- To the best of my knowledge, working with nonconvex regularization on OT problems is not well-known. This paper investigates the $k$-cardinality constraint, that forces each column to get at most $k$ non-zeros elements, avoids the spreading of masses in the OT solution. I really appreciate the finite analytic results about the relations between the primal, dual, and semi-dual forms of the objective functions.
- The approach is strongly supported by theoretical findings. 
- As the OT community is a big fan of acronyms, so I can suggest the following acronym for this paper **Top-$k$-OT**.
- Extensive numerical experiments are conducted on sparse mixture experts with good performances and on supply-demand transportation spherical data.

I have a single question: what is the computational complexity of **Top-$k$ OT**?  One can complete Table 2 by adding time for the proposed algorithm. 
clarity,_quality,_novelty_and_reproducibility: - The paper is well-written and easy to follow. All the proofs are complete. 
- Code is not available, but I think reproducibility could be guaranteed since the authors detail the setting of each experiment. 

summary_of_the_review: Overall, I like the approach and I think it deserves to be published at ICLR conference since it gives advances to the OT community.
review_title: null

final_score: rating: 10: strong accept, should be highlighted at the conference
review_content: summary_of_the_paper: Entropy-regularized optimal transport is very popular today, but it leads to fully-dense transport plans. To address this problem, this work proposes a new approach for OT with explicit cardinality constraints on the transportation plan. Despite the non-convexity of the cardinality constraints, the work shows that the corresponding dual or semi-dual problems are tractable and can be solved with first-order gradient methods. This method can be treated as a middle ground between unregularized OT (case k=1) and quadratically-regularized OT( k is big enough). The smoothness of the objectives increases as k increases, giving rise to a trade-off between convergence speed and sparsity of the optimal plan.

The contributions are
1. presents a dual and semi-dual framework for OT with general nonconvex regularization. The framework is applied to obtain a tractable lower bound to solve an OT formulation with cardinality constraints on the transportation plan. 
2. shows this framework is formally equivalent to using squared k-support norm regularization in the primal, this model is the middle point between the unregularized OT and the quadratically-regularized OT.
3. The (semi) dual objectives were shown to be increasingly smooth as k increases, enabling the use of gradient-based algorithms such as LBFGS or ADAM.
4. the framework is demonstrated on a variety of tasks, which shows a direct control of sparsity improves the accuracy, lead to more interpretable transportation plans and the integer-valued hyperparameter k may be easier to tune.

strength_and_weaknesses: The work has many strengths:
1. The problem to tackle is fundamental: control the sparsity of optimal transportation plans, which is crucial for deep learning.
2. The idea of adding direct control to the cardinality of the images of transportation plan is novel and effective.
3. The high level perspective, which unifies the proposed method and the existing ones, is inspiring and promising.
4. The work has solid theoretic foundation, all the main claims are formulated as theorems and proved rigorously.
5. The experimental results are thorough and convincing.

The weakness of the work is that it requires advanced background knowledge,  currently, detailed discussions in the supplementary materials are very helpful, it will be more helpful to give more explanations to the key concepts and the main theorems.


clarity,_quality,_novelty_and_reproducibility: The idea of adding direct control to the sparsity by adding cardinality constraints to the columns of transportation plans is very novel and effective, this greatly improves the sparsity and the accuracy of optimal transportation plans.

The work is very carefully prepared, very well written. All the concepts, terminologies, theoretic formulations and main claims are carefully formulated, rigorously proved, and vividly illustrated and thoroughly discussed. Although the work involves advanced background knowledge in optimal transportation theory, convex analysis and optimization, the manuscript is relatively easy to follow and pleasant to study.

The manuscript has very good quality. The mathematical models are elegant, the theoretical methods are powerful, the proofs are rigorous and the experimental results are convincing.

The work should be easy to reproduce, all the algorithmic details are explained clearly.
summary_of_the_review: This work presents a dual and semi-dual framework for OT with general nonconvex regularization. The framework is applied to obtain a tractable lower bound to solve an OT formulation with cardinality constraints on the transportation plan. The work also shows this framework is formally equivalent to using squared k-support norm regularization in the primal, this model is the middle point between the unregularized OT and the quadratically-regularized OT. The (semi) dual objectives were shown to be increasingly smooth as k increases, enabling the use of gradient-based algorithms such as LBFGS or ADAM. The framework is demonstrated on a variety of tasks, which shows a direct control of sparsity improves the accuracy, lead to more interpretable transportation plans and the integer-valued hyperparameter k may be easier to tune.

The sparsity problem is fundamental in deep learning, this work gives a nice solution to the problem. The work has solid theoretic foundation, and high practical value. The mathematical formulation and proofs are rigorous and elegant. The description and analysis are clear and easy to follow. The experimental results are encouraging. Especially, this work unifies the existing methods, and present a coherent theoretic framework, this global view is very valuable.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper proposes a sparsity constraint on the optimal transport plan and resort to weak duality (and semi duals) to find an approximation of the original primal problem. The bi-conjugate maps are used to reconstruct the optimal and  experimentation shows the  benefits of the methods in recovery of sparse transport plans. 

The main weakness of the work is the lack of approximation guarantees for the algorithm proposed in the paper , since it is a non-convex optimization. This does not however hinder the value of the work but leaves room for future investigation. 
justification_for_why_not_higher_score:  The techniques proposed in the paper  should be highlighted especially in circumventing iterative thresholding and resorting to dual and semi dual instead to yield an efficient algorithm to impose sparsity on OT plan. The paper does not meet the bar of an oral since it is missing a complete theoretical study of the tightness of the feasible point returned by the algorithm when solving the dual or semi dual due to non convexity.
justification_for_why_not_lower_score: All reviewers agreed on the novelty and the quality of the work.
Decision: Accept: notable-top-25%