{"id":"7ff850b8-884f-43b7-ae16-89da47773b72","arxiv_id":"2508.21286","paper_version":1,"verdict":"REJECT","confidence":"HIGH","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"DFedRW runs parallel random walk model updates with decentralized averaging and reports accuracy gains of up to 38 percentage points over FedAvg and DFedAvg under high heterogeneity.","lead":"A decentralized federated learning algorithm, DFedRW, trains models by passing them along random walks between devices instead of updating many times on one device, and runs several such walks in parallel. The authors report faster convergence and accuracy gains of roughly 38 percentage points under highly heterogeneous data, plus a quantized version that cuts communication.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 1 never models aggregation step (11); Section V-B merely asserts the random walk trajectory is 'unbroken,' so the O(1/k^{1-q}) bound is not established for DFedRW as implemented.","rationale":"I read the paper as trying to prove O(1/k^{1−q}) convergence for a decentralized federated averaging algorithm built from parallel random walks with periodic weighted aggregation. For that claim to hold, the analysis must cover the periodic aggregation step that defines DFedRW. The proof, however, never does: every displayed step in Appendix A is a single-chain random-walk SGD recursion. The manuscript's own Section V-B states the necessary continuity assumption ('the random walk trajectory remains unbroken by the aggregation process') but provides no formal justification, and the algorithm description contradicts it (re-sampled initial devices in Algorithm 1 vs. inherited chains in the Reddit setup). This is precisely the weakest assumption the reader identified. The concern is not about disagreement with existing theory; it is an internal mismatch between the algorithm and the object being analyzed. The empirical results are suggestive, and the algorithmic idea may be salvageable with a proper consensus-error analysis, but the central theoretical claim is currently unsupported. I therefore agree with the reader's REJECT verdict; my stress-test does not change it.","tokens_in":31368,"tokens_out":4674,"duration_ms":50410,"concrete_test":"Re-derive Theorem 1 while explicitly including aggregation (11). Starting from Eq. (38), instantiate the post-aggregation model w^{t+1,0}_i = Σ_{l∈N_A(i)} (n_l^t/m_t) w^{t,last}_l and the actual initial-device sampling rule, then compute E_{i_k}[F_{i_k}(w_{k−τ}) − F_{i_k}(w∗)]. If an extra term depending on the disagreement among the M chains' last models, or on the restart distribution, appears, the stated bound (15) is not established. A complementary numerical check: run DFedRW with M=2 on a small strongly convex least-squares problem with q=0.75 and plot E∥w_k−w∗∥^2 against k^{q−1}; a meaningfully worse slope would corroborate the mismatch.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The proof of Theorem 1 analyzes a single random-walk SGD sequence: w_{k+1} = Π_W(w_k − η_k ∇F_{i_k}(w_k)) (Appendix A, Eqs. (22)–(25)). But DFedRW periodically applies decentralized weighted averaging (11), replacing the model at each device with a weighted sum of last-update models from multiple random-walk trajectories, and Algorithm 1 re-samples initial devices uniformly each round. Section V-B contains the key assertion: 'the random walk trajectory remains unbroken by the aggregation process.' No equation or argument substantiates this. Lemma 6 (Appendix A, Eq. (38)) conditions on a single trajectory X_0,...,X_{k−τ}; after aggregation, w_{k−τ} depends on M parallel trajectories and the next walk starts from a re-sampled (or, in the Reddit experiments, inherited) device, so P(i_k=i | X_{k−τ}) is no longer the τ-step transition probability of that same chain. Hence Lemma 6 and the final O(1/k^{1−q}) bound do not apply to the algorithm as written. This gap is load-bearing because it is the sole route to the headline theoretical contribution; without it, the paper rests on experiments alone, and the main experiments use η_k = 1/(R k^{0.499}), outside the theorem's assumption q ∈ (1/2, 1).","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes DFedRW, a decentralized federated averaging algorithm in which local updates are replaced by random-walk SGD steps along a Markov chain on the device graph, with M parallel chains and periodic decentralized weighted averaging (Eq. (11)). A quantized version, QDFedRW, is also introduced. The main theoretical claim is a convex convergence bound of order O(1/k^{1-q}) (Theorem 1) with an additional quantization term (Theorem 2), and Proposition 1 gives conditions under which quantization saves communication. Experiments on MNIST, Fashion-MNIST, and Reddit compare DFedRW/QDFedRW against FedAvg, DFedAvg, and DSGD under various statistical and system heterogeneity levels, reporting accuracy gains and lower communication cost for the busiest device.","tokens_in":31725,"tokens_out":7134,"duration_ms":72600,"significance":"If the theoretical result were valid, the paper would provide a useful convergence guarantee for a communication-efficient decentralized method that handles heterogeneity. The algorithmic idea is interesting and the experimental study is extensive, covering multiple datasets, heterogeneity settings, network topologies, and quantization levels. The paper also makes a reasonable attempt to separate the effects of statistical and system heterogeneity. However, the central convergence proof is not actually about the algorithm as implemented, and the experimental learning-rate schedule falls outside the theorem's assumptions. These issues undermine the main advertised contribution.","major_comments":[{"comment":"The proof of Theorem 1 analyzes the single-chain recurrence (22) and never applies the aggregation rule (11). The only bridge is the assertion in Section V-B that the random walk trajectory 'remains unbroken by the aggregation process,' but no equation or argument substantiates this. After aggregation, w_{k+1} is a weighted average of outputs of M chains, and Algorithm 1 line 3 re-samples the initial device, so the pair (i_k, w_k) is not a Markov chain with transition P. Consequently Lemma 6, Eq. (38), which uses P(i_k=i | X_{k-τ}) = [P^τ]_{i_{k-τ},i}, does not apply to DFedRW as implemented. The bound (15) also has no dependence on M or the aggregation weights, confirming that the parallel-chain algorithm is not the object being analyzed. This is a load-bearing gap: without Lemma 6, the claimed O(1/k^{1-q}) rate is unproven.","section":"Section V-B and Appendix A, Eq. (22)/(11)"},{"comment":"The main experiments use η_k = 1/(R k^{0.499}), i.e., q=0.499, while Theorem 1 requires 1/2 < q < 1. For q=0.499, Assumption 2 fails because ∑ ln k · (η_k)^2 diverges when 2q<1. Thus the empirical evaluation does not operate in the theorem's regime, weakening the connection between the numerical results and the theoretical claim. Fig. 10 uses q=0.501, but that is not the main setup.","section":"Section VI-B, learning rate"},{"comment":"The proof of Theorem 2 (Appendix B) adds quantization-error bounds to the same single-trajectory argument (Eqs. (46)-(52)) and does not introduce the aggregation step (14) or the M parallel chains. The trajectory-continuity assertion is reused without proof. Hence Theorem 2 is also unsupported.","section":"Theorem 2 and Appendix B"}],"minor_comments":[{"comment":"The abstract reports a 38.3% accuracy increase, while Section VI-B reports 38.8% for the same comparison. Please reconcile the numbers.","section":"Abstract vs. Section VI-B"},{"comment":"The state-space size is denoted K in Definitions 3 and 4, but the graph has n devices (V=[n]) and K is also used for the number of random-walk epochs. This is confusing; please use n consistently for the state-space dimension.","section":"Definitions 3 and 4"},{"comment":"The loop is written 'for k = {0, 2, ..., K_m − 1}'; it should be 'k = 0, 1, ..., K_m − 1'.","section":"Algorithm 1, line 5"},{"comment":"The notation N is used in Eq. (39) ('∑_k N η_k/(2k)') while n is used elsewhere in the same proof; please make the notation consistent.","section":"Eq. (38)-(39)"},{"comment":"The stationary distribution Π* is written as an n×n matrix '[(π*)^T, ..., (π*)^T]^T' but it should be a vector of length n. This is likely a typo.","section":"Section III-D, transition matrix"}],"recommendation":"reject","confidential_remarks":"The proof gap is not a presentation issue: the theorem's proof analyzes a single random-walk SGD chain and never models the decentralized aggregation of M parallel chains, so the headline convergence bound is not established for the algorithm the paper implements. The experimental learning rate is also outside the theorem's assumptions. These issues are load-bearing and would require a substantially new convergence analysis rather than a local fix."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The algorithmic idea is genuinely new: parallel random walk chains with periodic decentralized weighted averaging, plus a quantized difference-transmission variant. The empirical work is the strongest part — MNIST, Fashion-MNIST, and Reddit with a spread of statistical and system heterogeneity, graph topologies, and communication-cost curves. The reported gains under high heterogeneity (up to ~38 percentage points) are large and, if they survive reimplementation, would make this a practical swap-in for FedAvg in decentralized settings. The paper also gives a clean sufficient condition for when quantization pays off.\n\nThe soft spot is the theory, and it is load-bearing. Theorem 1's proof (Appendix A) starts from the single-device update (22) and never writes down the aggregation (11) or the M parallel chains. The bound has no dependence on M or on the aggregation weights. Section V-B asserts that \"the random walk trajectory remains unbroken by the aggregation process,\" but no equation or argument backs this up. After aggregation, w_{k−τ} depends on M parallel trajectories and on re-sampled initial devices, so Lemma 6's Markov property — which conditions on a single trajectory X_0,...,X_{k−τ} — no longer applies. The same gap carries into Theorem 2 and Proposition 1. On top of that, the main experiments use η_k = 1/(R k^{0.499}), which is outside the theorem's assumption q ∈ (1/2, 1). So the headline convergence rate O(1/k^{1−q}) is not established for DFedRW as implemented.\n\nThe paper is not incoherent; the authors seem to know the proof follows a single chain and treat aggregation as a perturbation. But that continuity assumption is exactly what needs proving, and it is not a minor technicality — it is the bridge from known random-walk SGD rates to this specific algorithm. The empirical claims stand on their own, and the algorithm may be salvageable either by repairing the proof or by simplifying the algorithm to match the analysis (e.g., one chain, or aggregation only at the end).\n\nWho is this for? Researchers working on decentralized FL, especially those interested in random-walk methods and communication-efficient training. They should read the experiments and treat the theory as unverified. I would send this to peer review — a serious referee can help the authors fix the proof or at least correctly scope the claims — but the current theoretical contribution should not be accepted as-is. If the authors can close the aggregation gap, this becomes a solid paper.","headline":"Interesting algorithm and strong experiments, but the convergence theorem doesn't model the aggregation step, so the main theoretical claim is unproven.","tokens_in":32190,"tokens_out":1592,"would_cite":false,"duration_ms":18666,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W15","90C25"],"pacs":[],"model":"deepseek-v4-flash","headline":"Decentralized federated learning by random walk claims to converge at the same order as SGD while outperforming FedAvg under data and device heterogeneity, without a central server.","keywords":["decentralized federated learning","random walk SGD","statistical heterogeneity","system heterogeneity","quantization","convex convergence","stragglers","Markov chain mixing"],"falsifier":"For M=2 chains on a connected graph, run DFedRW with a fixed step size and log the pre-aggregation and post-aggregation models. If the post-aggregation model cannot be reproduced as the state of a single Markov-chain trajectory with the paper's transition matrix, the mixing argument in the proof is not operating on the actual iterates; then check numerically whether the predicted O(1/k^{1-q}) slope holds for M=2 or only for M=1.","tokens_in":31278,"feed_emoji":"🐾","tokens_out":7405,"duration_ms":69602,"temperature":0.7,"pith_summary":"This paper proposes DFedRW, a decentralized federated learning algorithm that replaces the repeated local epochs of FedAvg with a random walk: the model is passed from device to device, each performing one SGD step, and after several steps a set of parallel random-walk chains are averaged over the graph. The point is to keep the communication savings of multiple local updates while exposing the model to more heterogeneous data, and to let slower devices contribute partial updates instead of being dropped. Under convex assumptions and a decreasing step size, the authors prove that (quantized) DFedRW converges with an upper bound of order O(1/k^{1-q}), close to the O(1/sqrt(k)) rate of SGD, with constants depending on graph mixing, statistical dissimilarity, and compute capability. Numerically, they report accuracy gains over (D)FedAvg that grow with heterogeneity—up to roughly 38% on their benchmarks—without increasing the communication cost of the busiest device. If correct, this offers FedAvg-like communication efficiency with better robustness to skewed and imbalanced data in serverless settings.","feed_headline":"Random-walk FL converges like SGD and beats FedAvg on skewed data","feed_subtitle":"No server, stragglers still contribute, and quantization cuts communication without sacrificing accuracy.","key_machinery":"The main object is a finite-state Markov chain on the device graph, with a transition matrix P designed by a local acceptance-rejection rule using only degree information, so the walk converges to a stationary distribution over devices. The random walk carries the model from device to device, each performing one SGD step, while M parallel chains run simultaneously. Around this, the algorithm performs a decentralized weighted aggregation, weighted by local sample counts, that averages the last parameters of the chains periodically. The load-bearing quantities are the chain's second-largest eigenvalue modulus lambda_P (mixing time), the delta^2 local dissimilarity, the gamma-inexactness produc","core_discovery":"The central claim is that a decentralized version of federated averaging can retain the communication efficiency of multiple local updates while avoiding their drift under heterogeneity, by making the updates themselves walk across devices. Formally, with M parallel random-walk trajectories on a connected graph, each trajectory performing K random-walk SGD steps, and a periodic decentralized weighted aggregation that averages the last parameters of the trajectories, the paper proves E[f(w_k)] - f(w*) = O(1/k^{1-q}) for convex L-smooth losses under standard assumptions, for step size eta_k = O(1/k^q) with 1/2 < q < 1. This matches the order of random-walk SGD and is close to centralized SGD's","pith_inferences":["The proof assumes the random-walk trajectory is unbroken across the aggregation step, but the implemented algorithm averages models from M different trajectories; if that assumption fails, the mixing bound of Lemma 6 may not apply as written, and the convergence result is safest when M=1 or when aggregation is infrequent enough for the chain to mix first.","The privacy argument is heuristic—each device sees only its immediate predecessor and successor—so a formal privacy analysis or an audit of trajectory leakage would be a natural testable extension the paper does not provide.","The theoretical results are convex-only; given the empirical gains on deep networks and LSTM, a plausible conjecture is that random-walk exploration reduces drift in non-convex settings as well, but that remains open.","For a fixed communication budget, there should be an optimal combination of number of chains M, walk length K, and graph sparsity; the paper's bounds provide ingredients for such a trade-off but do not optimize it."],"forward_implications":["Under the paper's assumptions, DFedRW's convergence rate is O(1/k^{1-q}), so the communication savings of multiple updates do not cost the asymptotic rate of random-walk SGD.","Accepting partial random-walk lengths means stragglers are not dropped, removing a source of sampling bias and letting system heterogeneity be absorbed without discarding data.","The quantized version pays only an extra bound of order sqrt(d) s from quantization, and Proposition 1 gives a threshold on expected error and bit width below which quantization strictly reduces total communication.","Empirical comparisons indicate the advantage over (D)FedAvg grows with both statistical and system heterogeneity and is largest when data is fully non-IID, pointing the method at realistic federated settings rather than IID benchmarks.","Sparse topologies such as 3-expander and ring graphs preserve accuracy under IID data but degrade in non-IID settings, making graph connectivity a design parameter in the communication-versus-performance trade-off."],"supporting_citations":[{"why":"Supplies the random-walk federated learning approach and the local device-sampling rule used in DFedRW.","marker":"[20]"},{"why":"Gives the O(1/k^{1-q}) convergence framework for Markov-chain gradient descent that Theorem 1 extends.","marker":"[21]"},{"why":"Provides non-asymptotic random-walk SGD bounds and the transition-matrix treatment used in the proofs.","marker":"[22]"},{"why":"Defines the decentralized federated averaging baseline and the idea of quantizing parameter differences, both used in DFedRW and QDFedRW.","marker":"[15]"},{"why":"Contributes the random-walk decentralized optimization method and the aggregation and mixing tools this paper extends.","marker":"[10]"},{"why":"Establishes the decentralized Markov-chain SGD model and the dependence of convergence on topology and mixing time.","marker":"[11]"},{"why":"Introduces the gamma-inexactness definition used to model device compute heterogeneity and straggler contributions.","marker":"[34]"},{"why":"Supplies the delta^2 local dissimilarity measure used to quantify statistical heterogeneity.","marker":"[37]"},{"why":"Provides the unbiased stochastic quantization scheme whose variance bound is used in QDFedRW.","marker":"[41]"}],"fun_headline_variants":["No-server FL via random walk matches SGD convergence","Random-walk FL beats FedAvg on skewed data","Decentralized FL: random walk converges like SGD","Stragglers welcome: random-walk FL converges like SGD","Quantized random-walk FL: lower comm, same convergence"],"cache_read_input_tokens":2688,"weakest_assumption_plain":"The convergence proof hinges on the random-walk trajectory remaining a single continuous Markov chain across the decentralized aggregation step, even though aggregation averages the last models of M parallel chains; if that continuity does not hold, the mixing bound used in the proof does not apply to the algorithm as implemented.","fun_headline_variants_meta":{"raw":{"variants":["No-server FL via random walk matches SGD convergence","Random-walk FL beats FedAvg on skewed data","Decentralized FL: random walk converges like SGD","Stragglers welcome: random-walk FL converges like SGD","Quantized random-walk FL: lower comm, same convergence"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000821,"raw_usage":{"total_tokens":3474,"prompt_tokens":835,"completion_tokens":2639,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":579,"completion_tokens_details":{"reasoning_tokens":2560}},"tokens_in":579,"tokens_out":2639,"duration_ms":17298,"temperature":1.0,"reasoning_tokens":2560,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-05T14:26:07.343825+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"For M=2 chains on a connected graph, run DFedRW with a fixed step size and log the pre-aggregation and post-aggregation models. If the post-aggregation model cannot be reproduced as the state of a single Markov-chain trajectory with the paper's transition matrix, the mixing argument in the proof is not operating on the actual iterates; then check numerically whether the predicted O(1/k^{1-q}) slope holds for M=2 or only for M=1.","supporting_citations":[{"cited_title":"Walk for learning: A random walk approach for federated learning from heterogeneous data,","cited_arxiv_id":null,"evidence_quote":"Supplies the random-walk federated learning approach and the local device-sampling rule used in DFedRW."},{"cited_title":"On markov chain gradient descent,","cited_arxiv_id":null,"evidence_quote":"Gives the O(1/k^{1-q}) convergence framework for Markov-chain gradient descent that Theorem 1 extends."},{"cited_title":"Private weighted random walk stochas- tic gradient descent,","cited_arxiv_id":null,"evidence_quote":"Provides non-asymptotic random-walk SGD bounds and the transition-matrix treatment used in the proofs."},{"cited_title":"Decentralized federated averaging,","cited_arxiv_id":null,"evidence_quote":"Defines the decentralized federated averaging baseline and the idea of quantizing parameter differences, both used in DFedRW and QDFedRW."},{"cited_title":"Walkman: A communication-efficient random-walk algorithm for decentralized optimization,","cited_arxiv_id":null,"evidence_quote":"Contributes the random-walk decentralized optimization method and the aggregation and mixing tools this paper extends."},{"cited_title":"On the decentralized stochastic gradient descent with markov chain sampling,","cited_arxiv_id":null,"evidence_quote":"Establishes the decentralized Markov-chain SGD model and the dependence of convergence on topology and mixing time."},{"cited_title":"Federated optimization in heterogeneous networks,","cited_arxiv_id":null,"evidence_quote":"Introduces the gamma-inexactness definition used to model device compute heterogeneity and straggler contributions."},{"cited_title":"SCAFFOLD: Stochastic controlled averaging for federated learning,","cited_arxiv_id":null,"evidence_quote":"Supplies the delta^2 local dissimilarity measure used to quantify statistical heterogeneity."},{"cited_title":"Qsgd: Communication-efficient sgd via gradient quantization and encoding,","cited_arxiv_id":null,"evidence_quote":"Provides the unbiased stochastic quantization scheme whose variance bound is used in QDFedRW."}],"review_version":1}