acceptodds
Withdrawn from ICLR 2027

PRUNE AND SPLIT: A SCALABLE APPROACH TO UNBALANCED OPTIMAL TRANSPORT

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

In this paper, we analyze the T-Sparse Unbalanced Optimal Transport (TSUOT) problem, a variant of the standard Unbalanced Optimal Transport (UOT) problem that enables customizable sparsity, i.e., Pruning of long-range transport arcs, via a tunable parameter . After showing that the TSUOT is well defined for most of the Csiszár divergences, we propose the Main Diagonal Block method, an ad hoc Block Coordinate Descent algorithm for UOT problems. At the core of the method is a structure-aware coordinate partition that, by Splitting the transport variables into suitably chosen blocks, allows for efficient parallel optimization. The interaction between Pruning and Splitting yields dual advantages. On the one hand, Pruning bounds the number of relevant blocks; on the other hand, Splitting decreases the local \Holder constant. These effects combined improve the overall complexity of the method. Experiments on heterogeneous real-world benchmarks show that the proposed approach achieves comparable numerical accuracy to standard UOT baselines while substantially reducing wall-clock computation time, with speedups of up to two orders of magnitude in the tested regimes. These results position the proposed framework as a competitive approach to large-scale UOT computation.

Primary area:
optimization
Keywords:
Unbalanced Optimal Transport, Block Coordinate Descent Algorithm, Large-scale Convex Optimization

Reviews

Among:
Shape:
1234this paper, Bottom 2%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.33 over 3 reviews, above 2% of the others.
Reviewer_3JznOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper addresses the high computational cost of large-scale unbalanced optimal transport (UOT). It proposes a “prune-and-split” framework: first, high-cost transport connections are discarded using a fixed threshold to reduce the number of variables; then, the remaining variables are partitioned into non-conflicting blocks and updated by a block-coordinate method called MDB. The theoretical part discusses the solvability of the pruned problem and analyzes the convergence and complexity benefits of the block partitioning. Experiments on image transfer, LiDAR change detection, and domain adaptation show speedups and competitive performance. Overall, the main contribution is to combine fixed-threshold pruning with structured block optimization, providing a sparser and more scalable approach for large-scale UOT.

Critical strengths
  1. The paper proposes a fixed-threshold pruning strategy for unbalanced optimal transport (UOT), referred to as Pruning, together with a corresponding block partitioning strategy, referred to as Splitting.

  2. On the theoretical side, the paper provides guarantees that the pruned problem (TSUOT) admits a finite optimum under certain conditions, and shows that on a special class of data sets the number of blocks is controlled by the truncation threshold TT. In addition, the paper establishes convergence guarantees and complexity analyses for the two block-selection rules, R-MDB and GS-MDB.

  3. Numerically, the paper demonstrates that both Pruning and Splitting improve computational speed. Overall, MDB shows competitive advantages in both small-scale and large-scale comparisons, and the quality of the solutions it produces also performs well when used as a training signal for small-scale learning problems.

Critical weaknesses
  1. Theorem 1 only guarantees that TSUOT has a finite optimum in certain cases. In such cases, how far is its optimal solution from that of the original UOT problem? What parameters determine this gap, and can the gap be controlled? Moreover, since the gap between TSUOT and the original UOT remains unknown, the complexity of solving TSUOT cannot be directly translated into a complexity guarantee for the original UOT problem. It would be helpful to clarify this limitation explicitly.

  2. The truncation threshold TT is selected by hyperparameter tuning. Can the authors provide either theoretical guidance or empirical rules for choosing TT in general settings?

  3. Theorem 2 shows that the Splitting strategy improves the convergence bound by reducing the Hölder constant on each block. Is the speedup observed in Figure 1(a) due to a lower per-iteration cost, fewer iterations, or both? A more explicit decomposition would strengthen the empirical analysis.

  4. Theorem 3 guarantees a bound on the number of blocks for a special class of grids. For more general graphs or supports, could the number of blocks become excessively large, thereby weakening the effectiveness of MDB?

Questions for authors

What are the differences between this work and Schmitzer (2019) and Su et al. (2024, 2025) in terms of experimental performance? The paper discusses conceptual differences in the related-work section, but it does not provide direct numerical comparisons with Su et al. (2024, 2025).

Reviewer_r8ogOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

The authors propose MDB, a block-coordinate method for non-entropic Unbalanced Optimal Transport (UOT) on finite sets. First, transport along edges with cost above TT is forbidden, which defines the truncated problem TSUOT. The remaining variables are then split into blocks that share no row or column, so that coordinates can be updated independently. The paper studies the random variant R-MDB and the greedy variant GS-MDB, derives convergence guarantees, and presents experiments on images, LiDAR, and Office-Home.

Critical strengths

The separability of the matching blocks does follow from the structure of the marginal penalties and allows parallel one-dimensional updates without entropic regularization of the plan (Theorem 2). Theorem 4 gives quantitative convergence guarantees under a quadratic growth condition. In Image Transfer, the authors report a large speed-up over their own implementations of BCD and RowBlock under the same problem parameters (Figure 1, Table 4). This suggests that the chosen method can be practically useful.

Critical weaknesses

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\pi_{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 GTG_T. By König's theorem, the minimum number of such blocks equals Δ(GT)\Delta(G_T), the maximum degree of the graph; see also [5, sec. 1 and Corollary 1b]. On the unit lattice, Δ(GT)≤(2⌊T⌋+1)d\Delta(G_T)\le(2\lfloor T\rfloor+1)^d, which gives the order O(Td)O(T^d) for T≥1T\ge1. 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)c_{ij}>\lambda(a_i+b_j). Here aa, bb, λ\lambda 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 TT and does not complete the justification of the computational complexity

No distinction between exact and approximate pruning. The choice of TT 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\varphi_p at lines 350–352; it is not a result stated by the authors.

Assume that the problem is discrete, μi,νj>0\mu_i,\nu_j>0, all costs are finite and non-negative, ρ>0\rho>0, and 1<p≤21<p\le2; there are no additional regularizers and no hard marginal constraints. Denote ri=∑jπijr_i=\sum_j\pi_{ij}, sj=∑iπijs_j=\sum_i\pi_{ij}, and the original objective by FF. Then

φp′(u)=up−1−1p−1≥−1p−1,\varphi_p'(u)=\frac{u^{p-1}-1}{p-1}\ge-\frac1{p-1},

=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.
Questions for authors

See Weaknesses

Reviewer_G3gMOpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper proposes a faster method for unbalanced optimal transport. It removes high-cost edges and splits the remaining edges into blocks. Edges in the same block share no rows or columns. This allows the updates within a block to run in parallel. The paper gives feasibility conditions and convergence bounds for the pruned problem. Experiments cover image transport, LiDAR change detection, and domain adaptation.

Critical strengths
  1. The matching blocks give independent scalar updates and smaller block smoothness constants. This provides a useful form of parallelism.
  2. The image experiments separate pruning and splitting. The supplied solvers also agree with independent convex solves and checks on an original image pair.
Critical weaknesses
  1. The total complexity does not account for graph construction, block partitioning, and full GS selection. The code scans all retained edges after each update. These costs need to be included.
  2. The convergence bound applies to the pruned problem. A general pruning-error bound for the original UOT cost is missing. Safe cutoffs and empirical thresholds should be distinguished.
  3. The LiDAR code fills uncovered targets with a nearest-neighbor median. Under the supplied settings, every predicted change must use this fallback. The solver controls coverage, but the fallback’s contribution to the gain is not isolated.
Questions for authors
  1. What is the pruning error relative to the original UOT cost? Which choices of T preserve the optimum?
  2. What are the total time and memory costs, including preprocessing and GS block selection?
  3. Can you benchmark against known parallel algorithms that can run on both CPUs and GPUs? For example, [1], [2], and [3].
  4. Does the supplied LiDAR configuration reproduce the reported result? How much gain comes from the fallback? Please compare solvers with the same objective and prediction rule.

[1] Sinkhorn Distances: Lightspeed Computation of Optimal Transport.

[2] Scaling Algorithms for Unbalanced Optimal Transport Problems.

[3] A Combinatorial Algorithm for Approximating the Optimal Transport in the Parallel and MPC Settings.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.