- 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
-
The paper makes the admissible positive evidence explicit and distinguishes it from a negative witness that can be replayed on the candidate coupling.
-
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
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 ? 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 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.
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.