{"id":"d91bc0a5-fa85-4312-9da5-6813b3a6f80d","arxiv_id":"2509.08120","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":4.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"A thesis that packages the author's published federated learning work, whose main new theoretical result is an improved complexity bound for error-feedback compression.","lead":"This PhD thesis compiles seven prior papers on federated learning, spanning theory (error feedback, PAGE) and software (simulators, fast backpropagation). The central theoretical contribution replaces a quadratic-mean smoothness constant with an arithmetic-mean version in EF21 error-feedback analysis.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"EF21-W's convergence guarantee is conditioned on exact per-client smoothness constants; estimation error can violate the step-size bound and void the claimed T = O((L + L_AM ξ)/ε) rate.","rationale":"The central theoretical claim — replacing L_QM with L_AM in EF21's communication complexity — is mathematically sound as stated, and I found no internal error in the proof of Theorem 8. The main burden falls on the assumption that the smoothness constants L_i are known exactly, which the reader also identified. This assumption is load-bearing because the algorithm's weights and step size both depend on L_i, and underestimating any L_i can break the step-size condition that the proof relies on. This does not invalidate the theorem, but it limits its practical applicability, which is central to a thesis on optimization methods and software for federated learning. The reader's CONDITIONAL verdict is appropriate; I would not change it. My proposed perturbation test would empirically settle whether the concern is practically significant.","tokens_in":71607,"tokens_out":8437,"duration_ms":87067,"concrete_test":"Construct a synthetic federated problem with known L_i (e.g., quadratic objectives with prescribed Lipschitz constants). Run EF21-W with the exact theoretical step size and with step sizes computed from per-client estimates L_i * (1 + δ_i), where δ_i are random perturbations in [-0.5, 0.5]. Measure iterations to reach E||∇f(x̂)||² ≤ ε. If the perturbed runs diverge or require significantly more iterations than the exact theory predicts (more than, say, 2×), the concern is confirmed. If performance is stable, the assumption is not load-bearing.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorem 8 states the EF21-W step size as γ ≤ 1/(L + L_AM ξ(α)) and the client weights as w_i = L_i / Σ_j L_j. Both quantities require exact knowledge of every L_i. In federated practice, L_i are not given and must be estimated from local data. The proof's Lyapunov argument requires γ² β L_AM² / θ + L γ ≤ 1 (Appendix C3.2). If any L_i is underestimated, the true L_AM is larger than the value used to set γ, so the implemented γ can exceed the threshold and the inequality fails — the contraction no longer holds and the convergence guarantee collapses. Overestimation preserves correctness (γ becomes smaller) but degrades the rate, so the claimed improvement is not robust to typical estimation error. The chapter's experiments use 'theoretical' step sizes but do not report how L_i were obtained or how sensitive the method is to misspecification, leaving the central complexity claim conditional on an unverified assumption.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The dissertation addresses five challenges in Federated Learning (FL) across seven chapters, each a previously published paper. The central theoretical contribution is in Chapter 3, where the author replaces the quadratic mean (L_QM) of client smoothness constants in the EF21 error-feedback method with the arithmetic mean (L_AM), yielding the communication complexity T = O((L + L_AM * xi(alpha))/epsilon) for non-convex smooth objectives. This is achieved through three routes: client cloning, a new weighted algorithm EF21-W (Algorithm 3), and a weighted analysis of the original EF21. The other chapters present FL_PyTorch, a simulation framework; DCGD/PermK/AES, a classical-cryptography approach to private FL; refined PAGE analysis; compressed personalized L2GD; a high-performance FedNL implementation; and BurTorch, a low-latency backpropagation engine. The thesis emphasizes the interplay between theory, systems, and practical implementation, with each chapter containing its own reproducibility appendix.","tokens_in":71817,"tokens_out":5340,"duration_ms":72730,"significance":"If the Chapter 3 result is correct, it is a genuine improvement over the best-known communication complexity for algorithms using contractive compressors, replacing a potentially much larger quadratic-mean constant with the arithmetic mean. The proofs are self-contained and the derivation of the weights w_i = L_i / sum_j L_j is structurally sound. The systems chapters provide substantial engineering contributions, and the thesis explicitly ships reproducibility statements and code links for several chapters. However, the practical applicability claims rest on assumptions that are not stress-tested: exact knowledge of per-client smoothness constants in EF21-W, no sensitivity analysis in the experiments, and performance claims (x1000 speedup, x3500 memory reduction) that are not fully verifiable from the manuscript alone. The significance is therefore real but tempered by the gap between the stated theoretical conditions and the claimed practical readiness.","major_comments":[{"comment":"The central practical claim of Section 3.3 relies on exact knowledge of each L_i to set w_i = L_i / sum_j L_j and gamma <= 1/(L + L_AM * xi(alpha)). The proof in Appendix C3.2 requires the inequality gamma^2 * beta * L_AM^2 / theta + L * gamma <= 1. If L_AM is underestimated, the implemented gamma can violate this bound and the contraction argument collapses. Overestimating preserves correctness but degrades the rate. The experiments report 'theoretical step sizes' but do not state how L_i were obtained or how sensitive the method is to misspecification. This is load-bearing for the thesis's applicability claims, and it conflicts with the thesis's own principle stated in Section 1.2.5 that estimation costs should be accounted for in final evaluation. I recommend adding a sensitivity analysis and discussing practical estimation of L_i.","section":"Chapter 3, Theorem 8 / Algorithm 3"},{"comment":"The improved theory for the original EF21 also assumes knowledge of L_i to set the step size via L_AM and the analysis uses weights w_i = L_i / sum_j L_j in the Lyapunov argument (Appendix D3). The text (Section 3.2.4) suggests that EF21 inherits the L_AM rate automatically for positively homogeneous compressors, but in practice the step size still requires exact smoothness constants. The manuscript does not discuss how practitioners should obtain these constants in federated settings, nor does it analyze the robustness of Theorem 9 to inexact L_i. This is a gap between the stated theoretical improvement and the claimed practical impact.","section":"Chapter 3, Theorem 9"},{"comment":"The performance claims - x1000 wall-clock improvement for FedNL (Section 7.5) and up to x2000/x3500 runtime/memory improvements for BurTorch (Chapter 8, Table 8.1) - are central to the software contributions. The manuscript provides detailed optimization narratives and reproducibility appendices, but the full experimental code is not included in the arXiv submission, and the baselines are compared against a specific reference implementation and specific framework versions. This makes independent verification difficult. Given that the thesis explicitly positions practical implementation as a key contribution, the lack of a complete, self-contained benchmark suite or measurement scripts in the manuscript is a significant gap.","section":"Chapters 7 and 8"}],"minor_comments":[{"comment":"The phrase 'partial partial participation' appears twice (Figures 3.2 caption and text). The intended expression is likely 'partial participation' or 'random client participation'.","section":"Section 3.3"},{"comment":"The title contains a typo: 'Improvemens' should be 'Improvements'.","section":"Table 7.4"},{"comment":"The heading '2-Suboptimal but simple step size rule' is unclear; the '2-' prefix is not explained. Presumably it means the step size is within a factor of 2 of optimal, but this should be stated.","section":"Appendix A3.4"},{"comment":"The condition for choosing s and mu uses both 'mu' and 'nu' with inconsistent notation: the algorithm defines nu, but the condition states (1+s)(1+mu)<1/(1-alpha). This should be unified.","section":"Appendix E3.3, Theorem 13"},{"comment":"Several intermediate lines contain garbled or duplicated symbols (e.g., '\\\\|\\\\nabla f_i(x^{t+1}) -' followed immediately by '\\\\|\\\\nabla f_i(x^t)\\\\|^2\\\\|'). These appear to be formatting errors from the LaTeX conversion; please correct.","section":"Appendix E3.2, Lemma 10 proof"},{"comment":"The phrase 'conically bounded variance' is used but not defined. If this is standard, a reference or definition is needed.","section":"Section 1.5.3, Definition 6"}],"recommendation":"major_revision","confidential_remarks":"This is a dissertation-style manuscript consisting largely of previously published papers. The theoretical core of Chapter 3 is solid, but the practical claims are not fully supported by the manuscript's own experiments because the exact-smoothness assumption is not stress-tested. The performance chapters similarly make strong empirical claims that would benefit from a public, version-controlled benchmark. I also note a high self-citation rate, though the derivations are independently grounded and I do not see circularity in the proofs. The fit with a general ML journal could be questioned, but the synthesis of theory and systems is a strength."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You should know this is a PhD thesis, not a research monograph with a single new result. Each of the seven chapters corresponds to a published paper or preprint by the author and collaborators, and the EF21-W theorems already appear in Richtárik et al., ICLR 2024. That's not necessarily a flaw—a thesis is expected to compile prior work—but it shapes what you can learn here. If you want the new science, read the underlying papers; if you want a coherent retrospective that connects theory to software, this is useful.\n\nWhat it does well: Chapter 3's proof of the EF21-W rate (replacing L_QM with L_AM) is complete and self-contained. The discovery narrative is a nice pedagogical device. The software chapters (7 and 8) document serious engineering: the FedNL speedup is broken down into a plausible chain of optimizations, and BurTorch's reported improvements on small graphs are the kind of claim a competent practitioner can check.\n\nSoft spots. First, the big speedup and memory claims (x1000, x3500) are not independently verifiable from the thesis material alone. There are reproducibility statements but no full code release in the arXiv artifact; a referee should ask for the repository and a minimal reproduction script. Second, the stress-test concern is valid: EF21-W's step size and client weights require exact knowledge of every L_i. If any L_i is underestimated, the proof's Lyapunov inequality can fail and the rate collapses. This is a real limitation, though not fatal—it is standard in this literature to assume smoothness constants for theoretical step sizes. The problem is that the thesis also claims practical applicability, and the experiments use theoretical step sizes without reporting how L_i were obtained or how sensitive the method is to misspecification. The author does flag estimation of unknown constants as a practical concern in Section 1.2.5, but Chapter 3 does not act on that flag. Third, the empirical comparisons in later chapters rely on self-benchmarks; not circular, but the practical gains need external confirmation.\n\nWho is this for? A graduate student learning how to structure a dissertation bridging optimization theory and systems, or a researcher wanting a consolidated reference. It deserves a serious referee if evaluated as a thesis; I would not desk-reject it. My recommendation: send it to review with a request that the author release code/data for the two systems chapters and add a short section in Chapter 3 on estimating or bounding L_i and the effect of misspecification.","headline":"A solid, well-organized PhD thesis that consolidates the author's previously published work; the EF21-W chapter is mathematically sound and the engineering chapters are substantial, but the empirical speedup claims and reliance on known per-client smoothness constants deserve scrutiny.","tokens_in":72289,"tokens_out":3639,"would_cite":false,"duration_ms":43650,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W40","90C26"],"pacs":[],"model":"deepseek-v4-flash","headline":"This thesis proves that error feedback with contractive compressors converges in O((L + L_AM ξ(α))/ε) rounds, replacing the quadratic mean of client smoothness constants with their arithmetic mean.","keywords":["federated learning","error feedback","EF21-W","communication compression","smoothness heterogeneity","nonconvex optimization","distributed training","FedNL"],"falsifier":"Take a non-convex problem with n=1000 clients where one client has smoothness 100 times the others, run EF21 and EF21-W with the Top1 compressor and the theoretical steps from Theorem 8 versus the old bound, and record rounds to reach E‖∇f‖² ≤ ε. If EF21-W's rounds do not follow (L + L_AM ξ(α))/ε, or if perturbing the claimed optimal weights w_i by 10% drives the method to diverge at the theoretical step size, the central claim fails.","tokens_in":71481,"feed_emoji":"🧮","tokens_out":6138,"duration_ms":61150,"temperature":0.7,"pith_summary":"The thesis tackles five challenges in federated learning—heterogeneous data, heterogeneous devices, communication bottlenecks, privacy, and the gap between theory and usable software. Its central theoretical result is that error feedback with contractive compressors (EF21) can be analyzed with the arithmetic mean of per-client smoothness constants instead of the quadratic mean, so heterogeneous smoothness is less costly than previously proven. The mechanism is a smoothness-weighted variant, EF21-W, and a weighted analysis of vanilla EF21; both admit step sizes up to 1/(L + L_AM ξ(α)) and therefore communication complexity O((L + L_AM ξ(α))/ε). The same weighting transfers to stochastic-gradient and partial-participation variants and to Polyak-Łojasiewicz and rare-features settings. Around this theory, the thesis builds practical software: a federated simulation environment, a fast FedNL implementation, and a high-speed CPU backpropagation framework.","feed_headline":"Error feedback now converges with average smoothness, not quadratic","feed_subtitle":"Weighted EF21-W proves fewer rounds suffice when client smoothness varies; theory and benchmarks included.","key_machinery":"The carrying identity is w_i = L_i / Σ_j L_j: with these weights, EF21-W's server update is x^{t+1} = x^t − γ Σ_i w_i g_i^t, and the weighted distortion G^t = Σ_i w_i ‖g_i^t − ∇f_i(x^t)/(n w_i)‖² obeys a contraction whose residual coefficient is L_AM² rather than L_QM². The same weights inserted into the proof for vanilla EF21, via Jensen's inequality on the distortion, deliver the same rate without modifying the algorithm. Client cloning is the discovery route: replicating client i to N_i copies with rescaled functions reduces the quadratic mean to the arithmetic mean; integer cloning frequencies ⌈L_i/L_AM⌉ are a √2-approximation and need at most 2n total clients.","core_discovery":"For minimizing f(x)=1/n Σ f_i(x) under L-smoothness of f and L_i-smoothness of each f_i, the paper proves that EF21—the best-known error-feedback method for contractive compressors—needs only T = O((L + L_AM ξ(α))/ε) iterations to reach E‖∇f(x̂)‖² ≤ ε, where L_AM = (1/n)Σ L_i and ξ(α) depends only on the compressor's contraction parameter. Previously the best bound had L_QM = sqrt((1/n)Σ L_i²) in place of L_AM. The improvement is obtained three ways: by cloning each client N_i times with frequencies ⌈L_i/L_AM⌉ (a √2-approximate optimal scheme), by the weighted algorithm EF21-W with weights w_i = L_i/Σ_j L_j, and by a weighted analysis of unweighted EF21. The proof introduces a weighted gradi","pith_inferences":["If exact L_i are unavailable, the theory suggests an online estimator for w_i could still capture much of the benefit; a testable extension is to replace L_i with running estimates of local gradient Lipschitz constants and measure whether the step-size validity holds.","The equivalence between cloning and weighting hints that the L_AM rate may extend to other biased compressors (RankK, natural compression) and to decentralized topologies where each node's 'clones' are weighted aggregations.","The same weighted-distortion technique could sharpen rates for second-order FL methods like FedNL by replacing worst-case client smoothness with an arithmetic-mean dependence."],"forward_implications":["Communication complexity of EF21-style methods with contractive compressors becomes O((L + L_AM ξ(α))/ε), so heterogeneous smoothness between clients is less harmful than the earlier L_QM bound suggested.","EF21-W permits theoretical step size γ ≤ 1/(L + L_AM ξ(α)), which is larger than the L_QM-based step whenever L_QM > L_AM, yielding fewer communication rounds in the experiments.","The weighted analysis extends to EF21-SGD, EF21-PP, PL functions, and the rare-features regime, so the L_AM improvement is not limited to full-gradient full-participation EF21.","Cloning shows that adding rescaling clients can improve rates: at most 2n virtual clients suffice to get within √2 of the optimal cloning objective.","Experiments on non-convex logistic regression and synthetic linear problems show the largest gains when L_var = L_QM² − L_AM² is large."],"supporting_citations":[{"why":"Defines EF21, the algorithm whose quadratic-mean complexity bound this thesis improves to the arithmetic mean.","marker":"(Richtárik et al., 2021a)"},{"why":"Supplies the EF21-SGD and EF21-PP variants and their stochastic-gradient analysis framework, which EF21-W-SGD and EF21-W-PP extend to weighted updates.","marker":"(Fatkhullin et al., 2021)"},{"why":"Provides the Natural compressor, an example that is contractive but not positively homogeneous, showing the improved analysis of vanilla EF21 does not need homogeneity.","marker":"(Horváth et al., 2019)"},{"why":"The descent lemma used in the convergence proofs for EF21-W and the weighted EF21 analysis.","marker":"(Li et al., 2021a)"},{"why":"The rare-features regime analysis that the weighted technique refines in Section H3.","marker":"(Richtárik et al., 2023)"},{"why":"Introduces the original error-feedback mechanism that EF21 modernizes, situating the paper's object of study.","marker":"(Seide et al., 2014)"}],"fun_headline_variants":["EF21 converges with average smoothness, not quadratic","Weighted EF21 cuts rounds using average smoothness","Average smoothness tightens error feedback convergence","Error feedback: fewer rounds with L_AM, not L_QM","EF21-W: average smoothness beats quadratic mean"],"cache_read_input_tokens":2688,"weakest_assumption_plain":"The step size and the weights in EF21-W require exact knowledge of every client's smoothness constant L_i; if these constants are estimated or tuned imperfectly, the advertised step size bound and convergence complexity no longer hold.","fun_headline_variants_meta":{"raw":{"variants":["EF21 converges with average smoothness, not quadratic","Weighted EF21 cuts rounds using average smoothness","Average smoothness tightens error feedback convergence","Error feedback: fewer rounds with L_AM, not L_QM","EF21-W: average smoothness beats quadratic mean"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000234,"raw_usage":{"total_tokens":1388,"prompt_tokens":856,"completion_tokens":532,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":600,"completion_tokens_details":{"reasoning_tokens":454}},"tokens_in":600,"tokens_out":532,"duration_ms":5629,"temperature":1.0,"reasoning_tokens":454,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-04T21:14:35.054982+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a non-convex problem with n=1000 clients where one client has smoothness 100 times the others, run EF21 and EF21-W with the Top1 compressor and the theoretical steps from Theorem 8 versus the old bound, and record rounds to reach E‖∇f‖² ≤ ε. If EF21-W's rounds do not follow (L + L_AM ξ(α))/ε, or if perturbing the claimed optimal weights w_i by 10% drives the method to diverge at the theoretical step size, the central claim fails.","supporting_citations":[],"review_version":1}