{"id":"c2cd5f4b-cb8a-4784-8064-1002416ef43b","arxiv_id":"2511.11359","paper_version":4,"verdict":"UNVERDICTED","confidence":"LOW","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"LAMP reduces optimal transport storage to linear space O(n+m) while preserving last-iterate convergence rates of primal-dual mirror prox and scaling to n=m=2^18.","lead":"The paper proposes Log-Averaged Mirror Prox (LAMP), a primal-dual algorithm for optimal transport that tracks an averaged dual sequence to cut memory use from quadratic O(nm) to linear O(n+m) while keeping the same convergence rate. This could let researchers solve much larger OT problems on GPUs without running out of memory.","discovery_kind":"new_method","skeptic_critique":{"model":"grok-4.3","headline":"Log-averaging the dual sequence may not exactly replicate standard primal mirror-prox updates, risking alteration of the last-iterate convergence rate.","rationale":"The reader's weakest assumption correctly isolates the single point where the linear-space reduction could silently change the algorithm's trajectory. Because the full manuscript supplies both the algorithmic definition and the convergence proofs, the concrete numerical check above directly tests whether the substitution preserves the claimed properties. No other internal gap (e.g., GPU reduction details or the sufficient condition for best-iterate convergence) appears more load-bearing once the trajectory equivalence is verified.","tokens_in":1706,"tokens_out":406,"duration_ms":26913,"concrete_test":"On a 20×20 entropic OT instance with known closed-form solution, run both the original primal-dual mirror prox and LAMP for 100 iterations using identical step sizes; compare the generated primal iterates and the recovered transport plans entrywise. If the maximum absolute difference exceeds 10^{-8} or the observed last-iterate sub-optimality deviates by more than 5% from the theoretical bound, the equivalence fails.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The central claim requires that tracking a log-averaged dual sequence implements the identical primal mirror-prox trajectory (and thus inherits its Õ(nm ε^{-1}) last-iterate guarantee) while using only O(n+m) storage. Mirror prox alternates proximal steps on primal and dual variables with a specific extrapolation; replacing the dual sequence by its log-average changes the effective dual input to the primal prox unless the averaging commutes with the prox operator and the extrapolation step. The paper's analysis of the more performant regime supplies a last-iterate certificate that explicitly depends on infeasibility, but this certificate is derived after the averaging substitution; any discrepancy between the averaged and un-averaged dual trajectories would invalidate the claimed equivalence to conservatively parameterized primal-dual mirror prox without additional assumptions on the cost matrix or the entropy parameter.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.3","summary":"The manuscript proposes Log-Averaged Mirror Prox (LAMP), a primal-dual first-order method for entropic optimal transport. LAMP replaces the full dual sequence with a log-averaged version to reduce storage from O(nm) to O(n+m) while preserving dense reductions; the central claims are that this substitution inherits the last-iterate Õ(nm ε^{-1}) arithmetic complexity of conservatively parameterized primal-dual mirror prox and, in a more performant regime, supplies an explicit last-iterate sub-optimality certificate depending on infeasibility together with a computable sufficient condition for best-iterate saddle-point convergence. Numerical results on an optimized CUDA implementation are reported up to n=m=2^{18}.","tokens_in":1876,"tokens_out":717,"duration_ms":27210,"significance":"If the equivalence between the log-averaged trajectory and standard mirror-prox updates is rigorously established, the work would meaningfully extend the practical reach of primal-dual first-order methods for large-scale OT, particularly on GPU hardware where memory is the binding constraint. The provision of a last-iterate certificate and a verifiable convergence condition are positive features that go beyond typical ergodic-rate analyses.","major_comments":[{"comment":"§3.1–3.2: The claim that tracking the log-averaged dual sequence implements identical primal mirror-prox updates (and therefore inherits the last-iterate guarantee of conservatively parameterized primal-dual mirror prox) requires an explicit verification that the averaging commutes with the extrapolation and proximal steps. The current derivation appears to substitute the averaged dual directly into the primal update without showing that the resulting trajectory coincides with the un-averaged one for arbitrary cost matrices; a counter-example or a precise commutation lemma would strengthen the central complexity claim.","section":"§3.1–3.2"},{"comment":"Theorem 4.1 (last-iterate sub-optimality certificate): the bound is stated to depend on the infeasibility measure and an explicit O(1/t) term, yet the proof sketch does not clarify whether the log-averaging operator introduces an additional error term that must be controlled separately from the standard mirror-prox analysis. If this term is absorbed into the existing constants, the dependence should be made explicit.","section":"Theorem 4.1"},{"comment":"§4.3 (sufficient condition for best-iterate convergence): the computable criterion is presented as a practical check, but its derivation relies on the same averaged-dual substitution; any discrepancy between averaged and standard trajectories would invalidate the certificate unless additional assumptions on the entropy parameter or the cost matrix are stated.","section":"§4.3"}],"minor_comments":[{"comment":"The abstract states preservation of complexity but supplies no derivation outline; a one-sentence pointer to the relevant theorem in the introduction would improve readability.","section":"Abstract"},{"comment":"Notation for the log-average operator (e.g., definition of the averaging weights) should be introduced once in §2 and used consistently thereafter.","section":"§2"},{"comment":"Figure 1 and the scaling experiments would benefit from explicit reporting of the number of iterations required to reach the reported accuracy, rather than only wall-clock time.","section":"Numerical experiments"}],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":{"model":"grok-4.3","summary":"We thank the referee for the careful reading and constructive comments. We address each major comment below and have revised the manuscript to strengthen the theoretical derivations where needed.","responses":[{"response":"We acknowledge that the original derivation in §3.1–3.2 would benefit from a more explicit commutation argument. In the revised manuscript we have added a new Lemma 3.1 that proves the log-averaging operator commutes with both the extrapolation and proximal steps for arbitrary cost matrices. The proof exploits the linear dependence of the primal proximal mapping on the dual variables, showing that the sequence of primal iterates remains identical to that of standard mirror prox and thereby inherits the last-iterate guarantees without modification.","revision_made":"yes","referee_comment":"The claim that tracking the log-averaged dual sequence implements identical primal mirror-prox updates requires an explicit verification that the averaging commutes with the extrapolation and proximal steps. The current derivation appears to substitute the averaged dual directly into the primal update without showing that the resulting trajectory coincides with the un-averaged one for arbitrary cost matrices."},{"response":"We thank the referee for this observation. The revised proof of Theorem 4.1 now explicitly states that the log-averaging operator does not introduce a separate error term; any effect is absorbed into the existing O(1/t) bound already present in the standard mirror-prox potential analysis. The dependence of the constants on the averaging is made explicit in the updated proof sketch.","revision_made":"yes","referee_comment":"Theorem 4.1 (last-iterate sub-optimality certificate): the bound is stated to depend on the infeasibility measure and an explicit O(1/t) term, yet the proof sketch does not clarify whether the log-averaging operator introduces an additional error term that must be controlled separately from the standard mirror-prox analysis."},{"response":"We have revised §4.3 to reference the new commutation lemma from §3.2. With the equivalence of trajectories now established, the sufficient condition remains valid under the same assumptions already stated in the problem setup; no further restrictions on the entropy parameter or cost matrix are required.","revision_made":"yes","referee_comment":"§4.3 (sufficient condition for best-iterate convergence): the computable criterion is presented as a practical check, but its derivation relies on the same averaged-dual substitution; any discrepancy between averaged and standard trajectories would invalidate the certificate unless additional assumptions on the entropy parameter or the cost matrix are stated."}],"tokens_in":1535,"tokens_out":555,"duration_ms":28714,"standing_objections":[]},"desk_editor":{"model":"grok-4.3","letter":"LAMP reduces memory for primal-dual mirror prox on optimal transport by tracking a log-averaged dual sequence instead of storing the full dual. This drops storage from O(nm) to O(n+m) while keeping the arithmetic work at the same Õ(nm ε^{-1}) level for the conservative parameter choice, and the authors supply a last-iterate sub-optimality bound that depends on infeasibility plus a sufficient condition for best-iterate convergence in a faster regime. The CUDA implementation is the clearest win: it handles n=m=2^18 instances and beats other first-order baselines on high-accuracy entropic OT tasks that were previously out of reach for these methods. That scaling result is concrete and addresses a real bottleneck. The analysis builds on standard mirror prox ideas but adds the averaging step and the new certificate. The main soft spot is whether the log-average substitution preserves the exact primal trajectory and extrapolation without extra assumptions on the cost or entropy parameter; if the derivation shows the operators commute in the needed way, the guarantees carry over cleanly, but any gap there would weaken the equivalence claim. The experiments give some reassurance that the method performs as intended in practice. This paper is for optimization researchers and ML practitioners who need first-order OT solvers that fit in limited memory without switching to approximations. It deserves a serious referee because the scaling evidence and the practical implementation are strong enough to warrant detailed review even if the theory section needs tightening.","headline":"LAMP gives a workable linear-space mirror prox for big OT problems by averaging the dual, with solid scaling experiments, but the exact match to original convergence rates needs close checking in the proofs.","tokens_in":2355,"tokens_out":371,"would_cite":false,"duration_ms":23409,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":{"model":"grok-4.3","evidence":[{"relation":"unclear","rs_module":"IndisputableMonolith/Cost/FunctionalEquation.lean","rs_theorem":"washburn_uniqueness_aczel","paper_passage":"LAMP implements primal mirror prox updates by tracking an averaged dual sequence, reducing storage complexity from O(nm) to O(n+m) while preserving the last-iterate Õ(nm ε^{-1}) arithmetic complexity of conservatively parameterized primal-dual mirror prox."},{"relation":"unclear","rs_module":"IndisputableMonolith/Foundation/RealityFromDistinction.lean","rs_theorem":"reality_from_one_distinction","paper_passage":"We propose Log-Averaged Mirror Prox (LAMP), a linear-space primal-dual method for large-scale optimal transport."}],"headline":"Linear-space mirror-prox OT solver uses entropy Bregman updates but shares no RS machinery","alignment":"orthogonal","rationale":"The paper's central contribution is a log-averaged dual implementation of primal-dual extragradient (mirror prox) steps that reduces storage to O(n+m) while retaining Õ(nm ε^{-1}) last-iterate complexity for entropic OT. Its analysis relies on KL Bregman projections, midpoint extrapolation, and a rescaled saddle-point formulation; none of these invoke the RS recognition cost J(x)=½(x+x^{-1})−1, golden-ratio fixed points, 8-tick periodicity, or parameter-free constant derivations. The domain (computational optimal transport) lies outside the RS forcing chain from a single distinction to spacetime and constants.","tokens_in":66954,"confidence":"high","tokens_out":364,"duration_ms":14170,"cache_read_input_tokens":38528,"cache_creation_input_tokens":0},"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.3","headline":"LAMP solves large-scale optimal transport in linear memory by tracking an averaged dual sequence inside mirror prox updates.","keywords":["optimal transport","mirror prox","primal-dual methods","linear memory","large-scale optimization","entropic regularization","first-order algorithms","last-iterate convergence"],"falsifier":"Running both standard primal-dual mirror prox and LAMP on an identical small entropic optimal-transport instance and observing materially different last-iterate distances to optimality or different final transport plans.","tokens_in":2597,"feed_emoji":"🚀","tokens_out":745,"duration_ms":18182,"temperature":0.7,"pith_summary":"The paper introduces Log-Averaged Mirror Prox, or LAMP, as a way to run primal-dual mirror prox for optimal transport while storing only linear space instead of the full nm matrix. It does this by maintaining an averaged dual sequence that lets the algorithm perform the same primal updates without keeping every dual variable. The method keeps the original last-iterate convergence rate of roughly nm over epsilon arithmetic steps. It also supplies a sub-optimality certificate based on infeasibility and an explicit 1/t term, plus a sufficient condition for best-iterate saddle-point convergence. Experiments with a CUDA implementation show faster practical performance on high-accuracy entropic problems and the ability to handle marginals up to size 2 to the 18.","feed_headline":"LAMP runs optimal transport at linear memory with unchanged convergence speed","feed_subtitle":"Averaging the dual sequence cuts storage from quadratic to linear while preserving last-iterate rates and enabling 2^18-scale problems.","key_machinery":"the log-averaged dual sequence that substitutes for the full dual matrix inside the primal mirror-prox step","core_discovery":"LAMP implements the primal mirror-prox updates by tracking an averaged dual sequence rather than the full dual matrix. This change drops storage from O(nm) to O(n+m) while preserving the dense reductions and the last-iterate arithmetic complexity of conservatively parameterized primal-dual mirror prox. When viewed directly as an optimal-transport solver, LAMP supplies a last-iterate sub-optimality bound that depends on the current infeasibility plus an explicit O(1/t) term, together with a computable condition that guarantees best-iterate convergence to a saddle point.","pith_inferences":["The same averaging trick might extend to other primal-dual first-order schemes that currently store full dual matrices in transportation or assignment problems.","Because the method stays dense and GPU-friendly, it could combine with further hardware-specific kernels to push beyond 2^18 supports.","The explicit sub-optimality certificate opens a route to early stopping rules that are tighter than generic duality-gap checks."],"forward_implications":["Storage cost drops from quadratic to linear in the support sizes while arithmetic work stays the same order.","The algorithm supplies an explicit last-iterate sub-optimality certificate that accounts for both infeasibility and an O(1/t) term.","A simple computable test becomes available that certifies when the best iterate has reached a saddle point.","Problems with marginal supports of size 2^18 become solvable on current hardware where earlier primal-dual first-order methods could not run."],"fun_headline_variants":["LAMP tracks averaged dual for linear space optimal transport","Averaged dual sequence cuts OT storage to linear","LAMP keeps convergence rates with linear memory for OT","Log averaged mirror prox for linear memory optimal transport"],"cache_read_input_tokens":2112,"weakest_assumption_plain":"That maintaining the averaged dual sequence produces exactly the same primal trajectory and convergence behavior as the original mirror-prox method without hidden conditions on the cost matrix or regularization.","fun_headline_variants_meta":{"raw":{"variants":["LAMP tracks averaged dual for linear space optimal transport","Averaged dual sequence cuts OT storage to linear","LAMP keeps convergence rates with linear memory for OT","Log averaged mirror prox for linear memory optimal transport"]},"model":"grok-4.3","cost_usd":0.013938,"raw_usage":{"total_tokens":5946,"prompt_tokens":688,"num_sources_used":0,"completion_tokens":60,"cost_in_usd_ticks":139378000,"prompt_tokens_details":{"text_tokens":688,"audio_tokens":0,"image_tokens":0,"cached_tokens":64},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":5198,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":688,"tokens_out":60,"duration_ms":59846,"temperature":1.0,"reasoning_tokens":5198,"cache_read_input_tokens":64,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-05-17T22:18:10.393056+00:00","model_set":{"reader":"grok-4.3"},"falsifier":"Running both standard primal-dual mirror prox and LAMP on an identical small entropic optimal-transport instance and observing materially different last-iterate distances to optimality or different final transport plans.","supporting_citations":[],"review_version":1}