1. The main ideas have direct predecessors; the additional contribution of MDB is not sufficiently isolated
Independent blocks. Nutini, Laradji, and Schmidt [1, sec. 5.4, pp. 28–29] propose splitting the dependency graph of the variables into color classes: dependent variables get different colors, and the variables of the same color form a block that is updated independently. For UOT, the coordinates πij are coupled through a common row or column. Therefore, applying this principle gives exactly the blocks of Definition 2 and explains the separability in Theorem 2. Reference [1] is cited at lines 109–112, but this direct connection is not discussed. The novelty of the principle of independent updates itself is not established here.
Number of blocks. The admissible blocks are matchings of the bipartite transport graph GT. By König's theorem, the minimum number of such blocks equals Δ(GT), the maximum degree of the graph; see also [5, sec. 1 and Corollary 1b]. On the unit lattice, Δ(GT)≤(2⌊T⌋+1)d, which gives the order O(Td) for T≥1. Thus, the existence claim for the partition in Theorem 3 is a direct consequence of a classical result plus a bound on the number of neighbors, and not a new combinatorial mechanism.
Removing transport edges. Chapel et al. [2, sec. 2.2, formula (3)] write non-entropic UOT as non-negative penalized regression. In sec. 3.1, formula (7), and the following paragraph, they give a quadratic MM that removes, starting from the first iteration, the coordinates with cij>λ(ai+bj). Here a, b, λ are the notation of that paper. Hence, the fixed removal of edges that are certainly unnecessary already has a direct predecessor. The claim of the paper under review that the listed baselines by definition work only with KL (lines 355–359) is incorrect for this MM. Note also that the quadratic penalties of the two papers differ in their weights: a comparison requires adapting that solver to the objective of this paper, and not running a different problem.
The other predecessors are also concrete. In Su, Fang, and Kasai [3, sec. 3.1, Theorem 5 and formulas (8)-(9) of the preprint], strict satisfaction of the corresponding dual inequality guarantees a zero optimal coordinate; this gives safe edge removal. In Schmitzer [4, sec. 3.3, Propositions 10–11], kernel truncation is accompanied by a control of the added error in the primal-dual gap. These are, respectively, safe screening and adaptive entropic sparsification, and not exact copies of MDB. However, they call for a substantive comparison with the claimed contribution, not just a bibliographic mention.
2. The theory does not clarify the central role of T and does not complete the justification of the computational complexity
No distinction between exact and approximate pruning.
The choice of T is mentioned at line 353 and described experimentally in the appendices. However, there is no mathematical characterization of the range in which variables are removed but the optimal problem essentially does not change. Theorem 1 establishes the finiteness of TSUOT, and Theorem 4 the convergence to its own optimum; this is not an accuracy bound with respect to the original UOT.
For the divergence used in the paper, such a range can be established directly. The derivation below belongs to the reviewer and follows from formula (2) and the definition of φp at lines 350–352; it is not a result stated by the authors.
Assume that the problem is discrete, μi,νj>0, all costs are finite and non-negative, ρ>0, and 1<p≤2; there are no additional regularizers and no hard marginal constraints. Denote ri=∑jπij, sj=∑iπij, and the original objective by F. Then
φp′(u)=p−1up−1−1≥−p−11,
=c_{ij}+\rho\varphi_p'(r_i/\mu_i)+\rho\varphi_p'(s_j/\nu_j)
\ge c_{ij}-\frac{2\rho}{p-1}.$$
If $c_{ij}>2\rho/(p-1)$ and $\pi_{ij}>0$, a small decrease of this coordinate is feasible and strictly decreases the objective. Consequently, such a coordinate is zero in every optimal plan. Therefore
$$T\ge T_{\mathrm{safe}}:=\frac{2\rho}{p-1}
\quad\Longrightarrow\quad
F_T^\star=F_\infty^\star.$$
The set of optimal plans is preserved as well. This is a sufficient threshold, not necessarily a minimal one. When $T$ decreases from infinity down to $T_{\mathrm{safe}}$, the graph becomes sparser, but no optimal plan is excluded: the pruning is an exact preprocessing step, and not an approximation of the problem.
For $\rho=1$, Figure 1 with $p=2,T=4$, the LiDAR subproblems with $p=2,T=2$, and the Table 3 configurations with $p=1.5,T=4$ fall exactly in this regime (lines 390–391, 1304–1306, and Table 3). In contrast, for $p=1.1,T=4$ the sufficient threshold is equal to $20$, and the accuracy requires a separate check. The absence of this guarantee does not mean that the error is necessarily positive.
It is especially significant that `experiments/Image_Transfer/params_abl/run.py:159–166` already contains `T_exact = 2/(p-1)` for $p\ne1$, that is, the corresponding formula for $\rho=1$. The notion of an exact threshold is present in the experimental code, but its justification and its role are absent from the scientific explanation of the method. This is a meaningful mismatch: the property determines which problem is actually solved and how the experimental error should be interpreted. From the code one cannot establish why the authors did not include it in the text.
For smaller $T$, no quantitative bounds on the dependence of $F_T^\star-F_\infty^\star$ on the threshold are obtained. Table 3 studies this difference numerically, but the theory does not separate it from the optimization error:
$$F(\hat\pi_T)-F_\infty^\star
=\underbrace{F(\hat\pi_T)-F_T^\star}_{\text{solver error}}
+\underbrace{F_T^\star-F_\infty^\star}_{\text{truncation error}}.$$
Theorem 4 controls the first term but not the second. The short derivation given above shows that even a basic explanation of the exact regime does not require new complex theory. For a paper in which pruning is a central element, the absence of this distinction is a significant omission.
**The passage to the total complexity of GS-MDB is not justified transparently enough.**
Table 1 is stated explicitly for GS-MDB (lines 317–319), and the need for the full gradient is acknowledged at lines 280–284. Nevertheless, the cost of updating a single block does not include the whole selection of this block. The implementation computes the gradient and the scores over all active edges (`src/solvers/GS_MDB.py:36–51,92–100`); with padding, this is a pass over an $N\times D$ array, where $D$ is the maximum number of neighbors of a row. It does not reduce to the update of the at most $N$ coordinates of the selected block. Consequently, the total complexity estimate should be reconciled with the full cost of an iteration and with a model of parallel computation. This objection concerns the analysis of GS-MDB and does not disprove the possible gain of R-MDB.
The hidden constants also require an explicit scaling regime: for $p=2$ and $\mu_i=\nu_j=1/N$, the Hessian of a non-empty matching block is equal to $2\rho NI$, so its Lipschitz constant grows with $N$. A possible compensation through the quadratic growth constant is not traced in Table 1. Finally, the geometric bound on the number of blocks in Theorem 3 refers to the unit integer lattice. It directly explains Image Transfer, but for LiDAR one needs information about the number of edges and the local density; the mere fact that the physical radius is fixed does not bound the number of neighbors independently of the size of the cloud. This is a limitation of the complexity bound, and not of the general applicability of MDB.
### 3. The experiments do not provide an unambiguous verification of the additional contribution of the method
**First: the comparisons do not answer the main question about the solver.** In Image Transfer, the paper tests its own BCD/RowBlock and the pruning/splitting on-off variants (lines 367–377). These are useful internal comparisons, but they do not replace an independent sparse optimizer for the same objective. For $p=2$, a weighted non-negative quadratic problem is natural, so the regression formulation [2, formula (3)] gives a concrete path to such a comparison. One needs to fix the penalty weights, the admissible edges, and the accuracy, so that the gain is not explained by the solution of a different or more coarsely solved problem.
Moreover, in the partition comparison the local step changes at the same time: for $p=2$, MDB minimizes the one-dimensional subproblems exactly, while RowBlock performs a single projected-gradient step (lines 1285–1292; the tuning of the step size is provided in `experiments/Image_Transfer/baselines.py:364–399`). Therefore, Table 4 evaluates the combination of the partition and the local update, and not the pure contribution of the partition. This does not devalue the result, but it limits its interpretation.
**Second: the key accuracy reference in Table 3 is not traceable.** Lines 1228–1230 and the table caption state a comparison with the result at $T=\infty$. However, `experiments/Image_Transfer/params_abl/run.py:121–133` takes the minimum over all found results, without requiring an untruncated or safe reference run. If only $T=1,2,3,4$ are available, then under exact optimization this minimum is equal to $F_4^\star$. In that case, the zero gap at $T=4$ does not testify to the closeness to $F_\infty^\star$.
The provided ZIP contains no source CSVs that would make it possible to establish which reference was used. Therefore, the published error is not disproved, but its origin is not confirmed by the reproduction materials. This is especially important for $p=1.1,T=4$. The code does admit a correct reference; it is enough to confirm the result at $T=\infty$, or at a safe finite threshold, for example $T=20$ for $p=1.1,\rho=1$, and to report its numerical accuracy.
**Third: the applied improvement is mixed with a change of the transport model.** In LiDAR, the final MDB settings use $p=2$, whereas the presented UOT baselines use KL and/or entropic regularization with other penalties (lines 1304–1306). In Office-Home, the parameters and the regularization also differ between the methods (lines 1538–1548). A comparison of tuned systems is acceptable, but a higher applied metric does not establish the advantage of the very algorithm that solves UOT.
### 4. The code does not quite test the computational process that is described in the paper
**LiDAR uses an additional procedure that determines all change predictions in the provided configuration.** In the paper, the classification is built from the barycentric projection and a threshold on the squared displacement (lines 417–422). In the code, $T=2$ and $h=149.3876$ are chosen (`experiments/Change_Detection/Lidar.py:44–58`). For a non-negative plan, if a target point has received positive transport mass, its projection is a convex combination of sources from the ball of radius $T$. Therefore
$$|s_j|\le\|y_j-\widehat y_j\|^2\le T^2=4<h,$$
and such a point is always classified as unchanged. For points with zero incoming mass, the code substitutes, instead of the barycentric projection, a height estimated from the neighbors: by default, the median of the heights of the eight nearest sources in the horizontal plane (`algorithms.py:34–57`, `baricentre_proj.py:60–96`, in the `experiments/Change_Detection/` directory).
Consequently, all change predictions arise in this additional branch, which is not described in the mathematical exposition. The method in fact combines the determination of the transport coverage with a geometric reconstruction of the height. UOT may be important for determining the uncovered points; the bound does not imply that it is useless. But the comparisons with M3C2 and RFF (Table 5) do not separate its contribution from this procedure. A control is needed with a simple geometric determination of the coverage and an identical processing of the uncovered points.
**The partition used differs from the construction presented.** Formula (5) defines cyclic diagonal blocks, whereas `src/utils/block_update.py:10–55` builds sequential maximal matchings. They also satisfy Definition 2, so this does not disprove Theorem 4. However, the number of blocks and the cost of their construction need to be justified for the procedure actually used, and the link between the construction, the complexity bound, and the experiment should not be left implicit.
### Typos and local technical corrections
These corrections are separated from the main conceptual complaints. The local nature of an error does not always mean the absence of consequences for the experiment.
**Office-Home parameter passing.** In `experiments/Domain_Adaptation/mdb_torch_utils.py:51`, the call passes the arguments `rho, T, p`, whereas `mdb_lib/MDB.py:6–15` expects `p, T, rho`. For the settings from lines 1545–1548, this gives $(p,\rho)=(1,1.1)$ instead of $(1.1,1)$: KL instead of the declared power penalty. The call needs to be fixed, and the configuration used for Table 7 needs to be confirmed. From the archive it is impossible to establish whether the error affected the published results.
**The constant in Theorem 4, line 305.** Inside the expression raised to the power $-1/\alpha$, the exponent of $\widetilde\mu$ must be $(1+\alpha)/2$, and not $(1+\alpha)/(2\alpha)$. This follows from the authors' own derivation in formulas (46)–(48), where first $A=L^\star c_\alpha^{1+\alpha}\widetilde\mu^{(1+\alpha)/2}$ is introduced and then $A^{-1/\alpha}$ appears.
**Formula (42), line 1056.** The exponent of the objective error must be $(1+\alpha)/(2\alpha)$ instead of $(1+\alpha)/\alpha$. The correct power is already used further in formulas (48), (50), and (51). This is a correction of the writing, and not a refutation of the claimed convergence rate.
**The constraint in formula (7), line 291.** Under the $\arg\min$, the constraint must refer to the variable $\pi_{ij}$, and not to $\pi_{ij}^\star$.
#### **Overall assessment.**
The paper offers a potentially useful specialization of known ideas, but its additional scientific and computational value is not yet sufficiently established. The uncertainty of the role of $T$, the incomplete passage to the total complexity, and the insufficiently controlled experiments touch the central claims of the paper. The discrepancies with the code reinforce these questions but do not replace them. My recommendation is clear rejection.
#### References for the remarks
[1] Nutini, J., Laradji, I., Schmidt, M. **Let's Make Block Coordinate Descent Converge Faster: Faster Greedy Rules, Message-Passing, Active-Set Complexity, and Superlinear Convergence.** JMLR 23(131), 1–74, 2022. Used: sec. 5.4, pp. 28–29.
[2] Chapel, L., Flamary, R., Wu, H., Févotte, C., Gasso, G. **Unbalanced Optimal Transport through Non-negative Penalized Linear Regression.** NeurIPS 34, 23270–23282, 2021. Used: sec. 2.2, formula (3), and sec. 3.1, formula (7) and the following paragraph.
[3] Su, X., Fang, Z., Kasai, H. **Safe Screening for Unbalanced Optimal Transport.** arXiv:2307.00247v1, 2023. The numbers of Theorem 5 and of formulas (8)–(9) refer to sec. 3.1 of this particular version of the preprint.
[4] Schmitzer, B. **Stabilized Sparse Scaling Algorithms for Entropy Regularized Transport Problems.** SIAM Journal on Scientific Computing 41(3), A1443-A1481, 2019. Used: sec. 3.3, Propositions 10-11.
[5] Schrijver, A. **Bipartite Edge Coloring in $O(\Delta m)$ Time.** SIAM Journal on Computing 28(3), 841-846, 1998. Konig's theorem is stated in §1; the constructive result about a $\Delta(G)$-coloring is Corollary 1b.