{"id":"b406cb91-8dbf-4cf0-8418-ede06c638679","arxiv_id":"2412.14935","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"MARINA, a compression-based distributed method, is adapted to cocoercive strongly monotone variational inequalities and proven to converge linearly with a communication complexity of O((1+δ(ℓ/µ)(1+α/n)) log(1/ε)).","lead":"A distributed optimization algorithm for variational inequalities that compresses the information devices send to a server is shown to converge linearly for cocoercive strongly monotone problems. The paper extends the MARINA compression technique, known from minimization, to variational inequalities and proves a communication complexity matching existing methods like DIANA.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Corollary 1.1's communication bound counts only uplink, omitting full-vector downlink broadcasts; true per-device cost is O((1+δ)(ℓ/µ)(1+α/n) log(1/ε)), so the compression advantage is overstated.","rationale":"The paper's proof of Theorem 1 is mathematically sound: Lemma 1 correctly uses per-device cocoercivity, strong monotonicity, and unbiased compression to obtain a contraction on E||g_k||²; Lemma 2's telescoping argument and the final combination with γ = 1/(8ℓ(1+α/n)) and K = 30ℓ(1+α/n)/µ check out. The central convergence claim is valid under the stated assumptions. However, the advertised communication complexity in Corollary 1.1 is incomplete. The algorithm broadcasts a full vector g_{k-1} to every device at each inner iteration, and this downlink cost is not counted in the stated O((1+δ(ℓ/µ)(1+α/n)) log(1/ε)) bound. When downlink is included, the per-device cost becomes O((1+δ)(ℓ/µ)(1+α/n) log(1/ε)), which is strictly worse for all δ < 1 and eliminates the claimed near-constant communication when δ is small. The reader identified this as a weakness but selected Assumption 1 as the 'weakest assumption.' I argue the downlink omission is more load-bearing because it is an internal accounting error directly tied to the paper's central communication-efficiency contribution, whereas Assumption 1 is a strong but explicitly stated modeling condition. Since the convergence theorem is correct and the communication bound is fixable, the existing CONDITIONAL verdict is appropriate; my concern does not change the verdict.","tokens_in":15393,"tokens_out":19646,"duration_ms":124269,"concrete_test":"Recount the total per-device communication of Algorithm 1 including line 7's full-vector broadcasts. For δ = 0.1 and ℓ/µ = 100, compare the stated per-epoch factor 1 + δ(ℓ/µ)(1+α/n) ≈ 11 with the corrected factor (1+δ)(ℓ/µ)(1+α/n) ≈ 121 when α/n = 0.1; if the corrected factor is more than 5x larger, the communication complexity claim is materially overstated.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Algorithm 1 (line 7) requires the server to send the full uncompressed vector g_{k-1} to every device at each inner iteration k=1,...,K-1. Corollary 1.1 counts only per-device uplinks: one full vector per epoch (for F_i(z_0)) plus (K-1) compressed vectors of size δ. Including the downlink, total per-device transmissions per epoch are 1 + δ(K-1) + (K-1) = K + δ(K-1). With K = 30ℓ(1+α/n)/µ, this gives O((1+δ)(ℓ/µ)(1+α/n) log(1/ε)) gradient transmissions per device, not O((1+δ(ℓ/µ)(1+α/n)) log(1/ε)) as claimed. For small δ, the stated bound suggests near-constant per-epoch cost, but the full downlink makes the cost proportional to ℓ/µ regardless of δ. The convergence theorem (Theorem 1) remains correct; the issue is that the paper's central communication-efficiency claim is quantitatively overstated.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies distributed variational inequalities of the form F(z) = (1/n) \\sum_i F_i(z) = 0 under per-operator cocoercivity and aggregate strong monotonicity. It proposes Algorithm 1, a MARINA-type method that periodically recomputes the full operator and otherwise communicates compressed differences F_i(z_k) - F_i(z_{k-1}). The main result (Theorem 1) gives a contraction E||F(\\tilde z_s)||^2 <= (1/2) E||F(\\tilde z_{s-1})||^2 for a fixed step size and epoch length; Corollary 1.1 translates this into a communication complexity. Experiments on a bilinear saddle-point problem compare compressed and uncompressed variants.","tokens_in":15572,"tokens_out":10275,"duration_ms":82085,"significance":"Under the stated assumptions, the convergence proof is coherent and the constants are explicit; I verified the key steps in Lemmas 1 and 2, including the variance bound for unbiased compressors, the use of cocoercivity and strong monotonicity, and the telescoping arguments. The method is a sensible extension of MARINA to cocoercive variational inequalities and would be a useful contribution if the communication claim is stated accurately. The main weakness is the communication accounting in Corollary 1.1; the convergence theorem itself is not affected.","major_comments":[{"comment":"The communication count in Corollary 1.1 counts only uplink transmissions. Algorithm 1, line 7 requires the server to broadcast the full uncompressed vector g_{k-1} to every device in each of the K-1 inner iterations. Counting both directions per device gives S(1 + \\delta(K-1) + (K-1)) = O((1+\\delta)(\\ell/\\mu)(1+\\alpha/n) \\log(1/\\varepsilon)) gradient transmissions per device, not the stated O((1+\\delta(\\ell/\\mu)(1+\\alpha/n)) \\log(1/\\varepsilon)). For small \\delta, the advertised compression saving disappears. Because the paper's headline contribution is communication efficiency, the statement of Corollary 1.1 and the surrounding discussion must be revised, or the algorithm must be modified to avoid full-vector downlink.","section":"Corollary 1.1 (proof) and Algorithm 1, line 7"},{"comment":"The proof of Lemma 1 uses per-device \\ell-cocoercivity to control the variance term (\\alpha/n^2) \\sum_i ||F_i(z_k) - F_i(z_{k-1})||^2. In federated settings it is often realistic that only the aggregate operator F is cocoercive while individual local operators are not. The paper should explicitly state this restriction and discuss whether the analysis can be relaxed to aggregate cocoercivity; as written, the linear convergence guarantee depends critically on Assumption 1 holding for every device.","section":"Assumption 1 and Lemma 1"}],"minor_comments":[{"comment":"The epoch length K is written as a real number 30\\ell(1+\\alpha/n)/\\mu, although it is used as a number of iterations; a ceiling should be taken, with a remark that the constants are unchanged up to rounding.","section":"Theorem 1 and Algorithm 1"},{"comment":"Assumption 4, which says that the compressor 'leaves a fraction \\delta of information', is informal. The bit-counting in Corollary 1.1 is only exact for coordinate-sampling compressors; for quantization, the relation between \\delta and the transmitted bits should be specified.","section":"Assumption 4 and Corollary 1.1"},{"comment":"The experiments do not report the exact \\delta used for quantization, nor do they use the theoretical step size and epoch length from Theorem 1, so they should be described as an empirical illustration rather than a validation of the theorem's constants.","section":"Section 6"},{"comment":"The citation 'Medyakov et al.' in Section 2.2 appears without a year or venue; it should be completed or removed.","section":"References"}],"recommendation":"major_revision","confidential_remarks":"The convergence analysis appears sound and self-contained, and the paper is a reasonable extension of MARINA to cocoercive variational inequalities. However, the central communication-efficiency claim is overstated because it ignores the full-vector downlink broadcasts required by Algorithm 1. The authors should correct Corollary 1.1 and either adjust the algorithm or carefully state the accounting convention (e.g., uplink-only). The per-device cocoercivity assumption also deserves a more prominent discussion."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: the paper is a competent, correct adaptation of MARINA with deterministic epoch restarts to cocoercive strongly monotone variational inequalities. The convergence analysis is self-contained, the constants in Theorem 1 are explicit, and the two lemmas check out: the variance decomposition uses unbiasedness correctly, and the telescoping in Lemma 2 is valid. I verified the key steps. That is real value, but the headline communication complexity is overstated. Corollary 1.1 counts only device uploads. Algorithm 1 line 7 sends the full vector g_{k-1} to every device every inner iteration, so over one epoch a device receives K-1 full downlinks. True per-device cost is O((1+δ)(ℓ/µ)(1+α/n) log(1/ε)) — the downlink alone already gives the ℓ/µ factor, independent of δ. The stress-test note is right. This does not break Theorem 1, but it weakens the central selling point.\n\nMinor issues: the integer rounding of the epoch length K is not discussed in the corollary, though taking a ceiling only shifts constants. More substantively, Assumption 1 requires every local F_i to be ℓ-cocoercive; the proof needs this device-by-device, and in federated settings the aggregate operator can be cocoercive while individual local operators are not. That fragility is worth stating.\n\nExperiments use int8 quantization without saying whether rounding is stochastic/unbiased; nearest-neighbor rounding is biased and sits outside the theory. There are also no error bars and no DIANA baseline, which is the natural comparator. These are fixable.\n\nThe authors themselves note that DIANA already attains the same rate, so the incremental contribution is modest. But the analysis is new, the comparison is honest, and the core proof is solid. This paper is for readers working on compressed distributed VIs who want a MARINA-style analysis under cocoercivity. It deserves a serious referee, but the referee should require a corrected communication count and a clarified experimental setup before acceptance.","headline":"Solid but narrow: a correct MARINA-for-cocoercive-VI analysis with an overstated communication bound and experiments that do not match the theory.","tokens_in":16127,"tokens_out":1707,"would_cite":true,"duration_ms":15761,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C33","68W15","90C25"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper shows that a MARINA-style compressed update converges linearly for cocoercive strongly monotone variational inequalities, halving the expected squared operator norm every epoch while transmitting only compressed gradient…","keywords":["variational inequalities","cocoercive operators","strongly monotone operators","distributed optimization","gradient compression","MARINA","linear convergence","communication complexity"],"falsifier":"Run Algorithm 1 on a two-device problem where the aggregate operator $F=(F_1+F_2)/2$ is strongly monotone and cocoercive but $F_1$ is not cocoercive, using $\\gamma = 1/(8\\ell(1+\\alpha/n))$ and $K = 30\\ell(1+\\alpha/n)/\\mu$, and check whether $\\mathbb{E}\\|F(\\tilde z_s)\\|^2$ halves each epoch. If the contraction fails, the per-device cocoercivity assumption is doing real work rather than being a technical convenience.","tokens_in":15164,"feed_emoji":"📡","tokens_out":14753,"duration_ms":83050,"temperature":0.7,"pith_summary":"The paper targets variational inequalities solved across many devices, where the per-device cost of sending full operator evaluations dominates training. It adapts the MARINA compression technique from minimization to cocoercive strongly monotone variational inequalities, letting each device transmit a compressed difference of local operators instead of the full operator. The central result is linear convergence: with step size $\\gamma = 1/(8\\ell(1+\\alpha/n))$ and epoch length $K = 30\\ell(1+\\alpha/n)/\\mu$, each epoch halves the expected squared norm of the aggregate operator, so reaching $\\varepsilon$-accuracy costs $O((1+\\delta(\\ell/\\mu)(1+\\alpha/n))\\log(\\|F(z_0)\\|^2/\\varepsilon^2))$ compressed transmissions per device. If correct, this shows compression need not slow the convergence rate for this problem class, giving a practical way to cut communication in distributed saddle-point and game-theoretic training.","feed_headline":"Compressed solver for variational inequalities converges linearly","feed_subtitle":"Each device sends only compressed gradient differences, yet the squared operator error halves every epoch.","key_machinery":"The engine of the method is the recursive estimator $g_k^i = g_{k-1} + C(F_i(z_k) - F_i(z_{k-1}))$ maintained on each device, averaged by the server into $g_k$ and used in the step $z_{k+1} = z_k - \\gamma g_k$. Unbiasedness of the compressor $C$ makes the compression noise mean-zero, and the per-device cocoercivity inequality $\\|F_i(u)-F_i(v)\\|^2 \\le \\ell\\langle F_i(u)-F_i(v), u-v\\rangle$ converts the accumulated variance into a contraction of $\\mathbb{E}\\|g_k\\|^2$; strong monotonicity of $F$ supplies the $\\mu$-dependent rate. Lemma 1 controls the contraction of the compressed estimator, Lemma 2 bounds the gap between $F(z_K)$ and $g_K$, and their combination yields the factor-$1/2$ shrinkage per epoch that is Theorem 1.","core_discovery":"The paper claims that Algorithm 1, a MARINA-type method for distributed variational inequalities, achieves linear convergence under per-device cocoercivity, strong monotonicity of the aggregate operator, and unbiased compression. Concretely, Theorem 1 states that with $\\gamma = 1/(8\\ell(1+\\alpha/n))$ and $K = 30\\ell(1+\\alpha/n)/\\mu$, one epoch satisfies $\\mathbb{E}\\|F(\\tilde z_s)\\|^2 \\le \\frac12 \\mathbb{E}\\|F(\\tilde z_{s-1})\\|^2$, where $\\tilde z_s$ is the epoch output and $F$ is the average of the local operators. Corollary 1.1 converts this into a per-device communication complexity of $O((1+\\delta(\\ell/\\mu)(1+\\alpha/n))\\log(\\|F(z_0)\\|^2/\\varepsilon^2))$ gradient transmissions, where $\\delta$ is the fraction of information kept by the compressor. The experiments on a bilinear saddle-point problem illustrate that compressed variants reach the same accuracy with substantially fewer transmitted kilobits.","pith_inferences":["Beyond the paper: the theoretical guarantee does not cover the common federated setting where only the average operator is cocoercive, because the proof's variance control is per-device; whether the method still converges linearly there is an open empirical question.","Beyond the paper: biased compressors with error feedback are a natural next step, but the proof's cancellation of compression noise relies essentially on unbiasedness, so such an extension would need new machinery.","Beyond the paper: the epoch length $K$ grows linearly with $\\ell/\\mu$ times $(1+\\alpha/n)$, so for ill-conditioned problems the periodic transmission of the full operator becomes more expensive; the paper's high-condition-number experiments ($\\ell\\approx10^4$) show slower progress in transmitted kilobits, which is consistent with that dependence."],"forward_implications":["One epoch of Algorithm 1 reduces $\\mathbb{E}\\|F(\\tilde z_s)\\|^2$ by a factor of $1/2$, so the number of epochs to reach $\\varepsilon^2$-accuracy is $O(\\log(\\|F(z_0)\\|^2/\\varepsilon^2))$.","Per device, the number of transmitted gradient vectors is $O((1+\\delta(\\ell/\\mu)(1+\\alpha/n))\\log(\\|F(z_0)\\|^2/\\varepsilon^2))$, so smaller compression ratios $\\delta$ directly lower communication.","With $\\delta \\le 1/\\alpha$ and $\\alpha = n$, the bound becomes $O((1+\\ell/(\\mu n))\\log(1/\\varepsilon))$, the same communication complexity as the DIANA-based analysis for cocoercive VIs.","In the paper's saddle-point experiments, both coordinate-drop and int8-quantized MARINA reach the same accuracy as uncompressed MARINA while transmitting far fewer kilobits per device."],"supporting_citations":[{"why":"Supplies the MARINA algorithm and its unbiased-compression recursive estimator, which Algorithm 1 adapts from minimization to variational inequalities.","marker":"[Gorbunov et al., 2021]"},{"why":"Defines the cocoercivity assumption used throughout and discusses its relation to Lipschitzness of operators.","marker":"[Loizou et al., 2021]"},{"why":"Provides the SARAH-based variance-reduced method for cocoercive variational inequalities that the paper treats as the closest precedent to extend with compression.","marker":"[Beznosikov and Gasnikov, 2023]"},{"why":"Gives a unified analysis of stochastic VI methods with compression and the DIANA communication bound that Remark 1 compares with the paper's guarantee.","marker":"[Beznosikov et al., 2023a]"},{"why":"Introduces the general unbiased compressor definition (Assumption 3) and the quantization framework used in the experiments.","marker":"[Alistarh et al., 2017]"}],"fun_headline_variants":["Compressed distributed VI method converges linearly","Linear convergence via compressed distributed VI solver","MARINA-style compression gives linear convergence for VIs","Compressed VI solver converges linearly with fewer bits"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that every device's local operator satisfies the per-operator cocoercivity inequality; if even one local operator violates it, the proof's variance control in Lemma 1 fails, and the linear-convergence guarantee of Theorem 1 is not established.","fun_headline_variants_meta":{"raw":{"variants":["Compressed distributed VI method converges linearly","Linear convergence via compressed distributed VI solver","MARINA-style compression gives linear convergence for VIs","Compressed VI solver converges linearly with fewer bits"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000996,"raw_usage":{"total_tokens":4219,"prompt_tokens":944,"completion_tokens":3275,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":560,"completion_tokens_details":{"reasoning_tokens":3219}},"tokens_in":560,"tokens_out":3275,"duration_ms":17395,"temperature":1.0,"reasoning_tokens":3219,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T11:48:38.266397+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run Algorithm 1 on a two-device problem where the aggregate operator $F=(F_1+F_2)/2$ is strongly monotone and cocoercive but $F_1$ is not cocoercive, using $\\gamma = 1/(8\\ell(1+\\alpha/n))$ and $K = 30\\ell(1+\\alpha/n)/\\mu$, and check whether $\\mathbb{E}\\|F(\\tilde z_s)\\|^2$ halves each epoch. If the contraction fails, the per-device cocoercivity assumption is doing real work rather than being a technical convenience.","supporting_citations":[{"cited_title":"Stochastic gradient descent-ascent and consensus optimization for smooth games: Convergence analysis under expected co-coercivity","cited_arxiv_id":null,"evidence_quote":"Defines the cocoercivity assumption used throughout and discusses its relation to Lipschitzness of operators."}],"review_version":1}