{"id":"2a2bbb7c-4f6d-4c04-9a63-099a79d14f07","arxiv_id":"2505.14371","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"A new quantized optimistic dual averaging algorithm with layer-wise adaptive compression is presented, with theoretical convergence guarantees for monotone variational inequalities and empirical speedups on distributed GAN training.","lead":"The paper develops a layer-wise adaptive gradient quantization framework with theoretical variance and code-length bounds, and applies it to a new distributed optimization algorithm for variational inequalities. The proposed QODA algorithm claims convergence rates comparable to prior methods while removing a restrictive boundedness assumption, and reports large training speedups for GANs on multiple GPUs.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 5.5's proof bounds successive unprojected iterates by the diameter of the test set X, a step that is not justified and undermines the claimed removal of the almost sure boundedness assumption.","rationale":"The reader's weakest assumption identifies exactly the same load-bearing gap: the proof of Theorem 5.5 implicitly assumes the unprojected ODA iterates satisfy a uniform diameter-type bound that is neither stated nor a consequence of the algorithm or the noise assumptions. My concrete one-dimensional check confirms the specific intermediate bound is false under admissible data, so the proof as written does not support the central claim of removing the almost sure boundedness assumption. I see no independent evidence in the paper—such as a separate iterate-boundedness lemma or a machine-checked proof—that repairs this gap. The empirical results are plausible but cannot compensate for the missing theoretical step. Since the reader's verdict of REJECT is consistent with this assessment, I recommend no change to the verdict. A revision would need either to add an explicit bounded-iterates assumption (which would weaken the advertised contribution) or to provide a genuinely new argument controlling ||X_{t+1/2} - X_{t-1/2}|| under only Assumptions 2.1--2.5.","tokens_in":58053,"tokens_out":8670,"duration_ms":82198,"concrete_test":"Construct a 1D instance with K=1, A(x)=x, X=[-1,1], X_1=0, and zero-mean two-point noise U_{3/2} = +100 or -100 with equal probability (this satisfies Assumption 2.4 with sigma = 100). Initialize \\hat V_{1/2}=0 as in the proof. For t=1, X_{3/2}=0 and \\hat V_{3/2} = \\pm 100. From (4), eta_2 = gamma_2 = (1 + 100^2)^(-1/2), so X_2 = -eta_2 * (\\pm 100) and X_{5/2} - X_{3/2} = -(eta_2 + gamma_2) * (\\pm 100), whose squared magnitude is 4. Thus E[(X_{5/2} - X_{3/2})^2] = 4, while D^2 = sup_{p in [-1,1]} ||0 - p||^2 = 1. This directly falsifies the intermediate inequality E||X_{t+1/2} - X_{t-1/2}||^2 <= D^2 used in Eq. (11), showing that the proof of Theorem 5.5 relies on a false step.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The main convergence guarantee, Theorem 5.5, depends on Appendix E.2's Eq. (11), which bounds E||X_{t+1/2} - X_{t-1/2}||^2 by D^2, where D^2 = sup_{p in X} ||X_1 - p||^2 and X is the compact set used to define the restricted gap function. The ODA updates in Algorithm 1 (lines 10, 17--18) are unprojected: X_{t+1/2} = X_t - (gamma_t/K) sum_k \\hat V_{k,t-1/2}. Nothing in the algorithm or in Assumptions 2.1--2.4 forces these extrapolated iterates to remain inside X, and no separate bound on ||X_{t+1/2} - X_{t-1/2}|| is proved. The almost sure boundedness assumption on the dual vectors is being replaced by an unstated boundedness or confinement assumption on the iterates themselves. Without Eq. (11), the S1 and S2 terms in the proof are not known to be O(sqrt(T)), so the advertised O(1/sqrt(T)) gap bound is unsupported. The same issue carries over to Theorem 5.7 and to the claims in Remark 5.8 about avoiding the almost sure boundedness assumption.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper has two components. First, it proposes a general layer-wise unbiased quantization framework with adaptive sequences of quantization levels per layer, and derives variance and code-length bounds (Theorems 5.1 and 5.3) that generalize global quantizers such as QSGD, NUQSGD, and Q-GenX, with claims of matching lower bounds in special cases. Second, it applies this compression framework to distributed monotone variational inequalities via QODA, an optimistic dual averaging algorithm with adaptive stepsizes, claiming O(1/sqrt(T)) restricted-gap convergence under absolute noise (Theorem 5.5), O(1/T) under relative noise with co-coercivity (Theorem 5.7), and O(1/T) under relative noise without co-coercivity but with an almost-sure boundedness assumption (Theorem 6.2). The paper also reports wall-clock speedups up to 150% for WGAN training and layer-wise compression gains on Transformer-XL.","tokens_in":58296,"tokens_out":13047,"duration_ms":131913,"significance":"The layer-wise quantization analysis in Section 5.1 is self-contained: the variance bound is proved by optimizing quantization level spacings and the code-length bound via entropy coding, with explicit comparisons to prior global-quantization bounds. These parts appear sound and are a useful contribution. If the VI results were valid, QODA would be a meaningful advance as the first distributed quantized VI solver combining optimism with layer-wise compression and avoiding the almost-sure boundedness assumption on stochastic dual vectors. However, the central convergence proof of Theorem 5.5 contains an unstated bounded-iterates assumption, and this invalidates the advertised removal of the almost-sure boundedness assumption. The main theoretical claim of the paper is therefore not established as stated.","major_comments":[{"comment":"The proof bounds E[||\\hat V_{k,t+1/2} - \\hat V_{k,t-1/2}||^2_*] by 2L^2 E[||X_{t+1/2} - X_{t-1/2}||^2] + 4\\sigma^2 and then replaces E[||X_{t+1/2} - X_{t-1/2}||^2] by D^2, where D^2 := sup_{p \\in \\mathcal X} ||X_1 - p||^2. This substitution is not justified anywhere: Algorithm 1's optimistic dual averaging iterates are unprojected, and Assumptions 2.1-2.4 impose no confinement of {X_{t+1/2}, X_{t-1/2}} to \\mathcal X. Consequently the bounds on the terms S1 and S2 in the proof of Theorem 5.5 are unsupported, and the claimed O(1/sqrt(T)) restricted-gap rate is not established. Theorem 5.7 inherits the same gap because its proof uses the S2 bound from Theorem 5.5, and Remark 5.8's claim that the almost-sure boundedness assumption is removed is therefore not justified. Repairing this would require either an explicit bounded-iterates or containment assumption, which would weaken the stated contribution, or a genuinely new argument controlling ||X_{t+1/2} - X_{t-1/2}||.","section":"Appendix E.2, Eq. (11), proof of Theorem 5.5"}],"minor_comments":[{"comment":"The proof applies Lemma E.3 to E[sup_{p \\in \\mathcal X} \\langle \\sum_{t,k} U_{k,t+1/2}, p \\rangle], but Lemma E.3 as stated is a pointwise bound for a fixed x in C. A short justification for controlling the supremum, for example via sup_{p \\in \\mathcal X} \\langle S, p \\rangle \\leq \\sup_{p \\in \\mathcal X} ||p|| \\cdot ||S||_*, would make this step complete.","section":"Appendix E.2, S3 term in Theorem 5.5"},{"comment":"The notation X_{t+1/2} is reused for the averaged iterate \\bar X_{T+1/2} in the theorem statements; the average should be defined explicitly before its first use to avoid confusion with the half-step iterates in Algorithm 1.","section":"Section 5.2, Theorems 5.5 and 5.7"},{"comment":"The restricted gap function (GAP) and Lemma E.3 require convexity of the test domain, but Theorems 5.5 and 5.7 only state that \\mathcal X is compact. The authors should either state explicitly that \\mathcal X is convex and compact or adjust the proof accordingly.","section":"Theorem 5.5 statement"}],"recommendation":"reject","confidential_remarks":null},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Punchline: the paper has a real and useful contribution in its layer-wise quantization analysis, but the main convergence claim for QODA is not supported as written. The proof of Theorem 5.5 bounds successive unprojected iterates by the diameter of the test set X, effectively swapping one boundedness assumption for another. That is a load-bearing gap, not a cosmetic one.\n\nWhat is actually new: the variance bound (Theorem 5.1) is a clean generalization of global quantization with L_q normalization, and it matches known lower bounds in the special case of M=1, L2 normalization. The code-length bound (Theorem 5.3) is also new and plausible. The idea of combining optimistic dual averaging with layer-wise compression is natural, and reducing one gradient step versus Q-GenX is a modest but real algorithmic improvement. The empirical speedups (up to 150% on WGAN training) are substantial and, while not deeply benchmarked, suggest the method has practical legs.\n\nThe soft spot: Appendix E.2, Eq. (11) uses the bound E[||X_{t+1/2} - X_{t-1/2}||^2] <= D^2, where D is the sup over p in X of ||X_1 - p||, and X is the compact test set. But ODA is unprojected: iterates are generated by line 10 and line 18 of Algorithm 1, and nothing forces them to stay inside X. The convergence theorem relies on this to keep the S2 term at O(sqrt(T)); without a proof of bounded iterates, the advertised O(1/sqrt(T)) gap bound is unsupported. The same issue carries into Theorem 5.7. This is not a minor technical annoyance. The paper's headline contribution is that QODA removes the almost sure boundedness assumption on the stochastic dual vectors; this proof replaces it with an unstated boundedness assumption on the iterates themselves, which is generally no easier to guarantee.\n\nI checked whether Theorem 6.2 (relative noise with the Alt schedule) has the same problem. It appears to use a different argument, controlling the path length via Lemma F.12 rather than the diameter of X, so that part may survive. But the Section 5.2 claims, which are the main advertised results, are compromised.\n\nThe paper deserves a serious referee because the layer-wise quantization bounds are independently valuable and the flaw is patchable. A revision that either states the bounded-iterates assumption explicitly and owns the extra condition, or proves a bound on the iterates from the algorithm's dynamics, could turn this into a solid paper. As it stands, the central convergence theorem should not be accepted without major changes.\n\nRecommendation: send to peer review with a clear request to fix the bounded-iterates gap. The referee should focus on the proof of Theorem 5.5 and not get distracted by the empirical section.","headline":"The layer-wise quantization theory is solid and worth engaging, but the headline QODA convergence theorem leans on an unstated bounded-iterates assumption, so the claimed removal of a.s. boundedness does not go through as written.","tokens_in":58853,"tokens_out":3323,"would_cite":false,"duration_ms":35871,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Per-layer adaptive quantization can solve distributed monotone variational inequalities at the same asymptotic rates as uncompressed methods while dropping a common boundedness assumption.","keywords":["layer-wise quantization","optimistic dual averaging","variational inequalities","distributed optimization","adaptive quantization","communication-efficient training","GAN training","convergence rates"],"falsifier":"Run QODA on a monotone bilinear game with an unbounded domain and check whether $\\mathbb{E}\\|X_{t+1/2}-X_{t-1/2}\\|^2$ stays bounded by $D^2$; if it grows with $T$ while the empirical gap still decays, the proof's hidden boundedness premise fails even if the advertised rate is observed.","tokens_in":57842,"feed_emoji":"⚖️","tokens_out":13125,"duration_ms":148703,"temperature":0.7,"pith_summary":"The paper claims that communication-efficient training can be made layer-aware: instead of quantizing all coordinates with one global level sequence, it assigns each layer its own adaptive quantization sequence chosen to minimize expected quantization variance, and it proves bounds on the induced variance and transmitted bits. It embeds this layer-wise compressor in an optimistic dual averaging loop for distributed monotone variational inequalities, the equilibrium formulation behind minimax problems such as GAN training. The central claim is that the resulting algorithm, QODA, converges in the restricted gap function at rate $O(1/\\sqrt{T})$ under absolute noise and $O(1/T)$ under relative noise, without the almost sure boundedness of stochastic dual vectors that earlier distributed VI solvers required. If correct, distributed training of adversarial models can quantize per layer and still match uncompressed convergence, with faster wall-clock time in bandwidth-limited settings.","feed_headline":"Distributed game solver drops bounded-noise assumption, keeps rates","feed_subtitle":"Layer-wise quantization with optimism matches uncompressed convergence and speeds GAN training up to 150%.","key_machinery":"The load-bearing object is the layer-wise quantizer $Q_{L_M}(v)$, which normalizes a vector by its $L_q$ norm, maps each coordinate to one of $M$ type-specific sequences of quantization levels, and chooses those sequences by minimizing the expected quantization variance (MQV) from estimated marginal distributions. A companion coding protocol encodes the norm, signs, and level indices with per-type prefix codes, giving expected code length bounded by a weighted entropy expression. The quantizer feeds an optimistic dual averaging update, $X_{t+1/2}=X_t-\\gamma_t \\frac{1}{K}\\sum_k \\hat V_{k,t-1/2}$ and $Y_{t+1}=Y_t-\\frac{1}{K}\\sum_k \\hat V_{k,t+1/2}$, where the same compressed vector is stored and reused for the next extrapolation; this is what halves the number of transmitted vectors relative to extra-gradient methods. The adaptive step sizes $\\eta_t=\\gamma_t=(1+\\sum_{s<t}\\frac{1}{K^2}\\sum_k\\|\\hat V_{k,s+1/2}-\\hat V_{k,s-1/2}\\|_*^2)^{-1/2}$ are what let the proof telescope the error and control cumulative quantization noise through $\\varepsilon_Q$.","core_discovery":"The core discovery, stated on the paper's own terms, is that per-layer adaptive quantization does not cost asymptotic convergence. For a monotone $L$-Lipschitz operator, $K$ workers, and a compact test domain, QODA is claimed to achieve restricted-gap error $O(((LD+\\|A(X_1)\\|+\\sigma)c_{\\varepsilon_Q}+\\sigma)D^2 L^2/\\sqrt{T K})$ under absolute noise and $O((\\sigma_R\\varepsilon_Q+\\varepsilon_Q+\\sigma_R)D^2/(T K))$ under relative noise, where $\\varepsilon_Q$ is the average per-layer quantization variance bound. The absolute-noise rate needs no co-coercivity and matches the known lower bound for distributed stochastic convex optimization; the relative-noise rate requires co-coercivity in the main theorem. Both rates match the global-quantization baseline Q-GenX while removing its almost sure boundedness assumption, and the optimistic update reuses the previous compressed dual vector so only one quantized vector is broadcast per iteration.","pith_inferences":["The variance-minimization principle suggests that optimal level sequences should mirror the drift of each layer's marginal distribution of normalized coordinates; measuring that drift would give a principled replacement for the fixed 10k-step level-update cadence used in the experiments.","The same layer-wise compressor should transfer to weakly Minty or non-monotone operators, and to adjacent communication bottlenecks such as adversarial training and robust reinforcement learning, though the paper only proves monotone guarantees.","The reported speedups (1.28x-2.5x depending on bandwidth and node count) were measured on a 5 Gbps inter-node link; as bandwidth rises toward memory speed, the wall-clock benefit of quantized communication should shrink, making the method most attractive for bandwidth-limited clusters."],"forward_implications":["Layer-wise quantization never increases the expected variance relative to the best single global level sequence, so adapting levels per layer can only improve the accuracy of compressed communication.","Because the optimistic update reuses the previous compressed dual vector, QODA transmits one quantized vector per iteration instead of the two required by extra-gradient VI solvers, halving communication load.","Under absolute noise the restricted gap converges at $O(1/\\sqrt{T K})$ with $K$ workers, matching the known distributed convex-optimization lower bound; under relative noise it converges at $O(1/T)$, matching the best global-quantization baseline.","These rates are obtained without the almost sure boundedness of stochastic dual vectors, the assumption that previous distributed VI analyses (including Q-GenX) required.","Empirically, layer-wise QODA shortens end-to-end WGAN training time by up to 150% on 12+ GPUs, and layer-wise quantization improves Transformer-XL compression rates over global quantization at matched perplexity."],"supporting_citations":[{"why":"Supplies the QSGD unbiased quantization and coding scheme whose global variance and code-length results this work generalizes to layer-wise settings.","marker":"Alistarh et al., 2017"},{"why":"Q-GenX, the global-quantization extra-gradient VI baseline whose rates QODA matches, whose communication it halves, and whose almost sure boundedness assumption it removes.","marker":"Ramezani-Kebrya et al., 2023"},{"why":"L-GreCo, the practical layer-wise adaptive compression and dynamic-programming level selector used in the GAN and Transformer-XL experiments.","marker":"Markov et al., 2024"},{"why":"Provides the adaptive gradient quantization framework and distribution-estimation technique used for updating quantization levels over training.","marker":"Faghri et al., 2020"},{"why":"Supplies the martingale bound used to control absolute noise in the proof of the $O(1/\\sqrt{T})$ gap bound.","marker":"Bach & Levy, 2019"},{"why":"Provides the learning-rate-separation trick and auxiliary lemmas used in the alternative step-size analysis of Section 6.","marker":"Hsieh et al., 2022"},{"why":"Gives the $\\Omega(1/\\sqrt{T K})$ lower bound for distributed stochastic convex optimization that the absolute-noise rate is said to match.","marker":"Woodworth et al., 2021"},{"why":"NUQSGD; supplies the variance lower bound that the layer-wise variance bound matches in the special case of global L2 quantization.","marker":"Ramezani-Kebrya et al., 2021"},{"why":"Communication-complexity lower bound used to claim the code-length bound is optimal in the problem dimension.","marker":"Tsitsiklis & Luo, 1987"},{"why":"Communication lower bound for distributed optimization, paired with Tsitsiklis-Luo, used to establish dimension-optimality of the code-length bound.","marker":"Korhonen & Alistarh, 2021"}],"fun_headline_variants":[],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the squared distance between successive extrapolated update points never exceeds the squared diameter $D^2$ of a fixed compact test set, even though the iterates are never projected back into that set.","fun_headline_variants_meta":{"error":"Client error '402 Payment Required' for url 'https://api.deepseek.com/chat/completions'\nFor more information check: https://developer.mozilla.org/en-US/docs/Web/HTTP/Status/402"},"cache_creation_input_tokens":0},"created_at":"2026-08-07T15:35:19.279956+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run QODA on a monotone bilinear game with an unbounded domain and check whether $\\mathbb{E}\\|X_{t+1/2}-X_{t-1/2}\\|^2$ stays bounded by $D^2$; if it grows with $T$ while the empirical gap still decays, the proof's hidden boundedness premise fails even if the advertised rate is observed.","supporting_citations":[{"cited_title":"Distributed extra-gradient with optimal complexity and communication guarantees","cited_arxiv_id":null,"evidence_quote":"Q-GenX, the global-quantization extra-gradient VI baseline whose rates QODA matches, whose communication it halves, and whose almost sure boundedness assumption it removes."},{"cited_title":"L-greco: Layerwise-adaptive gradient compression for efficient data-parallel deep learning","cited_arxiv_id":null,"evidence_quote":"L-GreCo, the practical layer-wise adaptive compression and dynamic-programming level selector used in the GAN and Transformer-XL experiments."},{"cited_title":"M., and Ramezani-Kebrya, A","cited_arxiv_id":null,"evidence_quote":"Provides the adaptive gradient quantization framework and distribution-estimation technique used for updating quantization levels over training."},{"cited_title":"No-regret learning in games with noisy feedback: Faster rates and adaptivity via learning rate separation","cited_arxiv_id":null,"evidence_quote":"Provides the learning-rate-separation trick and auxiliary lemmas used in the alternative step-size analysis of Section 6."},{"cited_title":"E., Bullins, B., Shamir, O., and Srebro, N","cited_arxiv_id":null,"evidence_quote":"Gives the $\\Omega(1/\\sqrt{T K})$ lower bound for distributed stochastic convex optimization that the absolute-noise rate is said to match."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"NUQSGD; supplies the variance lower bound that the layer-wise variance bound matches in the special case of global L2 quantization."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Communication-complexity lower bound used to claim the code-length bound is optimal in the problem dimension."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Communication lower bound for distributed optimization, paired with Tsitsiklis-Luo, used to establish dimension-optimality of the code-length bound."}],"review_version":1}