acceptodds
Under review as a conference paper at ICLR 2027

Coarse-to-Fine: Hierarchical Incremental Acceleration for Solving Exact Semi-Discrete Optimal Transport

Abstract

Monte Carlo (MC)-based geometric variational methods address the intractability of analytical Power-Voronoi cell volume computation for semi-discrete optimal transport. However, their global cold-start synchronous iteration incurs drastically rising partitioning cost as target points scale up, severely slowing total solving efficiency. To mitigate this limitation, this paper proposes a hierarchical fast solving framework. First, we preprocess target points and partition them layer by layer in a nearest-to-farthest order. Second, we combine the head and tail layers to build global skeleton that locks the overall Power diagram topology in advance. In incremental updates, each point in every newly added layer is initialized with the Brenier height of its nearest solved neighbor. Using converged layer outputs for warm-start refinement, we sequentially solve optimal Brenier heights for all targets layer by layer. Experiments on standard and complex real-world distributions show that our approach achieves an average 53.88% acceleration versus the original MC solver, with stable permille-scale error between solved Brenier heights and ground truth. Supplementary tests on generative modeling, adversarial attacks and out-of-distribution overconfidence further confirm that our method causes only negligible percentage-to-permille scale performance deviations in downstream tasks.

Primary area:
optimization
Keywords:
Semi-discrete Optimal Transport, Hierarchical Solver, Geometric Variational Principle

Reviews

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

In this paper, the authors present new practical techniques for scaling up the computation of semi-discrete optimal transport plans. The first is a preprocessing of the target points into a layered network that groups similar points together. Then, the authors use this preprocessing in a hierarchical sequence of semi-discrete optimal transport solutions, where the solution to layer ii and the connections to layer i+1i+1 are used to warmstart the initial solution to the computed larger solution in layer i+1i+1. The authors show experimentally that this layered structure and warmstarting sequence significantly improves the runtime of computing semi-discrete optimal transport plans.

Critical strengths

I really enjoyed reading this paper. There was a clear issue with existing work on semi-discrete optimal transport solvers: variational methods for semi-discrete optimal transport can still require many iterations, and each iteration can still require comparing each sample point to its candidate cell centers. The authors propose a cute solution to this problem, imposing a data structure similar to the hierarchical navigable small world framework to initialize weights of nearby points similarly and speed up assignment of sample points to corresponding cell centers. Experimentally, this cute solution leads to a significant improvement in runtimes. Overall, the paper was pretty well written and quite easy to follow.

Critical weaknesses

My only issue would be that there is a chance the impact of their results is small. I found that their discussion of related work was also a bit bare, mostly restricted to existing variational methods for semi-discrete optimal transport. A more detailed comparison with other existing work may remove this concern, however. Without just saying "related work is weak", I wanted to give some thoughts on other potentially useful works to compare against.

Nearest neighbor search: (useful when assigning samples to their respective cells)

  • Classical algorithms for nearest neighbor search suffer from the curse of dimensionality, in the worst case attaining nΩ(d)n^{\Omega(d)} space ("Geometric approximation algorithms" by Har-Peled is a great initial reference)
  • Modern nearest neighbor search designed to mitigate the curse of dimensionality follows the hierarchical navigable small world framework, which is very similar to the preprocessing step performed by the authors ("Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs" by Malkov and Yashunin)

Other semi-discrete optimal transport solvers:

  • The authors refer to "conventional numerical solvers" but give no citations. Is this in reference to first-order optimization over the power cell assignments (e.g. "Minkowski-type theorems and least-squares clustering" by Aurenhammer et al. and/or "Notions of optimal transport theory and how to implement them on a computer" by Levy and Schwindt)?
  • The work described by the authors is not the first to avoid comparing all sample-to-target pairs! A comparison against other geometric preprocessing algorithms would be useful. Some such references include:
  1. "Approximating the Earth Mover's Distance between sets of geometric objects" by van Kreveld et al.
  2. "A combinatorial algorithm for the semi-discrete optimal transport problem" by Agarwal et al.
Questions for authors
  • See the weaknesses above. How does your layered approach compare to (1) the hierarchical navigable small world framework, and (2) the geometric preprocessing algorithms for semi-discrete optimal transport?
Reviewer_reyWOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

The authors work on the semi-discrete optimal transport problem (SDOT) with quadratic cost. This problem is relevant to modern machine learning and has unique challenges when solving high-dimensional problems, particularly when the number of discrete target points becomes large. The authors propose a hierarchical incremental framework to accelerate the MC based geometric variational solver. They report an average run time reduction of 53.88% compared with the original full-scale cold -start solver. The main contribution of the paper is algorithmic. The proposed method consists of three stages.

First, Algorithm 1 introduces a hierarchical preprocessing strategy for the target point set. An initial subset Y1\mathcal Y_1 is selected uniformly at random, with its size determined by the hierarchical ratio rr. The remaining points are partitioned into ``layers'' by selecting, at each step, those closest to the union of the previously selected layers. This construction produces a partition \mathcal H=\{(\mathcal Y_k,\nu_k,I_k)}_{k=1}^{N{\mathrm{layer}}\},

where Yk\mathcal Y_k contains the target points in layer kk, νk\nu_k their corresponding weights, and iki_k their indices in the original target set.

Second, the authors construct an initial head-tail skeleton by combining the first and last layers.

The MC based solver is then applied to the reduced target set. The remaining layers are added sequentially. For each newly introduced point, its Brenier height is initialized using the height of its nearest neighbor in the previously solved target set, followed by iterative refinement.

The theoretical motivation is given by Lemma 1, which establishes that Brenier heights associated with nearby target points are close for a fixed SDOT problem. The authors further introduce Lemma 4 and Theorem 1 to quantify the initialization error when additional target points are incorporated. In particular, Theorem 1 states an error bound involving the distance to the nearest previously processed target point and a correction depending on the mass of the newly introduced point.

Finally, the authors evaluate the method on synthetic and real-world latent distributions, comparing computational efficiency and numerical accuracy against existing SDOT solvers. Figure 2 and Table 3 report the dependence of runtime and numerical error on the number of target points, dimension, and hierarchical ratio.

Critical strengths
  1. The method is motivated by geometric properties of the Brenier height vector, see Lemma 1. The authors further develop this idea through Lemma 4 and Theorem 1.
  2. Section 3.4 provides a clear breakdown of the computational complexity of the original full-scale cold-start solver and the proposed hierarchical approach. The analysis distinguishes the cost of solving the initial skeleton from the subsequent layer-wise incremental updates.
  3. The numerical experiments provide evidence to support the computational claims. Figure 2 studies the error and speed-up ratio as a function of the number of target points and the hierarchical ratio. Table 3 shows that the computational benefits hold for problems up to dimension 100. I also appreciate the comparisons in Table 4, which provide additional context for the computational performance of the method.
  4. The experiments in Section 4.2 demonstrate the applicability of the proposed framework to existing methods that rely on SDOT.
Critical weaknesses
  1. Dependence on the initial target subset and convergence of the hierarchical construction. The method relies on an initial target subset selected uniformly at random. This subset determines the subsequent hierarchical partition and the resulting head-tail skeleton. However, the experiments do not provide statistical results to verify that the computational efficiency and error do not depend on the initial set. In addition, it is unclear whether an arbitrary initial subset produces a sequence of intermediate SDOT solutions that become progressively closer to the solution of the full problem. Although the proposed method uses the converged solution of each intermediate problem to initialize the next one, the intermediate problems have different target measures. The theoretical results motivate the initialization strategy but do not appear to establish a monotonic improvement. I kindly suggest that the authors include repeated experiments with different initial random seeds, reporting means and standard deviations of the runtime and numerical errors. In particular, for small values of rr, where the subset contains relatively few points. Understandably, they might not be able to do it for all experiments, but please include one or two representative examples.
  2. Missing computational efficiency in downstream applications. As one of the core strengths of the paper is the reduction in speed of computations, I kindly ask the authors to include the quantification of the reduction in SDOT solving time for each application.
Questions for authors
  1. I would appreciate clarification the application of Lemma 4 in Appendix C.4, Lemma 4 considers two target measures supported on the same fixed target set. However, Theorem 1 adds a new target point, which changes the cardinality of the target set. The authors address this by representing the insertion of a new point as an increase in its mass from zero to a positive value. My concern is that a zero-mass target point falls outside the strictly positive target-mass assumptions of the SDOT formulation. Moreover, the Brenier height associated with a zero-mass cell need not to be unique. Could the authors clarify how Lemma 4 applies in this setting? In particular, does the argument require additional assumptions or a limiting procedure as the mass of the newly introduced point approaches zero?
  2. In Section 3.1, the authors state that uniform random sampling provides an initial skeleton with full spatial coverage. Could the authors clarify whether this property is guaranteed or should be understood as an empirical observation? How do the random sampling and small rr affect spatial coverage?
  3. In Figures 2 a-f and Table 3, the authors fix r = 0.2. Although Figures 2g-I study the dependence on rr, could the authors explain the reason for selecting r=0.2r = 0.2 as a default? Can the authors provide guidelines for users on how to choose this value?
  4. I have a few minor suggestions regarding the presentation of the experimental results. Figures 3a and 3b would benefit from explicit labels on the vertical axes. In overall the subfigures from Figure 3 would benefit if they were enlarged. A possible way to do this is to use scientific notation or fewer decimal places in Table 3. Finally, there seems to be a typo error in Equation 15 of Appendix C.3
  5. In Figures 3 e–h, the authors report convergence curves for both the hierarchical and full-scale cold-start solvers. However, Section 4.1 defines the converged solution of the full-scale solver as the ground truth. Could the authors clarify which reference solution is used to compute the error metrics in these figures? In particular, are the intermediate iterates of both algorithms compared against the final solution, or is an independent reference solution used?
  6. Could the authors provide additional details on the computational complexity of the repeated nearest-neighbor searches in Algorithm 1? Are these included in the runtimes reported in Section 4.1?
Reviewer_HnvhOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

This paper proposes a hierarchical fast solving framework to accelerate Monte Carlo (MC)-based geometric variational methods for Semi-Discrete Optimal Transport. Standard MC-based solvers suffer from a bottleneck: they use a full-scale cold-start strategy, which becomes prohibitively expensive and slow as the number of target points scales up. To solve this, the authors introduce a strategy that first partitions the target points into layers, builds a global skeleton using the head and tail layers, and then sequentially solves for the remaining layers using warm starts inherited from nearest neighbors. The proposed method achieves an average 53.88% speed-up compared to the original MC solver while maintaining accuracy.

Critical strengths
  1. By replacing the expensive global cold-start with a layer-wise warm-start strategy, the method achieves massive speed-ups (53.88% on average, and even higher in specific high-sample scenarios) without relying on unstable neural network approximations.
  2. The approach is grounded in the mathematical property that spatially adjacent target points have similar Brenier heights (Lemma 1). This allows the method to preserve high accuracy and universal applicability across diverse data distributions.
Critical weaknesses
  1. The method requires a multi-stage, hierarchical preprocessing algorithm (random sampling, iterative nearest-neighbor partitioning, and head-tail skeleton construction) that is significantly more complex to implement and tune than a straightforward cold-start solver.
  2. The efficiency and accuracy rely on several manually set hyperparameters, such as the hierarchical ratio for initial sampling, the layer-specific convergence thresholds, and the "coarse" vs. "fine" tolerance levels, which may require careful tuning for different datasets.
  3. Unlike recent Neural Network (NN)-based SDOT solvers, this is a purely geometric and numerical solver. While it generalizes better than NNs, it cannot be directly integrated into end-to-end deep learning pipelines that require differentiable transport maps.
Questions for authors
  1. How does the hierarchical partitioning strategy perform when the target points are highly clustered or have extremely irregular spatial distributions, which might violate the nearest-neighbor similarity assumption?
  2. How sensitive is the total runtime and final accuracy to the choice of the hierarchical ratio and is there an adaptive way to choose it without manual tuning?
  3. Since the method relies on Monte Carlo sampling, how does the variance of the gradient estimator behave across different layers, and could it cause instability during the warm-start refinement of the later layers?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.