{"id":"71cb863c-ae6f-4ee7-9789-b4aa284a757b","arxiv_id":"2501.11267","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"FedQVR matches the O(1/ε) communication complexity of SCAFFOLD while using quantized uplink updates and heterogeneous local steps, with an enhanced version for radio resource allocation.","lead":"FedQVR is a federated learning algorithm that combines SCAFFOLD-style variance reduction with quantized uplink updates and heterogeneous local steps, aiming to cut communication costs in wireless edge networks. The paper provides a non-convex convergence bound and experiments on CIFAR-10 and MNIST, with an extension FedQVR-E that jointly allocates bandwidth and quantization bits.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The proof of Theorem 1 telescopes a potential with r-dependent coefficient C_0^r but treats it as constant; the omitted term (C_0^{r+1}-C_0^r)∑p_iΞ_i^{r+1} is uncontrolled, so the central convergence bound does not follow.","rationale":"The reader's conditional verdict focused on Eq. (17), which is a real issue, but the proof's potential-function telescoping is a more fundamental defect: it is an internal inconsistency in the main theorem's derivation, not merely an unverified supporting formula. The convergence bound (24) and Corollaries 1-2 all rest on this telescoping. If the potential coefficients are time-varying, the standard argument must be replaced by one that handles the extra term or uses a uniform constant; neither is present in the paper. This warrants moving from CONDITIONAL to UNVERDICTED, since the central claim is not established as written even under Assumptions 1-3. The concern is concrete and testable: one can directly check whether the omitted term is controlled on the actual experimental trajectory or by the stated parameter conditions.","tokens_in":44844,"tokens_out":23165,"duration_ms":200794,"concrete_test":"Analytically re-derive the potential step with C_0^r kept time-varying: express P^{r+1}-P^r as A_r + (C_0^{r+1}-C_0^r)∑p_iΞ_i^{r+1} and check whether the extra term can be bounded or is non-positive. Numerically, compute C_0^r from (62) for consecutive rounds using \\bar{ω}^r values from a CIFAR-10 run with B=2 and a=0.3; if the extra term is positive and not dominated by the negative terms in A_r, the telescoping bound fails, and Theorem 1 would need a constant C_0 built from max_r \\bar{ω}^r, which strengthens the parameter conditions and may slow the claimed rate.","verdict_should_be":"UNVERDICTED","load_bearing_attack":"The central claim is Theorem 1's bound (24). In the supplementary proof (Section IX-C), the potential is defined as P^r = E[f(θ^r)] + C_0^r ∑_i p_i Ξ_i^r. The inequality just above this definition bounds A_r := E[f(θ^{r+1})-f(θ^r)] + C_0^r ∑ p_i(Ξ_i^{r+1}-Ξ_i^r). But P^{r+1}-P^r = A_r + (C_0^{r+1}-C_0^r)∑p_iΞ_i^{r+1}. The proof then writes P^{r+1}-P^r ≤ RHS_r without addressing the extra term. C_0^r depends on r through \\bar{ω}^r = max_i ω_i^r (Eqs. 62-65), and the theorem explicitly allows \\bar{ω}^r to vary across rounds, with (24) summing r-dependent \\bar{ω}^r terms. Unless the extra term is shown non-positive or absorbed by RHS_r, the telescoping sum ∑(P^r-P^{r+1}) = P^0-P^R is not bounded by the summed RHS_r, so (24) is unproven. This internal gap is independent of the quantization variance formula (17), though both undermine the theorem.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes FedQVR, a federated learning algorithm that combines control-variate-based inter-device variance reduction with stochastic uplink quantization and time-varying heterogeneous local updates. The main theoretical claim is Theorem 1: under smoothness and bounded stochastic gradient variance, and with a quantization variance coefficient ω_i^r satisfying Assumption 3, FedQVR converges at rate O(1/R + σ²/√R) and achieves O(1/ε) communication complexity. A second algorithm, FedQVR-E, adds joint bandwidth and quantization-bit allocation under per-round delay constraints in an FDMA system. The authors support the claims with a supplementary proof of Theorem 1 and with experiments on MNIST and CIFAR-10 comparing against FedAvg, SCAFFOLD, FedDyn, FEDADAM, FedPAQ, FedCOMGATE, and FedCAMS, including a communication-cost comparison table.","tokens_in":45128,"tokens_out":8047,"duration_ms":78754,"significance":"If the central convergence and communication-complexity claims were established, the paper would be significant: it would demonstrate that quantized uplink transmission can be combined with variance reduction without doubling per-round communication, and that the convergence bound can be made independent of explicit device-heterogeneity terms. The paper also provides a structured supplementary proof and a broad experimental comparison with communication-cost accounting, which are useful strengths. However, the proof of Theorem 1 contains a gap in the potential-function argument, and the stated quantization coefficient in Eq. (17) is dimensionally inconsistent; these issues are load-bearing because the convergence conditions and the heterogeneity-robustness interpretation rely on them. The FedQVR-E algorithm also has an aggregation inconsistency after device removal. The paper is not acceptable in its current form, but the claims are of the type that could be repaired with a corrected proof and consistency fixes.","major_comments":[{"comment":"The proof of Theorem 1 defines the potential P^r = E[f(θ^r)] + C_0^r Σ_i p_i Ξ_i^r with a round-dependent coefficient C_0^r, but the bound displayed as Eq. (57) does not actually bound P^{r+1} - P^r. The quantities being combined in Eqs. (51)-(54) give E[f(θ^{r+1}) - f(θ^r)] + C_0^r Σ_i p_i (Ξ_i^{r+1} - Ξ_i^r), whereas P^{r+1} - P^r contains the additional term (C_0^{r+1} - C_0^r) Σ_i p_i Ξ_i^{r+1}. The proof never shows that this extra term is non-positive or that it is absorbed into the RHS_r terms. Since C_0^r depends on r through \\bar{ω}^r in Eqs. (62)-(65), and Theorem 1 explicitly allows \\bar{ω}^r to vary across rounds, the telescoping sum Σ_{r=0}^{R-1} (P^r - P^{r+1}) = P^0 - P^R that leads to Eqs. (70)-(72) is not justified. This is a direct gap in the proof of the central bound (24).","section":null},{"comment":"The explicit formula for ω_i^r in Eq. (17) is dimensionally inconsistent. The numerator Σ_{j=1}^d (max_k{[z_i^r]_k} - min_k{[z_i^r]_k}) has the units of z (one power of the parameter scale), while the denominator 4(2^{B_i^r}-1)‖z_i^r‖² has units of z², so the claimed ω_i^r has units of 1/z. But Assumption 3 in Eq. (16) requires ω_i^r to be dimensionless because it multiplies E‖θ_i^{r+1}-θ_0^r‖² on both sides. The standard bound for this stochastic quantizer is instead of the form (Σ_j (range_j)²)/( (2^B-1)² ‖z‖² ) or d‖z‖²/(2^B-1)². As written, Eq. (17) cannot be used to determine the admissible interval 0 < a < min{1/ω_i^r, 1}, nor the round-dependent constants \\bar{ω}^r appearing in the theorem conditions (22)-(23) and in Remark 2. This directly affects the validity of Assumption 3 and the parameter region in which Theorem 1 is claimed.","section":null},{"comment":"The FedQVR-E aggregation is inconsistent after the device-removal step. Line 5 removes from A_r all devices whose allocated quantization bits fall below B, but line 12 still updates θ^{r+1} = θ_0^r + (N/m) Σ_{i∈A_r} p_i Δ_i^{r+1} with the original m, even though |A_r| is now smaller. The update is then not a normalized aggregation over the actually transmitted updates, and the unbiasedness property used in the proof of Lemma 7 no longer holds. In addition, line 11 writes c^{r+1} = c^r - (1/N) Σ_{i∈A_r} a p_i/(η \\tilde{E}_i^r) Δ_i^{r+1}, which differs from Eq. (11) by the extra factor 1/N and is not consistent with the identity c^r = Σ_i p_i c_i^r used throughout the analysis. No convergence analysis is provided for the device-removal procedure, so the claim that FedQVR-E 'enhances the convergence of FedQVR' is not supported by the theory.","section":null},{"comment":"The parameter conditions in Theorem 1 do not match those used in the proof. The first bound on η in Theorem 1, Eq. (22), is 1/(2γ\\bar{E}^r√{N(1+\\bar{ω}^r)}), while the corresponding condition in Lemma 8, Eq. (66), is 1/(2γ\\bar{E}^r√{N p(1+\\bar{ω}^r)}) with p = max_i p_i. Unless p = 1, the theorem's stated condition is weaker than the proof requires, so the proof does not establish Theorem 1 for the stated parameter region. The notation for \\bar{E}^r also differs: Theorem 1 defines it as a per-round maximum over devices, while the proof of Lemma 8 needs a uniform bound over rounds. These are not merely cosmetic issues because they determine the admissible stepsize region on which Corollaries 1 and 2 rely.","section":null}],"minor_comments":[{"comment":"Theorem 1 states that it holds under Assumptions 1 and 2, but the proof and the condition 0 < a < min{1/\\bar{ω}^r, 1} also rely on Assumption 3 (the quantization variance bound), which should be listed explicitly in the theorem statement.","section":null},{"comment":"The last two sums in Eq. (24) run over i = 0 instead of i = 1, and the definition of P^0 contains garbled notation ('C^0_0 N pi') and uses x_0 where θ_0 is used elsewhere; these need correction.","section":null},{"comment":"The lemma and corollary numbering is inconsistent: the main text refers to Lemma 1 and Lemma 2, then to 'Lemma 3' in the discussion of Eq. (31); the supplementary proof of Lemma 1 is labeled Lemma 3, and Corollary 2 in the main text is proved as Corollary 3 in Section X. The algorithm references in Section IV-A also point to 'Algorithm 2' when Algorithm 1 is meant.","section":null},{"comment":"The experimental figures report single curves without error bars, confidence intervals, or number of seeds. Given the stochastic quantization, random device sampling, and the text's claims about 'smoother convergence' and stability, the reported differences should be supported by multiple independent runs.","section":null},{"comment":"In the quantization rule, the probabilities are written with absolute values but the boundaries c_k are defined on the interval [z, z]; the notation should clarify how negative entries are handled, since the formula currently mixes sign([z]_i) with sub-intervals that may contain both signs.","section":null}],"recommendation":"major_revision","confidential_remarks":"For the editor: the paper's main selling point is Theorem 1 and the resulting O(1/ε) communication complexity. The potential-function gap in Section IX-C is not a cosmetic issue; it means the central bound is currently unproven as written. The dimensional inconsistency in Eq. (17) and the mismatch between Eq. (22) and Eq. (66) suggest that the supplementary proof and the theorem statement have not been carefully cross-checked. The FedQVR-E aggregation bug further weakens the second contribution. I would not recommend acceptance until these points are resolved, but the overall framework is plausible and the experimental comparison is extensive, so a carefully revised version could be suitable for reconsideration."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You should know this paper's main selling point is a convergence bound for a quantized, variance-reduced FL algorithm that handles both data and system heterogeneity. That bound is not proven as written. The supplementary proof builds the potential P^r = E[f(θ^r)] + C_0^r Σ p_i Ξ_i^r, but C_0^r depends on r through ¯ω^r. The difference P^{r+1} - P^r contains (C_0^{r+1} - C_0^r)Σ p_i Ξ_i^{r+1}, and the proof telescopes as if that term were absent. Nothing in the argument controls it. This is in the main proof, not a side lemma, so Theorem 1 and its corollaries about O(1/ε) communication complexity don't follow from the written analysis.\n\nSecond, Eq. (17) for ω_i^r is dimensionally inconsistent: the numerator sums element-wise ranges of z (dimension of z) while the denominator is ||z||². Since the condition a < 1/ω_i^r appears throughout the theorem, this needs to be fixed before the parameter region makes sense.\n\nWhat the paper does well: the algorithm is a reasonable new combination of SCAFFOLD-style control variates with stochastic quantization and time-varying local update counts. The control-variate step size a/(η eE_i^r) is a genuine twist, and the experimental section is thorough, with consistent gains over FedAvg, SCAFFOLD, FedDyn, FedPAQ, FedCAMS at B=2 and roughly 10x communication savings. The empirical work is reproducible in spirit, though there are no error bars and no code.\n\nTwo smaller issues: in Algorithm 2, when devices are removed due to low quantization bits, the aggregation uses the original m instead of renormalizing by the number of remaining devices, which biases the global update. And the relationship to the authors' own framework [39] is hinted at but never made precise.\n\nMy take: these are fixable, but the central convergence claim currently has a real gap. This is not a desk reject; the ideas are worth referee time. Send it to peer review with a clear request to fix the potential-function argument and Eq. (17) before any acceptance. I would not cite the convergence rate as-is, though I might cite the algorithm once it's repaired.","headline":"The convergence theorem that carries the paper has a missing term in the potential-function argument and the quantization parameter formula in Eq. (17) doesn't have consistent dimensions; the algorithm itself is sensible and the experiments are strong enough that a serious referee should look at it, but the main bound is currently unproven.","tokens_in":45652,"tokens_out":1718,"would_cite":false,"duration_ms":19523,"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":"The paper claims that a new algorithm, FedQVR, removes inter-device variance from the convergence bound of federated learning even when uplink updates are quantized and local update counts vary across devices, achieving O(1/R + σ²/√R)…","keywords":["federated learning","quantized communication","variance reduction","device heterogeneity","wireless edge networks","convergence analysis","resource allocation","control variates"],"falsifier":"Take a concrete vector such as $z=(1,-1)$ with $B=2$ and compute the true ratio $\\mathbb{E}\\|Q(z,B)-z\\|^2/\\|z\\|^2$; if that ratio is not a dimensionless number in $[0,1]$, or if it disagrees with Eq. (17), then the coefficient $\\omega_i^r$ is not the quantity Theorem 1 assumes and the parameter region $a<1/\\omega_i^r$ is unjustified.","tokens_in":44651,"feed_emoji":"📡","tokens_out":9750,"duration_ms":89098,"temperature":0.7,"pith_summary":"FedQVR is a federated-learning algorithm for wireless edge networks that couples control-variate variance reduction with stochastic quantization of uplink updates and time-varying numbers of local SGD steps per device. The paper's central claim is that this combination removes the inter-device variance term from the convergence bound: under smooth nonconvex losses, unbiased bounded-variance stochastic gradients, and an unbiased contracting quantizer, the average squared gradient norm decays as $O(1/R + \\sigma^2/\\sqrt{R})$, and no term in the bound depends on how heterogeneous the data or local update counts are. If the theorem is right, a system using as few as 2-bit quantized uploads and devices doing different amounts of local work reaches $\\epsilon$-accuracy in $O(1/\\epsilon)$ communication rounds, rather than the $O(1/\\epsilon^2)$ of FedAvg and SCAFFOLD. A companion scheme, FedQVR-E, allocates bandwidth and quantization bits per round to keep delay-constrained devices from dropping out. Experiments on CIFAR-10 and MNIST show FedQVR reaching the same test accuracies as unquantized baselines with roughly one-tenth of the upload cost.","feed_headline":"FedQVR kills the heterogeneity penalty in quantized federated learning","feed_subtitle":"Even 2-bit uploads and uneven local update counts keep the no-drift bound, so target accuracy costs a fraction of the bits.","key_machinery":"The load-bearing mechanism is the pair of control variates $c_i$ (per device) and $c$ (server) together with the server-side anchor $\\theta_0^r = \\theta^r - c^r/\\gamma$. Each participating device runs a convex combination of a control-variate-corrected SGD step and a pull back toward $\\theta_0^r$, which prevents local models from drifting when the control variates are stale, and updates $c_i$ with a decaying stepsize $a/(\\eta \\tilde{E}_i^r)$ so that the variate accumulates an exponentially weighted average of all historical local stochastic gradients. The quantized quantity is the local update $\\Delta_i^{r+1}=Q(\\theta_i^{r+1}-\\theta_0^r, B_i^r)$, and the same quantized update is used to refresh both control variates, preserving the identity $c=\\sum_i p_i c_i$ without extra communication. This construction is what lets the proof build a potential function whose decrease is controlled in every round by $\\|\\nabla f(\\theta^r)\\|^2$ plus variance terms that depend only on $\\sigma^2$ and quantization error, not on heterogeneity.","core_discovery":"The discovery the authors are trying to establish is Theorem 1: under Assumptions 1–3 (L-smooth lower-bounded losses; unbiased stochastic gradients with variance bounded by $\\sigma^2$; and an unbiased quantizer whose error variance is at most $\\omega_i^r \\mathbb{E}\\|\\theta_i^{r+1}-\\theta_0^r\\|^2$ with $0\\le \\omega_i^r\\le 1$), with $\\eta$ and $\\gamma$ satisfying (22)–(23), FedQVR obeys the bound in (24). The right-hand side of that bound contains no measure of data heterogeneity or of the variation in local update counts, which the authors interpret as intrinsic resilience to both forms of device heterogeneity (Remark 1). Corollary 1 specializes the bound to $O(1/R + \\sigma^2/\\sqrt{R})$ when the mini-batch size is $\\sqrt{R}$, and Corollary 2 gives $O(1/\\epsilon)$ communication complexity to reach $\\epsilon$-accuracy. The same convergence guarantee is what makes the quantized, partially participating algorithm communication-efficient despite coarse uplink transmission. A companion allocation scheme, FedQVR-E, is proposed for non-ideal wireless channels, where per-round bandwidth and quantization bits are chosen to maximize the minimum bit count under delay constraints.","pith_inferences":["If the heterogeneity-free bound is correct, the practical trade-off is between bits per round and rounds, not between heterogeneity and speed: operators can lower quantization bits aggressively and compensate with more rounds, without needing to sample more devices.","The theorem's validity hinges on Assumption 3's coefficient; because Eq. (17) appears dimensionally inconsistent, the actual admissible range of $a$ may differ from $a<1/\\omega_i^r$, and recomputing that coefficient is a direct test of the proof.","The same anchor-and-control-variate construction could be transplanted to decentralized or multi-server FL, where the central $c$ is replaced by a consensus estimate, potentially preserving the no-drift bound in topologies without a single aggregator.","The per-round separability of the FedQVR-E allocation problem suggests an online or predictive variant that tracks channel fading, converting the convex solve into a light per-round update."],"forward_implications":["Under the theorem, FedQVR reaches $\\epsilon$-accuracy in $O(1/\\epsilon)$ communication rounds and $O(m(d(B+1)+\\mu)/\\epsilon)$ uploaded bits, matching the best known nonconvex FL complexity while paying only a small per-round bit cost.","The absence of heterogeneity terms in (24) means the same round count suffices for strongly non-i.i.d. data and for devices with very different local epoch counts; no extra penalty appears.","Quantization bits can be kept small: the bound degrades only through $\\omega_i^r$, and experiments with $B_i^r=2$ show the algorithm still converges faster than unquantized baselines.","Under delay constraints, FedQVR-E's convex relaxation of bandwidth and quantization-bit allocation avoids transmission failures and preserves convergence where fixed even bandwidth would not.","With full gradients ($\\sigma=0$), the variance terms vanish and the rate becomes pure $O(1/R)$, meaning the algorithm is exact in the deterministic heterogeneous case."],"supporting_citations":[{"why":"Introduces SCAFFOLD control variates and the inter-device variance-reduction baseline that FedQVR modifies; also supplies the comparison for communication cost per round.","marker":"[16]"},{"why":"Provides the stochastic quantization operator and its error bound used in Assumption 3, and the delay/outage wireless model behind FedQVR-E.","marker":"[18]"},{"why":"Defines FedPAQ, the quantized-FL baseline FedQVR is compared against for communication efficiency.","marker":"[19]"},{"why":"Analyzes FedAvg on non-iid data and identifies the device-drift/inter-device variance problem the paper targets.","marker":"[35]"},{"why":"Gives FedDyn, a heterogeneity-robust baseline that also motivates the partial-participation robustness of FedQVR.","marker":"[37]"},{"why":"Formalizes heterogeneous local updates (HLU) in federated optimization, motivating the time-varying $E_i^r$ in FedQVR.","marker":"[13]"}],"fun_headline_variants":["FedQVR: quantized FL that shrugs off device heterogeneity","2-bit uploads, no drift: FedQVR's heterogeneous edge trick","Quantized variance reduction kills FL's heterogeneity tax","FedQVR: same convergence with coarse bits and uneven updates"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"Everything in the proof rests on the assumption that quantization noise is no larger than a fixed fraction (somewhere between 0 and 1) of the size of the local update being quantized, and the paper's own formula for that fraction does not have the right units to be that fraction.","fun_headline_variants_meta":{"raw":{"variants":["FedQVR: quantized FL that shrugs off device heterogeneity","2-bit uploads, no drift: FedQVR's heterogeneous edge trick","Quantized variance reduction kills FL's heterogeneity tax","FedQVR: same convergence with coarse bits and uneven updates"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000526,"raw_usage":{"total_tokens":2591,"prompt_tokens":1048,"completion_tokens":1543,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":664,"completion_tokens_details":{"reasoning_tokens":1471}},"tokens_in":664,"tokens_out":1543,"duration_ms":10886,"temperature":1.0,"reasoning_tokens":1471,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T18:27:27.259972+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a concrete vector such as $z=(1,-1)$ with $B=2$ and compute the true ratio $\\mathbb{E}\\|Q(z,B)-z\\|^2/\\|z\\|^2$; if that ratio is not a dimensionless number in $[0,1]$, or if it disagrees with Eq. (17), then the coefficient $\\omega_i^r$ is not the quantity Theorem 1 assumes and the parameter region $a<1/\\omega_i^r$ is unjustified.","supporting_citations":[{"cited_title":"Scaffold: Stochastic controlled averaging for federated learning,","cited_arxiv_id":null,"evidence_quote":"Introduces SCAFFOLD control variates and the inter-device variance-reduction baseline that FedQVR modifies; also supplies the comparison for communication cost per round."},{"cited_title":"Quantized federated learning under transmission delay and outage constraints,","cited_arxiv_id":null,"evidence_quote":"Provides the stochastic quantization operator and its error bound used in Assumption 3, and the delay/outage wireless model behind FedQVR-E."},{"cited_title":"FedPAQ: A communication-efficient federated learning method with periodic averaging and quantization,","cited_arxiv_id":null,"evidence_quote":"Defines FedPAQ, the quantized-FL baseline FedQVR is compared against for communication efficiency."},{"cited_title":"On the convergence of FedAvg on non-iid data,","cited_arxiv_id":null,"evidence_quote":"Analyzes FedAvg on non-iid data and identifies the device-drift/inter-device variance problem the paper targets."},{"cited_title":"Federated learning based on dynamic regularization,","cited_arxiv_id":null,"evidence_quote":"Gives FedDyn, a heterogeneity-robust baseline that also motivates the partial-participation robustness of FedQVR."},{"cited_title":"Federated optimization in heterogeneous networks,","cited_arxiv_id":null,"evidence_quote":"Formalizes heterogeneous local updates (HLU) in federated optimization, motivating the time-varying $E_i^r$ in FedQVR."}],"review_version":1}