acceptodds
Under review as a conference paper at ICLR 2027

Verification Asymmetry in Optimal Transport

Abstract

Optimal transport (OT) solvers often return a coupling that is subsequently used as a correspondence, alignment, or training target. We study a question distinct from computing that coupling: given a candidate and a declared proof language, how much evidence is needed to certify near-optimality or refute it? We introduce a candidate-specific, proof-language-relative verification profile with two sides: the interaction width of a positive certificate and the size of a replayable negative witness. These requirements can scale differently. Under coordinate-block proofs, a -dimensional parity family requires full width to certify any optimal candidate to tolerance below , while every full-support suboptimal candidate has a four-edge refutation. The positive obstruction persists under Wasserstein perturbations; on the negative side, some four-cycle has unit improvement margin at least half of the global suboptimality gap. We also show how local Kantorovich duals compose into global lower bounds, when certificate gaps control plan error, and when incomplete observations force abstention. VerifyOT returns Certified, Refuted, or Unknown. Theorem-aligned experiments recover the predicted width regimes and four-cycle bound. On Sinkhorn/Greenkhorn candidates, positive closure appears near the exact-OT regime, while every repaired full-support output in our audit admits an exact four-cycle refutation under the common unregularized cost.

Primary area:
optimization
Keywords:
optimal transport, transport plan verification, optimality certificates, Kantorovich duality, verification complexity

Reviews

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

This paper studies the verification of a candidate optimal-transport coupling under a specified target cost and proof language. It introduces a verification profile consisting of the maximum coordinate-block dimension needed for a positive certificate and the number of edges needed for an improving transport-cycle witness. Its central example uses even- and odd-parity distributions: coordinate-block certification requires full dimension, whereas every full-support suboptimal coupling admits a four-edge refutation.

Critical strengths
  1. The paper makes the admissible positive evidence explicit and distinguishes it from a negative witness that can be replayed on the candidate coupling.

  2. The auditor’s design emphasizes checked dual feasibility, feasible candidate plans, and replayed improvements.

Critical weaknesses

1.The positive side of the main separation is a limitation of sums of coordinate-block OT bounds. The parity instance itself has a simple unrestricted dual certificate: every source–target squared distance is at least (4), so

ui=4,vj=0u_i=4,\qquad v_j=0

is dual-feasible and matching the optimum. However, why is this the relevant restriction for an auditor that already receives the target cost and candidate coupling?

On the negative side, full-support four-cycle refutability follows directly from the classical complementary-slackness structure of the transport LP. Several supporting results are also direct applications of duality or polyhedral arguments. Existing work, including the cited Observable Wasserstein paper, already studies hierarchies of lower bounds obtained from restricted observations, although it does not introduce this paper’s joint positive/negative profile.

The particular combination of these ingredients is a contribution, but the paper does not yet demonstrate that its profile yields sufficiently substantial additional insight into verification difficulty or useful verification decisions. A stronger justification of the evidence model and its consequences would materially improve the case for acceptance.

2.The positive and negative headline results concern different propositions. A certificate at tolerance (\varepsilon) establishes approximate optimality, whereas a four-cycle improvement at (\tau=0) only disproves exact optimality. Consequently, the same candidate can satisfy both conditions. This occurs in the actual-solver audit: all 80 repaired candidates at the smallest regularization satisfy the 1% positive tolerance and also admit exact four-cycle refutations.

The reported evidence does not show a convincing regime in which the proposed local audit resolves the practically relevant accuracy question. The broader LOCAL campaign produces 0/2200 positive certifications. In the follow-up audit, successful positive certificates require full coordinate-block width, using the exact full-space OT value in the reported setup. Meanwhile, although all 320 repaired solver outputs admit an improving four-cycle, no single four-cycle achieves a gain exceeding (0.01C^\star), even when the mean global relative suboptimality reaches 24.82%.

Questions for authors

What concrete computational or information-access constraint makes the coordinate-block certificate language appropriate for VerifyOT? In particular, how should the parity width obstruction be interpreted relative to the simple unrestricted certificate ui=4, vj=0u_i=4,\ v_j=0? Can the authors identify a setting in the existing results where the restricted audit gives a useful decision compared with a conventional global dual-feasibility/gap check?

2 comments

Thank you for identifying the differences between unrestricted and restricted evidence, and between exact refutation and approximate-optimality decisions. We have clarified both and added accuracy-matched analysis.

  1. Why this evidence language? Your parity dual (ui,vj)=(4,0)(u_i,v_j)=(4,0) is optimal and gauge-equivalent to (2,2)(2,2). We agree that the parity instance is easy to verify with an unrestricted dual; it is not an example of unrestricted OT verification hardness. Our question is instead when independently checked lower-dimensional OT bounds compose into a tight global certificate. For orthogonal squared-Euclidean costs, block duals compose soundly even though their optimal couplings need not be compatible. Proposition 5 gives the exact compatibility condition; Theorems 3 and 6 establish a sharp obstruction for the parity family and its Wasserstein neighborhood under the fixed-coordinate grammar. The unrestricted dual isolates a proof-language obstruction, not intrinsic OT hardness. We do not posit an application-specific block-access restriction in the full-cost audit; Section 5's incomplete-query oracle is a separate model.
  2. Classical versus new results. Kantorovich dual feasibility and residual-cycle optimality are classical. Our contribution is a candidate-specific profile pairing positive certificate width with replayable negative-witness size. Theorem 3 makes two structural statements for different candidate classes and thresholds: optimal candidates at ε<4\varepsilon<4 versus full-support suboptimal candidates at τ=0\tau=0. This is not a same-candidate, matched-tolerance separation. Appendix C.1 strengthens the four-cycle unit-margin bound to M≥ΔM\ge\Delta, with executable gain remaining capacity-dependent; Proposition R1 gives exact positive-threshold simple-cycle size in a specified Euclidean family, not packet or search complexity. We distinguish these statements from restricted-observable lower-bound hierarchies.
  3. A common accuracy question. In the revised accuracy mode, U−L≤εU-L\le\varepsilon certifies ε\varepsilon-optimality; a replayed feasible improvement G>εG>\varepsilon refutes it; otherwise the outcome is UNKNOWN. Because G≤U−P⋆≤U−LG\le U-P^\star\le U-L, the two decisions cannot conflict. An improving cycle with G≤εG\le\varepsilon does not refute ε\varepsilon-optimality. For relative accuracy, U≤(1+ρ)LU\le(1+\rho)L (L>0L>0) and U>(1+ρ)UnewU>(1+\rho)U_{\mathrm{new}}, for a verified feasible alternative, are sufficient observable tests. The 0.01P⋆0.01P^\star tolerance used in the experiment is an offline reference.
  4. What decisions are actually supported? Table 3 shows that, among 320 protocol-reconstructed repaired candidates, one global c-transform certifies 80/320 at the offline 1% target, while tested width-one/two blocks certify none. We do not claim a positive-coverage advantage for blocks. Table 5 then compares evidence at the same tolerance: a single four-cycle refutes 0/320; sequential feasible packets refute 160/320; global c-transform plus packets gives 80 certified, 160 refuted, and 80 unknown. In the explicitly post-hoc Iris example (Table 7, r=.10r=.10), the fixed one-sweep global dual gap is 6.8654% of P⋆P^\star and remains inconclusive at 1%, whereas a replayed packet produces a feasible gain of 1.8457% and refutes 1%-optimality. This is a decision beyond that particular gap check, not a block-specific advantage or superiority to global re-solving. Raw-solver convergence and the original LOCAL noncertifications remain separately reported. VerifyOT exposes the available positive and negative evidence; it does not replace unrestricted verification.

Thank you for your careful review. We would like to clarify the scientific motivation for studying coordinate-block certificates when unrestricted global dual verification is available.

We agree that our full-cost audit does not impose an information-access restriction, and the tested low-width certificates do not outperform global dual checks (Table 3). Our contribution is therefore not a claim of computational or certification-coverage superiority. Instead, we study a specific local-to-global question: although squared-Euclidean costs decompose exactly across orthogonal blocks, independently optimal projected OT couplings need not admit a common realization. Consequently, the sum of projected OT optima can be strictly smaller than the global optimum, even though the composed local duals remain globally feasible.

Proposition 5 gives a necessary and sufficient condition for exact compatibility. Theorems 3 and 6 establish a fixed-coordinate family and its Wasserstein neighborhood where this compositional gap persists below full interaction width. Appendix C.4 further clarifies the basis dependence of this obstruction. Thus, verification width characterizes the expressive limitations of a declared certificate language, rather than the intrinsic difficulty of unrestricted OT verification.

Separately, your concern about the mismatch between exact refutation and approximate-optimality certification motivated an additional theoretical result. Proposition R1 establishes that, for a specified squared-Euclidean family and positive thresholds (\tau=c\Delta) in its stated range, the shortest single simple-cycle witness requires (\Theta(n)) edges, despite four-edge exact refutability under full support. This is a witness-size result, not a computational complexity lower bound. Table 5 evaluates both branches at a common offline 1% tolerance, without attributing sequential-packet gains to the block certificate language.

Together, these results address two distinct structural questions: when independently verified local OT evidence can compose into a tight global certificate, and how the required negative evidence changes with the accuracy threshold. We do not claim an advantage over unrestricted global verification; identifying practical settings where restricted certificates are preferable remains open.

We appreciate your consideration of these clarifications and the revised manuscript.

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

The paper formulates the verification of a coupling γ^\hat\gamma returned by an OT solver as a problem separate from computing the optimal coupling. Relative to a declared proof language (the coordinate-block grammar), it defines a positive verification width wε+w_\varepsilon^+ (the smallest maximum block dimension of an orthogonal block partition whose sum of local Kantorovich duals closes an ε\varepsilon-certificate) and a negative refutation size ℓτ−\ell_\tau^- (the minimum number of edges of a replayable improving cycle), and calls the pair the verification profile. The main results are a separation on the parity family with wε+=dw^+_\varepsilon = d versus ℓ0−=4\ell^-_0 = 4 (Thm 3), persistence of the positive obstruction under W2W_2 perturbations (Thm 6), compositional soundness of local duals and a compatibility criterion for exact block certificates (Thm 4, Prop 5), control of plan error by the certificate gap (Thm 7), rigidity of full-support couplings and four-cycle refutability (Thm 8, Cor 9), the existence of a four-cycle whose unit margin is at least half of the global gap Δ\Delta (Thm 10), and the necessity of abstention under finite queries (Thm 11). These are implemented as an auditor, VerifyOT, that returns CERTIFIED / REFUTED / UNKNOWN. Experiments on synthetic data, small real datasets, and actual Sinkhorn/Greenkhorn outputs confirm the predicted width hierarchy and four-cycle margins.

Critical strengths
  1. Verification is explicitly defined as a candidate-specific, proof-language-relative problem, and the three-valued output enforces the operational contract that a failed search is never taken as evidence of optimality. This is sound evaluation practice and a useful auditing framework for applications that consume couplings downstream (alignment, pseudo-labels).

  2. Thm 10 (a four-cycle whose unit margin is at least half of the global gap) has a short, self-contained proof, and the experiments confirm that the margin ratio always exceeds 1 by a wide factor. This gives REFUTED outputs a quantitative meaning.

Critical weaknesses
  1. The main empirical highlight (refutation of every full-support solver output) follows trivially from Thm 8, so the experiments add no information beyond the theory. On the positive side, certificates do not close at low width, which leaves the auditor with a narrow practical range. As a conceptual framework the paper is clear, but the technical and empirical contribution is thin.

  2. The lower bound of Thm 3 depends heavily on the coordinate-block grammar, and the parity family is deliberately constructed to be invisible to that grammar. Whether the obstruction persists under more natural proof languages (arbitrary low-rank projections, sliced certificates) is touched on only empirically in the basis-sensitivity experiment of Appendix B and remains open theoretically.

Questions for authors
  1. Can you characterize when the positive branch of VerifyOT returns CERTIFIED at low width in real applications, i.e., conditions on the data under which the compatibility criterion of Prop 5 holds? An example on real data would help.

  2. Under entropic regularization, refutation at τ=0\tau = 0 always succeeds, so in practice the choice of the threshold τ\tau (e.g., 0.01 C⋆0.01\,C^\star) is essential. Do you have guidance on choosing τ\tau, or theoretical results on τ\tau-refutation size?

3 comments

Thank you for recognizing the candidate-specific verification formulation and the quantitative four-cycle result. We have strengthened the characterization of low-width closure, clarified the projection dependence of the lower bound, and examined refutation at nonzero accuracy thresholds.

  1. When can low width certify? Proposition 5 gives an exact structural condition: the projected OT problems must admit a common optimal coupling. Factorization of both measures over the same orthogonal blocks is sufficient; zero correlation alone is not. For an approximate feasible candidate, checked block-dual values D_r and its projected costs U_r yield the a posteriori sufficient test U−L^P=∑r(Ur−Dr)≤εU-\widehat L_{\mathcal P}=\sum_r(U_r-D_r)\le\varepsilon, without knowing P⋆P^\star. The structural condition and the candidate-specific test answer different questions. Table 4 shows that all ten Iris exact-reference candidates (d=4d=4) certify at width two for a 1% target, with mean checked lower-bound deficit 0.8283% of P⋆P^\star. These are real-data reference plans, not approximate solver outputs; none of the 320 separately reconstructed entropic candidates certifies at 1% under the tested width-two partitions. We therefore do not infer broad low-width coverage from the reference example.
  2. Scope of the parity obstruction. Theorem 3 is explicitly relative to the fixed-coordinate grammar. Appendix C.4 gives a normalized Hadamard rotation at d=4d=4 under which four one-dimensional projected OT values sum to the global parity value 4; the construction extends to Sylvester dimensions. Thus the obstruction is not invariant under a change of admissible basis. This is a boundary of the theorem, not a lower bound for arbitrary low-rank projections or an averaged-sliced proof language. The latter would require its own sound composition rule and complexity analysis.
  3. Meaningful thresholds and witness size. Exact refutability at τ=0\tau=0 is distinct from failing a desired approximation tolerance. We therefore use accuracy-matched decisions: U−L≤εU-L\le\varepsilon certifies; a replayed feasible gain G>εG>\varepsilon refutes; otherwise the result is UNKNOWN. Since G≤U−P⋆≤U−LG\le U-P^\star\le U-L, the decisions cannot conflict. For relative accuracy U≤(1+ρ)P⋆U\le(1+\rho)P^\star, observable sufficient tests are U≤(1+ρ)LU\le(1+\rho)L (L>0L>0) and U>(1+ρ)UnewU>(1+\rho)U_{\mathrm{new}} for a verified feasible alternative. The reported 0.01P⋆0.01P^\star threshold is an offline reference, not a deployment rule. Theorem 10 concerns unit improvement margin, whereas executable gain also depends on removable mass. Appendix C.1 strengthens the guarantee to M≥ΔM\ge\Delta and gives an asymptotically sharp squared-Euclidean family. Proposition R1 characterizes a different, nonzero-threshold question: in a specified Euclidean family, with K=1−α+α/nK=1-\alpha+\alpha/n, the maximum gain of one simple 2s2s-edge cycle is (s−1)K(s-1)K, hence ℓτ,simp−=2(⌊τ/K⌋+2)\ell^-_{\tau,\mathrm{simp}}=2(\lfloor\tau/K\rfloor+2) when this is at most 2n2n, and infinity otherwise. This is not a general search bound. In the reconstructed accuracy-matched audit (Table 5), the best single four-cycle refutes 0/320 candidates at 1%, whereas sequential feasible packets refute 160/320. Packets are a distinct witness format and are not a consequence of Proposition R1. Unlike the original zero-threshold existence checks, this comparison distinguishes short exact refutations from evidence that resolves a specified accuracy question; it does not establish a low-width performance advantage.

Thank you for the careful response and the added material. The two-dimensional example in the introduction, the accuracy-matched decision mode, and the comparison with global dual certificates (Tables 3 and 5) make the paper clearer and its scope more honest.

The new results also confirm the limits I raised. The tested width-one/two certificates certify none of the 320 candidates, and the Hadamard rotation in App. C.4 removes the parity obstruction. The positive lower bound is therefore specific to the coordinate grammar, and low-width certification has limited practical reach so far. I would also suggest that the abstract present the 320/320 four-cycle refutations as a consequence of Theorem 8 rather than as an empirical finding.

I keep my score of 3 (weak acceptance).

Thank you for your careful follow-up and for acknowledging the improvements in the revised manuscript.

We agree that the 320/320 exact four-cycle refutations should be presented as an instance of Theorem 8, rather than as an independent empirical finding. The audit verifies this theoretical consequence on the repaired full-support solver outputs. We will clarify this distinction in the abstract.

We appreciate your constructive feedback.

Reviewer_tmSZOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2(+1)
Soundness
3
Read review
Paper summary

This paper studies the verification of optimal transport couplings under a specific family of admissible certificates. It introduces a verification profile measuring the interaction width of a positive certificate and the size of a negative witness. For a parity-based construction, coordinate-block lower bounds remain zero until a full-dimensional block is used. On the negative side, every full-support suboptimal coupling admits an improving four-cycle. The authors then propose the VerifyOT framework, which combines certificate construction with witness search. They evaluate their framework on synthetic benchmarks and real-world outputs.

Critical strengths
  • The paper gives a concrete example of the limitations of coordinate-block certificates. The parity construction is an explicit instance in which all strict coordinate-block lower bounds are zero, despite a positive optimal transport cost.
  • The authors extend this observation beyond the exact parity construction by showing that the certificate gap persists under controlled Wasserstein perturbations.
  • The evaluation includes both theorem-aligned synthetic controls and solver-produced couplings, allowing the theoretical observations to be examined beyond the constructed examples.
Critical weaknesses
  1. My main concern is the exposition of the paper. Allthough the introduction motivates the overall question of the paper, Sections 3-5 introduce several definitions and results without doing the necessary explanation on their roles in the overall argument. It was difficult for me to distinguish foundational observations from the main contributions and to understand how the different results fit together. More intuitive explanations and a example introducing the certificate construction before the general statements would substantially improve accessibility
  2. The significance of the chosen certificate family needs stronger motivation. The parity result establishes a limitation of coordinate-block certificates, rather than a general obstacle to OT verification. The paper acknowledges this restriction, but it remains unclear why this particular family represents an important verification constraint. A clearer explanation of the settings in which these certificates are useful, and why their limitations matter in those settings, would strengthen the contribution.
  3. For me, the novelty is difficult to assess from the current presentation. Some parts appear to be closely related to standard dual feasibility or residual-cycle arguments. The proposed verification profile may provide a useful contribution, but the paper would benefit from a clear separation between established consequences and new results. My familiarity with the optimal transport literature is limited, so I raise this as a request for clarification rather than a definitive weakness.
  4. The experiments match the theoretical predictions, but they do not provide a direct comparison against certificates obtained by existing solvers using dual potentials for example. A comparison of certificate quality, certification coverage, and additional computational cost would help establish when the proposed approach is beneficial.
Questions for authors

Please comment on the Weaknesses.

3 comments

Thank you for the constructive review. We have clarified the argument connecting the results and added the requested comparison with conventional OT certificates.

  1. Exposition. We now introduce a two-dimensional example before the general statements: uniform sources (-1,-1), (1,1) and targets (-1,1), (1,-1). Each coordinate-wise OT problem has value zero, but their zero-cost matchings cannot be realized by one coupling. The full-space optimum is 4, immediately certified by the unrestricted dual f=g=2f=g=2. Thus the example illustrates a failure of compositional local evidence, not hardness of unrestricted verification. Sections 3–6 then develop local certificate composition and compatibility, executable negative witnesses, the separate incomplete-query model, and VerifyOT's checked three-valued decisions (Figure 1).
  2. Why this evidence language? Orthogonal squared-Euclidean costs admit valid global lower bounds assembled from independently checked block duals. Yet solving every projected OT problem exactly does not ensure that its optima are jointly realizable. Proposition 5 gives the necessary and sufficient condition for exact block closure: the projected optimal-coupling sets must share a common coupling. Theorems 3 and 6 show that, for the parity family and its Wasserstein neighborhood, a fixed-coordinate grammar can require full interaction width. These are statements about the expressiveness of a declared certificate class, not a claimed advantage over unrestricted global duals. The distinction is visible in the offline decomposition U−L=(U−P⋆)+(P⋆−L)U-L=(U-P^\star)+(P^\star-L). In the illustrative Iris case (Table 7, r=.01r=.01), candidate error is 0.6984% of P⋆P^\star, but the width-two certificate gap is 1.5841%, so it cannot establish 1% accuracy, although a global c-transform certificate can.
  3. Novelty. Kantorovich duality and residual-cycle optimality are classical soundness tools, not new criteria claimed here. Our candidate-specific, proof-language-relative profile jointly records positive certificate width and the size of replayable negative evidence. The fixed-grammar separation, compatibility characterization, and perturbation stability give concrete structural results. Appendix C.1 strengthens the four-cycle unit-margin bound to M≥ΔM\ge\Delta; Proposition R1 characterizes positive-threshold simple-cycle length in a specified Euclidean family. Neither result implies basis-independent verification hardness or a general search-time advantage. We clarify the relationship to prior restricted-observable Wasserstein bounds.
  4. Certificate comparison. Table 3 directly compares corrected solver-native duals, one global c-transform sweep, and PCA width-one/two certificates on the same 320 protocol-reconstructed, feasibility-repaired candidates. At the offline 1% tolerance, certification counts are 0/320, 80/320, 0/320, and 0/320, respectively; median lower-bound deficits are 37.710%, 0.491%, 19.635%, and 15.057%. The global certificate is stronger on this cohort. The table also reports construction and checking costs, distinguishing global per-candidate checks from per-base block bounds reusable across eight candidates. These component times have different accounting scopes and are not matched end-to-end runtimes. The comparison quantifies what the restricted proof language cannot certify; it does not claim that low-width blocks outperform unrestricted global checks. The reconstruction is reported separately from the original registered audit.

Thank you for your response and the additions to your paper. The added example improves the exposition and the new comparison addresses my concerns about the missing certificate baselines.

My remaining concern is the significance of this particular restricted language, as also noted by other reviewers. The motivation remains unclear to me. Moreover, the new theoretical and experimental additions are only contained in the appendix and not in the main paper.

Overall, the revision has improved my assessment, but the mentioned concerns remain. Therefore, I will raise my score to a weak accept.

Thank you for taking another look at our revised manuscript and for reconsidering your assessment. We appreciate your recognition of the improvements in exposition and the added certificate comparisons.

We understand your remaining concerns about the motivation for the restricted certificate language and the presentation of the additional results. We will further clarify the motivation and intended scope of the proposed framework and better integrate the key theoretical and experimental findings into the main text in a subsequent revision.

Thank you again for your constructive feedback.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.