acceptodds
Withdrawn from ICLR 2027

Partial Optimal Transport on the Circle for All Transported Masses in

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

Abstract

Partial optimal transport permits mass to remain unmatched, making it useful for comparing incomplete or contaminated distributions. On the real line, PAWL computes the entire transport profile—the optimal cost at every transported mass—in log-linear time. Extending this result to the circle requires resolving the cut optimization that already appears in balanced circular transport. In this paper, we introduce PAWC, an exact algorithm for circular partial -Wasserstein transport between discrete measures with distinct support points and a common atom weight. For atoms in total and geodesic transport cost, PAWC computes the full partial-transport profile and a compact encoding of optimal plans in time and memory. We prove that a single cut is simultaneously optimal for every transported mass and construct it through a free-gap invariant that makes local matching updates consistent with one unwrapping of the circle. This avoids solving a separate line problem at every support gap. Applying the solver to great-circle projections yields a partial extension of spherical sliced Wasserstein. The numerical benchmarks show agreement with the exact reference solvers and the predicted scaling. Applications demonstrate improved robustness in matching shape descriptors under occlusion and clutter and in spherical distribution fitting with contaminated targets.

Primary area:
other topics in machine learning (i.e., none of the above)
Keywords:
Optimal Transport, Partial Optimal Transport, Circular data, Directional data

Reviews

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

The paper introduces PAWC, an exact algorithm for partial optimal transport on the circle (S1\mathbb{S}^1) using the Wasserstein-1 cost. First, the source and target samples are cyclically sorted, and candidate triplets (u,v,m)(u,v,\mathfrak m) are initialized, where m\mathfrak m denotes the marginal transport cost. These candidates are stored in a priority queue ordered by their marginal costs, allowing efficient retrieval of the smallest one. The algorithm then performs K=min⁡(n,m)K=\min(n,m) iterations, each selecting the candidate with the smallest marginal cost, activating its endpoints, updating the optimal transport cost, and inserting newly formed candidates into the queue. This computes the optimal costs for all transported cardinalities in O(Nlog⁡N)O(N\log N) time, where N=n+mN=n+m. The paper presents three experiments: the first compares the computational runtime against two baselines, the second applies the method to shape descriptor matching, and the third extends the approach to the sphere.

Critical strengths

The paper addresses a relatively underexplored area of optimal transport, and the proposed algorithm appears to be novel, to the best of my knowledge. Furthermore, the method operates directly on samples from the circle, without requiring projections or additional approximations. These two points constitute its main strength.

Critical weaknesses

I think the paper in its current state has the following weaknesses:

[W1] Limited discussion and experiments on higher-dimensional spheres. The proposed PAWC solver is formulated for samples on the circle (S1\mathbb{S}^1), and Section 5 briefly introduces an extension to higher-dimensional spheres through spherical slicing. However, this extension is mainly presented as a definition, without sufficient theoretical discussion to justify its applicability to higher-dimensional settings. Furthermore, the experimental evaluation is restricted to S2\mathbb{S}^2, leaving the behavior of the proposed approach in higher dimensions unexplored. Overall, the extension lacks sufficient experimental validation, while most of its theoretical discussion is deferred to the overly dense Appendix J. This also relates to my second concern regarding the overall organization and presentation of the paper.

[W2] Paper organization and flow. Even though I believe the contribution of the paper is good and that it could benefit from a more extensive experimental section, in its current form, the paper is very difficult to follow and parse. In other circumstances, this issue alone would not necessarily lead to rejection. However, given the current state of the paper, I would not recommend acceptance unless major changes are made to its organization and the way the information is presented. Below, I list some of the main points motivating this concern alongside some specific examples:

  • The paper relies heavily on appendices and remarks, making it difficult to follow. The main text is insufficient to understand the key ideas, requiring constant back-and-forth reading between the main text and appendices.

  • The paper would benefit from a dedicated notation section or more precise mathematical definitions in the main text. For example, the cost Ck∘C_k^{\circ} and the active set are introduced without sufficiently explicit mathematical definitions, which are instead deferred to Equations (B.5) and (B.6) in the appendix. Similarly, the mathematical space to which MkM_k belongs is not specified, leaving its representation unclear. These quantities are central to understanding the proposed approach and should be properly defined in the main text rather than requiring readers to consult the appendices.

  • The theorems and lemmas do not clearly specify the assumptions under which they hold. For instance, Theorem 1 should explicitly state that it concerns the Wasserstein-1 distance on the circle, or the authors should clarify that all theoretical statements follow the assumptions introduced earlier. Similarly, Theorem 2 refers to “this extension” without clearly explaining what it means. These issues are not isolated, as similar ambiguities appear throughout the theoretical section, making it difficult to assess the applicability and limitations of the proposed findings.

To summarize, the paper is rather novel and presents an interesting idea; however, its current organization and overall presentation do not meet the standards expected of an A* conference paper. Given that substantial revisions are needed to improve the clarity and readability of the paper, I recommend rejection.

Questions for authors

None

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

In this paper, the authors study partial optimal transport between uniformly weighted discrete measures on the circle with geodesic (W_1) cost. It proposes PAWC, which computes the optimal costs for every transported cardinality in O(Nlog⁡N)O(N\log N) time and O(N)O(N) memory. The main structural result is the existence of a single cut that simultaneously recovers the circular optimum at every cardinality. A free-gap invariant constructs this cut while supporting local matching updates. The paper also uses PAWC to define a spherical sliced partial-transport discrepancy and evaluates applications to shape matching and distribution fitting.

Critical strengths
  1. The simultaneous-cut result is the main part of the paper. Extending PAWL to the circle requires more than adding wrap-around bookkeeping: a cut that is optimal at full mass need not work at smaller masses. Example F.1 makes this distinction concrete and shows that an unsuitable full-mass-optimal cut can incur arbitrarily large relative error. The proposed invariant addresses a real obstacle in obtaining the complete circular profile.

  2. The proof development is written carefully. In particular, the paper distinguishes nested active sets from nested matching edges, and local line marginals from changes in the globally optimal circular cost. The common-cut lemma in Appendix D and the two inequalities establishing the greedy rule in Appendix F provide a coherent route to the main theorem. I did not find an obvious contradiction in this argument.

  3. The complexity analysis is also convincing at the level of operation counts. The doubled-support preprocessing permits constant-time marginal queries, while each activation creates at most one new candidate. Together with lazy heap deletion, this gives the claimed bound without repeatedly solving a line problem.

  4. The reported numerical validation is broader than a comparison of objective values alone. Tests of free gaps, balanced cell interiors, recovered-plan feasibility, and rotation invariance are appropriate for this algorithm. The LP reference is particularly useful because it does not depend on the circular-cut argument.

Critical weaknesses
  1. Appendices K and L report missing application drivers, timing records, and per-run results. Some evaluation details also remain unspecified, including the retrieval-score denominator, confidence-interval calculation, and spherical-loss normalization. These gaps limit assessment of the reported results.

  2. Increasing γ\gamma changes both target batch size and trimming. A comparison with fixed target batches would help isolate the benefit of partial transport.

  3. Although computing the complete profile motivates the method, most experiments select mass using the true clutter or contamination level. An experiment selecting mass without this information would better demonstrate the profile’s practical value.

  4. Common atom weights exclude empirical probability measures with different sample counts. The shape application also uses jitter to avoid coincident supports; its sensitivity to this perturbation is not evaluated.

  5. Section 3.2 could briefly explain why free gaps certify exact greedy updates. The main complexity statement should also distinguish compact plan encoding from explicitly recovering all plans.

Questions for authors
  1. How much of the spherical-fitting improvement remains when target batch size and computational budget are controlled? What exact atom-weight and loss-normalization conventions are used across different values of (\gamma)?

  2. Can the complete profile support a useful mass-selection procedure without access to the true contamination level? Even a small validation-based experiment would help.

  3. Can the results in this paper be generalized to multimarginal POT (Le et al., 2022)? It would be better if you provide a discussion on this direction in the paper.

References

K. Le, H. Nguyen, K. Nguyen, T. Pham, and N. Ho. On multimarginal partial optimal transport: Equivalent forms and computational complexity. In AISTATS, 2022.

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

The paper studies a variant of the partial optimal transport problem on a circle, specifically, bipartite matching problem on a circle. Given n red and m blue points on a circle, the objective is to find a matching of size k between red and blue points, such that the sum of the distances of points (on the circle) in the matching is minimized. The authors give an O(NlogN)O(N log N) exact algorithm for this problem, where N=n+mN=n+m. Additionally, ideas how to generalize this construction are given, although no clear theoretical guarantees are shown.

Optimal transport is obviously a well studied problem. However, as far as I am aware the variation considered by authors has not received prior attention, therefore comparisons are difficult. Chapel and Tavenard [ICLR'2025] has considered the problem on a line an obtain an algorithm with simmiliar running time. The paper can be seen as an extension to this result.

The main idea behind the algorithm is dynamic programing based/inductive. Suppose we have a partial matching of size k−1k-1. To obtain an optimal matching of size kk, we can extend the previous matching by inserting two points into the set of matched points such that they are adjacent to an arc containing already matched points. The challenge is to find the pair of points whose inclusion in the matching increases its cost by the least amount.

Critical strengths

The paper studies a variant of an important problem of optimal transport.

The algorithm presented is essentially near optimal for the problem.

Critical weaknesses

The problem is not well motivated. In particular, the authors only give a single sentence to motivate optimal transport on a circle, without even providing any references. The paper actually studies a simplified version of the optimal transport, it should be well justified why the problem deserves attention.

The paper is hard to follow (compared to the technical depth), specifically, the main body does not include some central definitions (e.g. optimal cut), the (sub)section titles are unhelpful and confusing. While its clear the writers put in effort into the presentation in terms of appearances, I cannot help to feel like the paper is is a not properly polished variant of an AI model's output.

Questions for authors

I have no questions for the authors.

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

Related papers

Discussion (0)

Sign in to comment.