{"id":"517ff6be-2fab-46d9-b280-c0dbaf23c0a8","arxiv_id":"2502.00206","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"BICompFL applies minimal random coding to both uplink and downlink in stochastic federated learning, cutting measured communication cost by 5-32x on MNIST, Fashion-MNIST, and CIFAR-10.","lead":"This paper introduces BICompFL, a method that compresses both uploads and downloads in federated learning using a sampling technique called minimal random coding. On small image benchmarks it reports 5-32x lower communication cost than standard baselines at similar accuracy.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 2's proof reverses the monotonicity of 1/E[M] in L; since Lemma 2 underpins Lemma 1 and Theorem 1, the claimed contraction and convergence guarantees are not established by the provided proof.","rationale":"The reader identified the bounded-divergence assumptions (|q_j - p_j| <= rho and |p_i - p_j| <= zeta) as the weakest point. Those assumptions are indeed important for the quantitative communication-cost bound. However, the more load-bearing issue is internal to the proof of Lemma 2: the monotonicity direction used to bound the MRC sampling error is reversed. For q < p, more weight on the smaller likelihood ratio as L increases drives E[M] down and 1/E[M] up, so the claimed inequality has the wrong sign. Since Lemma 2 is the foundation for Lemma 1 and Theorem 1, the theoretical claims in the abstract and contributions are not currently demonstrated even when rho and zeta are small. This is a distinct and more severe concern than the reader's weakest-assumption point: it is not a premise that can be relaxed, but a step that must be corrected. The experimental side of the paper is substantial, with reproducible-looking bitrate tables and ablations, so I do not recommend rejection; the verdict should remain conditional, with the condition that the proof of Lemma 2 be repaired or the theoretical claims scaled back. I therefore partially concur with the reader's conditional verdict but disagree on the reason: the decisive issue is the validity of the core lemma, not the boundedness assumptions alone.","tokens_in":35231,"tokens_out":13088,"duration_ms":127996,"concrete_test":"Independently re-derive Lemma 2 with correct monotonicity. Concretely, for fixed q < p, evaluate f(L) = 1/E_Ber((L+1)/nIS)[M] for two values of L and verify that f increases with L; then redo the Chernoff decomposition using L <= nIS(p + eta_delta) in the upper-bound branch. Check whether the corrected first-order term is |Delta| * sqrt(log(nIS)/nIS) rather than (Delta + Delta^2) * sqrt(log(nIS)/nIS). If the corrected bound differs, recompute Lemma 1's contraction factor delta and the required nIS, and re-check Theorem 1's downlink bound. As a numerical cross-check, compute the exact MRC error for q = 0.55, p = 0.6 and nIS in [10^3, 10^6]; if the error decays with a positive coefficient while Lemma 2's expression has a negative or zero (Delta + Delta^2) coefficient, the stated lemma is false.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"In the proof of Lemma 2 (Appendix B), for the branch q < p, the authors define M with values q/p and (1-q)/(1-p), with success probability (L+1)/nIS on the smaller value q/p. As L increases, E_Ber[M] decreases, so 1/E_Ber[M] is strictly increasing in L, not non-increasing as claimed. The subsequent inequality 1/E_Ber[M(L)] <= 1/E_Ber[M(nIS(p - eta_delta))] therefore has the wrong direction; the same sign error appears in the q > p branch. The displayed upper bound on |Pr(X_ell = 1) - q| does not follow from the preceding steps. Lemma 2 is the core refinement over Chatterjee-Diaconis and is used to prove Lemma 1 (the contraction property of Cmrc composed with Qs) and Theorem 1 (the downlink KL-divergence bound). Without Lemma 2, the paper's convergence guarantees and its claimed communication-cost analysis are unsupported. This is independent of the rho/zeta bounded-divergence assumptions: even in the regime where those assumptions hold exactly, the proof chain breaks. The final bound may be repairable, for instance by using the upper endpoint p + eta_delta and an absolute value |Delta| in the first-order term, but that repair is non-trivial and the current statement of Lemma 2 is not established.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes BICompFL, a framework for stochastic federated learning with bi-directional compression based on minimal random coding (MRC). Two algorithms are given, one for globally shared randomness (BICompFL-GR) and one for private shared randomness (BICompFL-PR), together with an extension to conventional FL with stochastic quantization (BICompFL-GR-CFL). The experimental section reports large communication-cost reductions on MNIST, Fashion-MNIST, and CIFAR-10 compared with several non-stochastic baselines. The theoretical part claims (i) a contraction property for MRC composed with QSGD (Lemma 1), (ii) a refined MRC analysis for Bernoulli distributions (Lemma 2), (iii) a downlink KL-divergence bound (Theorem 1), and (iv) a convergence guarantee for an error-feedback version (Theorem 2).","tokens_in":35482,"tokens_out":6008,"duration_ms":58846,"significance":"If the theoretical results were correct, the paper would make a useful contribution to communication-efficient FL by extending MRC-based stochastic compression to the downlink and by providing a refined analysis of importance sampling for Bernoulli distributions. The experimental study is extensive, covering multiple datasets, heterogeneity regimes, ablations, and a careful accounting of communication bits, and the reported savings are substantial. The paper also provides a high level of reproducibility detail. However, the theoretical core is not currently established: the proof of Lemma 2 contains a sign error in a monotonicity argument, and Lemma 2 underpins Lemma 1, Theorem 1, and Theorem 2. In addition, the convergence theorem is only sketched and applies to a QSGD-based variant with s ≥ sqrt(2d), which is not the stochastic SignSGD method used in the experiments. These issues are load-bearing for the paper's central theoretical claims, though the experimental methodology and algorithmic framework remain valuable.","major_comments":[{"comment":"The proof of Lemma 2 contains a sign error in the monotonicity argument. For the branch q < p, the random variable M takes the value q/p (which is smaller than (1-q)/(1-p)) with probability (L+1)/nIS. As L increases, E_Ber[M] decreases, so 1/E_Ber[M] is strictly increasing in L, not non-increasing as claimed. The subsequent inequality 1/E_Ber[M(L)] ≤ 1/E_Ber[M(nIS(p - η_δ))] therefore has the wrong direction, and the same issue appears in the q > p branch. Consequently, the displayed upper bound on |Pr(X_l = 1) - q| does not follow from the preceding steps. Since Lemma 2 is used to prove Lemma 1 and Theorem 1, the contraction property and the downlink KL-divergence bound are not established by the provided proofs. The bound may be repairable (e.g., by using the upper endpoint p + η_δ and an absolute value in the first-order term), but the current statement is not proved.","section":"Section 5, Lemma 1 and Theorem 2"},{"comment":"The contraction property in Lemma 1 is stated for the QSGD quantizer with s ≥ sqrt(2d), which requires the number of quantization levels to grow exponentially with dimension; this is impractical for large d and is not the stochastic SignSGD compressor used in the experiments described in Section 4. Theorem 2, stated in Appendix C, is only a sketch and inherits the same condition. Thus the convergence guarantees do not apply to the experimentally evaluated BICompFL-GR-CFL method, and the paper should either provide convergence analysis for the actually implemented compressor or clearly separate the theoretical claims from the experimental validation.","section":"Appendix C, Theorem 2"},{"comment":"In the proof of Theorem 1, the Hoeffding bound is applied to |\\hat{q}_j - Pr(X_l = 1)| with a denominator involving nIS, writing sqrt(-ln(δ'/2)/(2 nIS)). However, the estimate \\hat{q}_j is the average of K samples (corresponding to nUL in the theorem statement), so the sample count in the Hoeffding bound should be nUL, not nIS. The theorem statement correctly uses sqrt(ln(2/δ')/(2 nUL)), but the proof does not match the statement. This is a concrete gap in the derivation of the downlink communication-cost bound.","section":"Appendix B, proof of Theorem 1"},{"comment":"The bitrate accounting for the broadcast case is not fully explained. For BICompFL-GR, the downlink in the point-to-point model consists of relaying the other clients' indices; the tables report a downlink bitrate of (n-1) times the uplink bitrate. In the broadcast column, the bitrate is reduced by roughly a factor of n, but it is unclear whether this assumes the server broadcasts the full set of indices once or uses a different downlink transmission scheme. The derivation of the bpp (BC) numbers should be made explicit so that the experimental comparisons are unambiguous.","section":"Appendix I, bitrate tables"}],"minor_comments":[{"comment":"In the displayed equation after defining M, the binomial coefficient is written as \\binom{n - 1}{L} instead of \\binom{nIS - 1}{L}; this is a typo that should be corrected.","section":"Appendix B"},{"comment":"The assumption |q_j - p_j| ≤ ρ is stated as 'natural' and enforceable by projecting onto a KL ball, but the experimental local training in Algorithm 3 does not perform such a projection. The paper should clarify whether the theoretical results apply to the unmodified algorithm or to a projected variant.","section":"Section 5"},{"comment":"The abstract and Section 4 use the phrase 'order of magnitude' and 'order-wise improvements'; the reported reductions versus the best non-stochastic baselines are factors between 5 and 32 (e.g., Figure 2 and Tables 5-12), which is at most about 1.5 orders of magnitude. A more precise quantitative summary would avoid overstating the improvement.","section":"Section 4"},{"comment":"In the non-i.i.d. CIFAR-10 results (Table 12), BICompFL-PR-Fixed-SplitDL achieves accuracy 0.47, much lower than BICompFL-GR-Fixed (0.665); the main text mentions this qualitatively but the large drop and its variance should be reported in the main-body discussion of partitioning.","section":"Appendix I"},{"comment":"The notation nIS is used both for the number of importance samples per block and, in the proof of Theorem 1, for the number of samples used in the Hoeffding bound; this dual use is confusing and should be disambiguated (e.g., by using nUL consistently for the number of transmitted samples).","section":"Section 2"}],"recommendation":"major_revision","confidential_remarks":"The paper's experimental contribution is solid and the writing is generally clear, but the theoretical section is not in a publishable state. The Lemma 2 proof error is the most serious issue because it breaks the chain leading to Lemma 1 and Theorem 1; the mismatch between the theoretical compressor (QSGD, s ≥ sqrt(2d)) and the experimental one (stochastic SignSGD) further weakens the claimed convergence guarantees. The authors may be able to repair the proof of Lemma 2 and adjust the statements, and the manuscript could then be reconsidered. I would advise the editor to request a thorough revision of the theoretical analysis before any acceptance decision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know. First, the experimental work is real: BICompFL-GR and BICompFL-PR extend MRC to the downlink, and the reported bitrate reductions (5–32x over the best non-stochastic baselines, on MNIST/Fashion/CIFAR with iid and non-iid splits) are backed by thorough tables and ablation studies. Second, the theoretical chain is not valid as written: Lemma 2's proof has a sign/monotonicity error, and since Lemma 2 feeds Lemma 1 and Theorem 1, the contraction and convergence guarantees are not established.\n\nWhat is actually new: the downlink MRC algorithms with two shared-randomness variants, and the attempt at a refined Bernoulli MRC analysis. That refinement would be a useful standalone result if repaired. The paper is also honest about its assumptions (bounded local drift, bounded prior disagreement) and cites the relevant prior work, including Isik et al. and Chatterjee–Diaconis, without self-citation padding.\n\nThe soft spot is load-bearing. In the proof of Lemma 2, for q<p, the random variable M takes the smaller value q/p with probability (L+1)/nIS and the larger value (1-q)/(1-p) otherwise. As L increases, E[M] decreases, so 1/E[M] strictly increases. The proof claims it is non-increasing and uses that direction in subsequent inequalities. The same reversal appears in the q>p branch. The displayed upper bound on |Pr(X_ell=1)-q| does not follow. This is not a cosmetic typo: it inverts the core step. The bound might be repairable, but the current proof does not establish Lemma 2, and therefore does not establish Lemma 1 or Theorem 1.\n\nBeyond that, even if Lemma 2 were fixed, the theory covers a QSGD variant with s >= sqrt(2d), which is impractical for large models, while the experiments use a stochastic SignSGD variant not covered by the contraction analysis. The main experimental body is also in the FedPM mask-training setting; the conventional-FL extension is a single variant with less depth. No code is released.\n\nWho this is for: researchers working on communication-efficient FL, particularly those building on MRC or FedPM. The experimental part is worth reading and the adaptive block allocation ideas are useful. But the theory needs correction before the convergence claims can be trusted.\n\nRecommendation: send to peer review with a clear request for major revision. A good referee will spot the Lemma 2 issue and ask for either a corrected proof or a downgrading of the theoretical claims to conjectures. If the authors fix the lemma, this is a solid contribution.","headline":"Solid experimental contribution on bidirectional MRC compression, but the theoretical proof chain has a monotonicity-direction error in Lemma 2 that currently invalidates the contraction and convergence claims.","tokens_in":36091,"tokens_out":2357,"would_cite":false,"duration_ms":24548,"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":"Two-way minimal-random-coding compression cuts federated communication cost by an order of magnitude while keeping accuracy.","keywords":["federated learning","bidirectional compression","stochastic compression","minimal random coding","importance sampling","convergence analysis","probabilistic mask training","communication efficiency"],"falsifier":"Simulate minimal random coding for a Bernoulli posterior $q$ and prior $p$ with $|q-p|$ large (say 0.4) and $n_{\\mathrm{IS}}=256$, and measure $|\\Pr(X=1)-q|$ across many replications; if the error consistently exceeds the Lemma 2 bound $\\Delta'/n_{\\mathrm{IS}}^2 + O((\\Delta+\\Delta^2)\\sqrt{6p\\log(2n_{\\mathrm{IS}})/n_{\\mathrm{IS}}})$, the refined MRC analysis underlying Theorem 1 is wrong.","tokens_in":34993,"feed_emoji":"📡","tokens_out":8013,"duration_ms":72570,"temperature":0.7,"pith_summary":"This paper takes on the full communication bottleneck of federated learning: not just clients sending updates to the server, but also the server sending the refreshed model back to every client. It proposes BICompFL, which represents each model update as a distribution over binary mask values and transmits a sample of it through minimal random coding (MRC): both sides generate candidate samples from a shared prior, and the sender pays only for an index telling the receiver which candidate to use. Two variants handle global shared randomness versus per-client private randomness, since the extra downlink compression round in the private case adds noise that slows convergence. The paper reports that BICompFL cuts total communication cost by an order of magnitude relative to several compression baselines while keeping the same accuracy, and it proves a contraction property and a high-probability divergence bound that together support convergence analysis for MRC-based compression in both settings.","feed_headline":"Two-way compression cuts federated learning bitrate 10x","feed_subtitle":"Sending model updates as short indices from a shared prior shrinks both uplink and downlink traffic.","key_machinery":"The load-bearing object is minimal random coding (MRC), a stochastic compressor that turns a posterior distribution into a short index. Encoder and decoder first generate $n_{\\mathrm{IS}}$ candidate samples from a shared prior using shared randomness; the encoder weights the candidates by likelihood ratios $Q(X)/P(X)$, samples an index from that categorical distribution, and sends the index using $\\log_2(n_{\\mathrm{IS}})$ bits, so the decoder can reproduce an approximate sample from $Q$. The cost is governed by the KL divergence between posterior and prior, so BICompFL's trick is to choose the previous global model estimate as the prior, making the transmitted amount shrink as training converges. The paper's new analytic engine is a Bernoulli-specific refinement of the MRC error bound that vanishes when posterior equals prior and depends explicitly on $n_{\\mathrm{IS}}$; this feeds both the high-probability bound on the aggregated model's divergence (Theorem 1) and the contraction property (Lemma 1) that converts MRC into a biased contractive compressor usable in standard convergence proofs.","core_discovery":"The central claim is that stochastic federated learning can be made communication-efficient in both directions without sacrificing accuracy, provided the compressor is driven by the right side information. In BICompFL, the server and each client share a prior distribution (initially the global model, later the previous model estimate); the client encodes a sample from its updated posterior by importance-sampling a fixed number of candidate samples from the prior and transmitting only the winning index, costing $\\log_2(n_{\\mathrm{IS}})$ bits per block. Two versions are analyzed: one with global shared randomness, where the server relays other clients' indices so everyone reconstructs the same global estimate, and one with only private randomness, where the server performs a separate downlink MRC round per client. The theoretical contribution is a refined analysis of MRC for Bernoulli distributions that bounds the per-client estimation error, leading to a high-probability upper bound on the KL divergence between the aggregated model and each client's prior, with an explicit $1/\\sqrt{n_{\\mathrm{UL}}}$ coupling between uplink and downlink cost. Combined with a contraction property showing the MRC-plus-quantization step shrinks the squared gradient norm by a factor $(1-\\delta)$, the paper obtains convergence guarantees for conventional federated learning with stochastic compression as well.","pith_inferences":["Beyond the paper, the refined Bernoulli MRC error bound should transfer to any relative-entropy coding scheme with Bernoulli latents, such as compression of Bayesian neural networks outside federated learning.","The explicit $1/\\sqrt{n_{\\mathrm{UL}}}$ coupling in the divergence bound reads as a design rule: when the downlink is the bottleneck, spending a few more uplink samples per client buys a more accurate global estimate and cheaper downlink transmission.","A testable extension is per-block adaptive control of $n_{\\mathrm{IS}}$: estimate local divergence per block rather than fixing $n_{\\mathrm{IS}}=256$, which could cut bitrate further in heterogeneous regimes where divergence varies strongly across parameter blocks.","The restriction to Bernoulli posteriors leaves open whether analogous contraction and divergence bounds hold for categorical or Gaussian posteriors, which would broaden the method to regression and larger models."],"forward_implications":["On MNIST, Fashion-MNIST, and CIFAR-10, BICompFL reaches roughly the same final accuracy as uncompressed FedAvg while transmitting about 0.06\\text{--}0.34 bits per parameter instead of 64, and the paper reports at least a 5\\text{--}32-fold saving over the best non-stochastic bidirectional baselines.","Because per-round cost is governed by the KL divergence between posterior and prior, communication automatically falls as training converges, and adaptive block allocation reduces it further with little accuracy loss.","The contraction property turns MRC plus a stochastic quantizer into a biased contractive compressor, so the same scheme can be dropped into conventional federated learning and inherits convergence guarantees, including with error feedback.","Under private (per-client) randomness the extra downlink compression round slows convergence, but splitting the downlink model across clients cuts downlink cost by the number of clients, which is attractive when broadcast is available.","Partial client participation is supported by the private-randomness variant, which global shared randomness does not allow."],"supporting_citations":[{"why":"Establishes the $\\Theta(\\exp(D_{\\mathrm{KL}}(Q\\|P)))$ sample-size law for importance sampling that MRC's bit budget relies on.","marker":"(Chatterjee & Diaconis, 2018)"},{"why":"Introduces KLMS/adaptive side-information compression in stochastic FL, the uplink-only precursor that BICompFL extends to the downlink.","marker":"(Isik et al., 2024)"},{"why":"Introduces minimal random coding as a way to get bits back from compressed model parameters.","marker":"(Havasi et al., 2019)"},{"why":"Defines federated probabilistic mask training, the Bayesian FL testbed used by BICompFL.","marker":"(Isik et al., 2023)"},{"why":"Defines FedAvg, the uncompressed baseline and the oracle accuracy target.","marker":"(McMahan et al., 2017)"},{"why":"DoubleSqueeze is the strongest bidirectional compression baseline BICompFL must beat.","marker":"(Tang et al., 2019)"},{"why":"Provides the unbiased stochastic quantizer QS and its variance bound used in the contraction lemma.","marker":"(Alistarh et al., 2017)"},{"why":"SignSGD supplies the 1-bit compressor used by the non-stochastic baselines and by BICompFL-GR-CFL.","marker":"(Seide et al., 2014)"},{"why":"Supplies the logarithmic bound used to size $n_{\\mathrm{IS}}$ in the contraction proof of Lemma 1.","marker":"(Weinberger & Yemini, 2023)"}],"fun_headline_variants":["Bi-directional compression slashes federated learning bitrate 10x","Stochastic FL with two-way compression cuts communication 10x","BICompFL: compress both directions, cut FL bits by 10x","Two-way stochastic compression trims federated learning traffic","10x smaller FL updates via bi-directional compression"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The cost and convergence bounds assume each client's local training moves the model distribution only a bounded distance from the shared prior, and that clients' priors stay close to one another; if those fail, the predicted communication savings do not apply.","fun_headline_variants_meta":{"raw":{"variants":["Bi-directional compression slashes federated learning bitrate 10x","Stochastic FL with two-way compression cuts communication 10x","BICompFL: compress both directions, cut FL bits by 10x","Two-way stochastic compression trims federated learning traffic","10x smaller FL updates via bi-directional compression"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000208,"raw_usage":{"total_tokens":1406,"prompt_tokens":949,"completion_tokens":457,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":565,"completion_tokens_details":{"reasoning_tokens":370}},"tokens_in":565,"tokens_out":457,"duration_ms":4562,"temperature":1.0,"reasoning_tokens":370,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-09T19:49:02.560004+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Simulate minimal random coding for a Bernoulli posterior $q$ and prior $p$ with $|q-p|$ large (say 0.4) and $n_{\\mathrm{IS}}=256$, and measure $|\\Pr(X=1)-q|$ across many replications; if the error consistently exceeds the Lemma 2 bound $\\Delta'/n_{\\mathrm{IS}}^2 + O((\\Delta+\\Delta^2)\\sqrt{6p\\log(2n_{\\mathrm{IS}})/n_{\\mathrm{IS}}})$, the refined MRC analysis underlying Theorem 1 is wrong.","supporting_citations":[{"cited_title":"The sample size required in importance sampling","cited_arxiv_id":null,"evidence_quote":"Establishes the $\\Theta(\\exp(D_{\\mathrm{KL}}(Q\\|P)))$ sample-size law for importance sampling that MRC's bit budget relies on."},{"cited_title":"Adaptive compression in federated learning via side information","cited_arxiv_id":null,"evidence_quote":"Introduces KLMS/adaptive side-information compression in stochastic FL, the uplink-only precursor that BICompFL extends to the downlink."},{"cited_title":"Minimal random code learning: Getting bits back from compressed model parameters","cited_arxiv_id":null,"evidence_quote":"Introduces minimal random coding as a way to get bits back from compressed model parameters."},{"cited_title":"Sparse random networks for communication-efficient federated learning","cited_arxiv_id":null,"evidence_quote":"Defines federated probabilistic mask training, the Bayesian FL testbed used by BICompFL."},{"cited_title":"Communication-Efficient Learning of Deep Networks from Decentralized Data","cited_arxiv_id":null,"evidence_quote":"Defines FedAvg, the uncompressed baseline and the oracle accuracy target."},{"cited_title":"QSGD : Communication-efficient SGD via gradient quantization and encoding","cited_arxiv_id":null,"evidence_quote":"Provides the unbiased stochastic quantizer QS and its variance bound used in the contraction lemma."},{"cited_title":"1-bit stochastic gradient descent and its application to data-parallel distributed training of speech DNNs","cited_arxiv_id":null,"evidence_quote":"SignSGD supplies the 1-bit compressor used by the non-stochastic baselines and by BICompFL-GR-CFL."},{"cited_title":"Multi-armed bandits with self-information rewards","cited_arxiv_id":null,"evidence_quote":"Supplies the logarithmic bound used to size $n_{\\mathrm{IS}}$ in the contraction proof of Lemma 1."}],"review_version":1}