{"id":"456f2ccf-ec04-40e6-b819-118fde41449c","arxiv_id":"2412.02781","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"New clipped federated methods with local steps and random reshuffling are proven to converge under (L0,L1)-smoothness, recovering known rates when L1=0.","lead":"This paper proposes three new federated learning algorithms that use local steps, random reshuffling of data, and server-side gradient clipping, and it proves convergence bounds for them under a generalized smoothness assumption that is more realistic for deep learning. The work matters because it extends federated learning theory to a setting where standard smoothness fails, which is common in practice.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorems' stepsize conditions require oracle quantities (L0, L1, max local gradient norms at every sync point, delta0, Delta*), and the pseudogradient stepsize used in the experiments is not covered by the proofs; Appendix F explicitly omits its analysis.","rationale":"I read the paper in good faith. The theoretical core is a substantial and mostly careful extension of local-step and reshuffling methods to (L0,L1)-smooth federated optimization, and the rates recover known standard-smooth rates in the L1=0 limit. The proofs are detailed, and the paper does not rely on data homogeneity, bounded variance, or cosine relatedness. My concern is not about algebraic correctness of the proofs under the stated stepsize choices; it is about whether those choices define a runnable algorithm. The reader's weakest_assumption identified exactly this issue: the stepsize conditions in Theorems 1-4 depend on quantities that are not available to the practitioner, and the implementations in the experiments use a pseudogradient heuristic not covered by the theorems. The paper's own Appendix F confirms the mismatch: it says the practical version uses g_p/g_t for the global stepsize and that the theoretical analysis for this version was not included. Appendix E gives a partial bridge, but for the stochastic reshuffling methods the stepsize gamma_t becomes correlated with g_t, and the conditional-expectation argument in the proofs treats gamma_t as deterministic given x_t. That gap is load-bearing for the claim that the experimentally tested methods are the same methods with proven guarantees. This does not overturn the paper's theoretical contribution, but it does justify the reader's CONDITIONAL verdict: the guarantee is for an algorithm whose stepsize protocol is specified only via existence conditions with oracle-dependent constants, and the actually deployed variant is not proven. I therefore see no reason to move the verdict; the concern lands but is already reflected in the conditional assessment.","tokens_in":68202,"tokens_out":18453,"duration_ms":180218,"concrete_test":"Re-derive the proof of Theorem 3 (Appendix C.1, inequality (13)) for Algorithm 2 with the experimental stepsize gamma_t = 1/(c0+c1||g_t||), where g_t = (1/M) sum_m (x_t - x^m_{t,N})/(alpha_t N) depends on the random permutation pi_t. Verify whether the conditional expectation E[f(x_{t+1})|x_t] can still be bounded using only the uniform bound ||g_t|| <= ||grad f(x_t)|| + delta from Appendix E, i.e., whether the correlation between gamma_t and ||g_t||^2 is controlled. If the proof requires additional assumptions or a different choice of c0,c1, then Appendix E's conclusion that 'all our theory works' for pseudogradient stepsizes is not established.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim requires that the proposed methods, as written, converge under (L0,L1)-smoothness. Theorems 1-4 impose stepsize conditions that are not implementable from information available to the server. For example, Theorem 1 requires alpha_p <= min{1/(2H a_p), 1/(c a_p) sqrt(hat_a_p/a_p)} and gamma_p in [zeta/hat_a_p, 1/(4 hat_a_p)], with hat_a_p = L0 + L1||grad f(hat_x_{t_p})|| and a_p = L0 + L1 max_m ||grad f_m(hat_x_{t_p})||. The pseudocode only says 'choose small local stepsizes ... so that' these bounds hold, but no procedure is given to compute a_p or to set c0,c1 from L0,L1 without oracle knowledge. Corollaries additionally require delta0, Delta*, and T. More seriously, Appendix F states that the experiments replace the global stepsize's full gradient with the pseudogradient g_p/g_t, and that the analysis for this 'practical' version was deliberately not included. Appendix E attempts to justify this replacement by showing ||g_p|| is within delta of ||grad f(hat_x_{t_p})|| for small alpha_p, but it does not re-derive the descent lemmas. For CLERR and Clipped RR-CLI, gamma_t becomes a random variable correlated with g_t through the random permutation, so the conditional-expectation step E[f(x_{t+1})|x_t] <= f(x_t) - (gamma_t/4)||grad f(x_t)||^2 + ... with a deterministic gamma_t is no longer valid. Thus, the proved guarantees apply to an implementation that is not run, and the run implementation lacks a proof.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes three federated optimization algorithms for non-convex objectives satisfying the generalized (L0,L1)-smoothness condition: Clip-LocalGDJ (Algorithm 1), CLERR (Algorithm 2), and Clipped RR-CLI (Algorithm 3). The methods combine local steps, random reshuffling, partial client participation, and server-side gradient clipping. The main theorems (Theorems 1-4) give convergence rates for the non-convex setting, and additional theorems in the appendices cover the Polyak-Lojasiewicz case. The paper claims these are the first such results without restrictive assumptions such as data homogeneity, bounded variance, or cosine relatedness, and the rates recover standard smooth rates when L1=0. Experiments on a synthetic shifted-fourth-order problem, ResNet-18 on CIFAR-10, and logistic regression datasets are reported in support of the theory.","tokens_in":68571,"tokens_out":5657,"duration_ms":61845,"significance":"If the theorems are correct as stated with their full hypotheses, the paper fills a genuine gap: it extends federated learning methods with local steps, random reshuffling, and partial participation to (L0,L1)-smooth non-convex problems without imposing the homogeneity or variance assumptions used in prior work. The recovery of known L-smooth rates when L1=0 is a useful consistency check and is not a circular derivation from the target result. The analysis follows established proof templates and the appendix contains detailed derivations. However, the practical impact is currently limited by two gaps: the stepsize conditions in the theorems require oracle quantities that are not available to the server, and the experiments run a version of the algorithms whose analysis is explicitly omitted. These issues are fixable but need to be addressed before the claims can be accepted as stated.","major_comments":[{"comment":"The convergence theorems analyze Algorithms 1-3 with a global stepsize of the form 1/(c0+c1||grad f(x_t)||), where grad f is the full gradient. The experiments, however, replace this by the pseudogradient g_p (Algorithm 1) or g_t (Algorithms 2 and 3), as Appendix F explicitly states. Appendix F further says that the theoretical analysis of this practical version was deliberately not included. Appendix E only shows that ||g_p|| is close to ||grad f(hat x_{t_p})|| for small local stepsizes; it does not re-derive the descent lemmas used in Theorems 1-4. In particular, for CLERR and Clipped RR-CLI the stepsize becomes a random variable that is correlated with the random permutation through g_t, so the conditional-expectation step E[f(x_{t+1})|x_t] with a deterministic gamma_t is no longer justified. As written, the paper proves convergence for an algorithm that is not the one run in the experiments, and the experimental support for the theory is therefore incomplete.","section":"Section 4 and Appendix F"},{"comment":"The stepsize conditions in the theorems require quantities that are not available to the server in a federated setting. For example, Theorem 1 requires alpha_p to be bounded in terms of a_p = L0 + L1 max_m ||grad f_m(hat x_{t_p})||, and gamma_p to lie in an interval defined by hat a_p = L0 + L1 ||grad f(hat x_{t_p})||. The server would need to know L0, L1, and the maximum local gradient norm over all clients at every synchronization point, as well as delta0, Delta*, H, and P. The pseudocode only says 'choose small local stepsizes' without giving a procedure for computing or estimating these quantities. If these quantities are not available, the theorems do not apply to a practical implementation. The paper should state explicitly that the stepsizes are theoretical, or provide a procedure for setting them from computable quantities.","section":"Section 4, Theorems 1-4"},{"comment":"The statement of Corollary 4 says that if T >= 72 delta0 / (zeta epsilon) and gamma_t, eta_t are small enough, then the method reaches epsilon accuracy. The proof in Appendix D.1, however, requires T >= max{72 delta0 / (zeta epsilon), 12 Delta* / (zeta epsilon), 6 Delta* / (zeta epsilon)} and precise upper bounds on eta_t and gamma_t that depend on these quantities. As stated, the corollary omits the dependence on Delta* and Delta*, so if these constants are large the claimed iteration complexity is an underestimate. This is a load-bearing issue for the partial-participation result and should be corrected.","section":"Section 4, Corollary 4"}],"minor_comments":[{"comment":"The main-text statement of Theorem 1 does not include the upper bound on alpha_p that is imposed in the appendix (alpha_p <= min{1/(2H a_p), 1/(c a_p) sqrt(hat a_p / a_p)} with c >= sqrt(P)). The main text says only 'choose small local stepsizes,' which is too vague for the theorem to be self-contained; please include the condition or provide an explicit reference to Appendix B.1.","section":"Section 4, Theorem 1"},{"comment":"The experiments are run over 3 or 10 random seeds, but Figures 2, 6, 7, and 8 show only mean curves without error bars or shaded regions. Adding variance information would make the comparisons between methods more convincing.","section":"Section 5.1.1 and Appendix F"},{"comment":"The abbreviation 'CRR-CLI' is used in Figure 4 and in Appendix F.3, while the method is named 'Clipped RR-CLI' in the main text. Please use a single consistent name for Algorithm 3.","section":"Section 5.3 and Appendix F.3"},{"comment":"The sentence 'Although, we decided not to include it to keep the presentation more concise' contains a typo; 'Although' should be 'However'.","section":"Appendix F, first paragraph"},{"comment":"The contribution bullet says the results are 'tight,' but the paper only shows recovery of known rates in the special case L1=0; no lower bounds are established for the (L0,L1)-smooth setting. Consider softening the claim to avoid suggesting optimality in the broader class.","section":"Section 1.1"}],"recommendation":"major_revision","confidential_remarks":"This is a theory paper with a clear and mostly correct-seeming proof structure. The main reasons for major revision are the gap between the analyzed and implemented algorithms and the inaccurate statement of Corollary 4. The stepsize implementability issue is also significant and should be discussed honestly, though it may be acceptable if framed as a theoretical guarantee under oracle knowledge. I do not see a basis for rejection: the central convergence claims are plausible and follow established techniques. The authors should either provide an analysis of the pseudogradient version used in experiments or clearly mark those experiments as heuristics and adjust the corresponding claims in the abstract and introduction."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Punchline: the theory is largely solid, but the experiments run a heuristic variant the proofs do not cover, and the stepsize conditions need oracle information.\n\nWhat's new: three algorithms—Clip-LocalGDJ, CLERR, Clipped RR-CLI—that combine local steps, random reshuffling, and partial participation under (L0,L1)-smoothness without extra restrictive assumptions. The analysis extends standard proof templates and recovers known rates when L1=0. The PL results are new for this setting. The writing is clear, and the appendix is thorough. The synthetic experiments reasonably illustrate that clipping once per epoch beats per-step clipping.\n\nThe main soft spot is the algorithm-theory gap. Appendix F explicitly says the practical version replaces the full gradient in the global stepsize with the pseudogradient, and that its analysis was deliberately omitted. Appendix E shows ||gp|| is close to ||∇f|| for small inner stepsizes, but that does not re-establish the descent lemmas. For CLERR and Clipped RR-CLI, γt becomes a random variable correlated with gt through the permutation, so the conditional-expectation argument with a deterministic γt no longer applies. This is a real gap, though it does not invalidate the theoretical results for the analyzed variants. The experiments would be more convincing if the heuristic were labeled as such and the claims softened.\n\nAlso, the stepsize conditions require L0, L1, and max local gradient norms at every sync point; the pseudocode gives no procedure for estimating them. That is common in this literature but limits practical applicability. Corollary 4 omits the dependence on the heterogeneity gaps Δ⋆ and ∆⋆ in the main text, though the appendix proof includes it.\n\nWho this is for: researchers working on federated optimization theory and generalized smoothness. The paper deserves a serious referee. I would send it to review with a request to address the mismatch, either by proving the pseudogradient version or by explicitly framing the experiments as heuristics.","headline":"Solid theory, shaky bridge to experiments: the paper proves first convergence rates for local-step FL with reshuffling under (L0,L1)-smoothness, but the implemented pseudogradient stepsize is not covered by the proofs.","tokens_in":69138,"tokens_out":3433,"would_cite":true,"duration_ms":36649,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C26","90C30","68W15"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves convergence of local-step federated methods under (L0,L1)-smoothness without data-homogeneity, bounded-variance, or cosine-relatedness assumptions.","keywords":["federated learning","local steps","random reshuffling","generalized smoothness","gradient clipping","partial participation","Polyak-Lojasiewicz condition","non-convex optimization"],"falsifier":"On a two-client $(L_0,L_1)$-smooth problem where one client's local gradients are far larger than the other's, compute $a_p = L_0 + L_1 \\max_m \\|\\nabla f_m(\\hat x_{t_p})\\|$ along the trajectory and check whether the tuned inner stepsize satisfies $\\alpha_p \\le 1/(2H a_p)$ at every epoch; because $a_p$ is not observable to the user, a run that converges while violating this condition would show the theorem's sufficient conditions are not the operative mechanism, while a run that diverges under the condition would refute the claimed guarantee for the implemented method.","tokens_in":68015,"feed_emoji":"🔄","tokens_out":10733,"duration_ms":102075,"temperature":0.7,"pith_summary":"Modern neural-network losses are often not $L$-smooth: the Hessian norm grows with the gradient norm. This paper claims that federated optimization with local steps can nevertheless be analyzed under the resulting generalized $(L_0,L_1)$-smoothness by combining small client stepsizes, larger server stepsizes, and gradient clipping applied once to the aggregated update. It proposes three methods—Clip-LocalGDJ, CLERR, and Clipped RR-CLI—and proves non-convex convergence rates for all three, plus linear rates under the Polyak–Łojasiewicz condition, without the data-homogeneity, bounded-variance, or cosine-relatedness assumptions that earlier federated analyses of generalized smoothness required. The rates reduce to the known standard-smooth rates when $L_1 = 0$, which is part of the paper's evidence that its conditions are the right generalization.","feed_headline":"Clipped federated local steps converge under generalized smoothness","feed_subtitle":"New rates cover random reshuffling and partial participation without homogeneity or variance assumptions.","key_machinery":"The load-bearing object is the generalized-smoothness coefficient $\\hat a_p = L_0 + L_1\\|\\nabla f(\\hat x_{t_p})\\|$ (with local variants $a_p$ and $\\tilde a_t$), paired with a server stepsize constrained to the interval $\\gamma_p \\in [\\zeta/\\hat a_p, 1/(4\\hat a_p)]$ and a pseudogradient $g_p = \\frac{1}{\\alpha_p(v-t_p)}(\\hat x_{t_p} - \\frac1M\\sum_m x^m_{t_{p+1}-1})$ formed from the local iterates. This coupling acts as smoothed clipping: when the gradient is large, the server step is automatically short, while the small client stepsize $\\alpha_p \\le 1/(2H a_p)$ bounds client drift. The proofs use a descent lemma for $(L_0,L_1)$-smooth functions and a deviation bound showing the average squared distance of local iterates from the synchronization point is at most $O((H-1)^2 a_p^3 \\alpha_p^2(\\delta_p+\\Delta^\\star))$; the argument then splits each epoch according to whether $\\|\\nabla f\\|$ is below or above $L_0/L_1$, which is what converts the stationarity measure into the stated rates. For symmetric smoothness, the proof additionally controls the exponential factor in the descent inequality by an induction that bounds all local gradient norms along the epoch.","core_discovery":"On the paper's own terms, the central claim is that local-step federated methods can converge under $(L_0,L_1)$-smoothness without extra restrictive assumptions, as long as the server takes a clipped, larger step along the averaged pseudogradient while clients take small steps. Concretely, Theorem 1 bounds $\\min_{0\\le p\\le P-1} \\frac{\\zeta}{8}\\min\\{\\|\\nabla f(\\hat x_{t_p})\\|^2/L_0, \\|\\nabla f(\\hat x_{t_p})\\|/L_1\\}$ by a term of order $O(L_0\\delta_0/(\\zeta \\varepsilon))$ for Clip-LocalGDJ, and Corollary 1 converts this into an iteration complexity matching standard LocalGD when $L_1=0$. Theorems 3 and 4 give the analogous guarantees for CLERR (local steps with random reshuffling) and Clipped RR-CLI (local steps, reshuffling, and partial participation); for each method the paper also proves a linear rate under the Polyak–Łojasiewicz condition, recovering the standard $O((L_0/\\mu)\\ln(2\\delta_0/\\varepsilon))$ rate when $L_1=0$. These are the first results of this kind for partial participation under generalized smoothness, according to the paper's literature survey.","pith_inferences":["If $(L_0,L_1)$-smoothness is the right model for deep-network losses, the paper's design principle suggests that federated systems should spend their clipping budget on the aggregated server step rather than on every local gradient; the theory proves this for the once-per-epoch variants, but a head-to-head comparison with per-step clipping under the same assumptions would test whether the design p","Because the theorems' stepsize conditions involve quantities unavailable to the user (the full gradient and the largest local gradient norm at each synchronization point), an adaptive scheme that estimates these quantities online, or a parameter-free version, is the natural next step before the guarantees can be applied directly to the implemented algorithms.","The same two-case 'small gradient / large gradient' proof technique could plausibly extend to local methods with communication compression or incomplete local epochs, which the paper itself lists as future work.","The experimental heuristic of replacing $\\nabla f(x_t)$ by the pseudogradient $g_t$ in the server stepsize is covered only approximately by the appendix's perturbation argument; a full proof for that practical variant would close the gap between the implemented and the analyzed methods."],"forward_implications":["For non-convex $(L_0,L_1)$-smooth distributed problems, Clip-LocalGDJ requires $O(L_0\\delta_0/(\\zeta\\varepsilon))$ synchronization epochs to reach the generalized stationarity measure $\\min\\{\\|\\nabla f\\|^2/L_0, \\|\\nabla f\\|/L_1\\}\\le\\varepsilon$, matching the standard LocalGD rate when $L_1=0$.","CLERR gives a random-reshuffling convergence rate for generalized smooth objectives that does not assume bounded variance or cosine relatedness, under the paper's claims.","Clipped RR-CLI extends the guarantee to partial participation of clients, with a rate that again becomes $O(L_0\\delta_0/(\\zeta\\varepsilon))$ when the inner stepsizes are small.","Under the Polyak–Łojasiewicz condition, all three methods converge linearly with complexity $O(L_0/\\mu \\ln(2\\delta_0/\\varepsilon))$ in the $L_1=0$ limit, and the theorem shows a large-gradient phase of at most $64\\delta_0 L_1^2/(\\mu\\zeta)$ epochs before the linear decay begins.","The results indicate that clipping once per epoch, rather than at every local step, is sufficient in theory for generalized smoothness, and the paper's synthetic experiments support that design choice."],"supporting_citations":[{"why":"Introduces the $(L_0,L_1)$-smoothness condition and the clipping rationale that the new methods adopt.","marker":"Zhang et al. (2020b)"},{"why":"Supplies the descent lemmas and symmetric-smoothness inequalities used in the proofs.","marker":"Chen et al. (2023)"},{"why":"Provides the random-reshuffling analysis and the lemma converting the recurrences into rates.","marker":"Mishchenko et al. (2020)"},{"why":"Is the RR-CLI base algorithm that Clipped RR-CLI extends with clipping.","marker":"Malinovsky et al. (2023a)"},{"why":"Introduces the server-side stepsize and jumping technique plus the sampling lemma used for random reshuffling.","marker":"Malinovsky et al. (2022)"},{"why":"Gives the LocalGD rate that is recovered when $L_1=0$.","marker":"Koloskova et al. (2020)"},{"why":"Previous LocalGD analysis under $(L_0,L_1)$-smoothness that relied on data homogeneity; the paper removes that assumption.","marker":"Liu et al. (2022)"},{"why":"Earlier local-steps-with-partial-participation analysis under $(L_0,L_1)$-smoothness that lacks reshuffling and adds heterogeneity assumptions.","marker":"Crawshaw et al. (2024a)"},{"why":"Previous Adam-with-random-reshuffling analysis under bounded variance, an assumption the paper avoids.","marker":"Wang et al. (2024)"},{"why":"Clipped incremental-gradient analysis under cosine relatedness, an assumption the paper avoids.","marker":"Qian et al. (2021)"}],"fun_headline_variants":["Clipped local steps converge for rugged non-convex federated learning","Random reshuffling plus clipping handles generalized smoothness","Federated learning converges under relaxed smoothness assumptions","Clipped local steps conquer non-smooth federated landscapes","Local steps and reshuffling tame generalized smoothness"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"For the proved rates to apply, stepsizes must be set using the exact global gradient and the largest local gradient norm among all clients at every synchronization point, values a federated user would not have; the implemented algorithms instead use a pseudogradient heuristic that the theorems do not cover.","fun_headline_variants_meta":{"raw":{"variants":["Clipped local steps converge for rugged non-convex federated learning","Random reshuffling plus clipping handles generalized smoothness","Federated learning converges under relaxed smoothness assumptions","Clipped local steps conquer non-smooth federated landscapes","Local steps and reshuffling tame generalized smoothness"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000592,"raw_usage":{"total_tokens":2805,"prompt_tokens":1005,"completion_tokens":1800,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":621,"completion_tokens_details":{"reasoning_tokens":1720}},"tokens_in":621,"tokens_out":1800,"duration_ms":13891,"temperature":1.0,"reasoning_tokens":1720,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T23:06:55.879334+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"On a two-client $(L_0,L_1)$-smooth problem where one client's local gradients are far larger than the other's, compute $a_p = L_0 + L_1 \\max_m \\|\\nabla f_m(\\hat x_{t_p})\\|$ along the trajectory and check whether the tuned inner stepsize satisfies $\\alpha_p \\le 1/(2H a_p)$ at every epoch; because $a_p$ is not observable to the user, a run that converges while violating this condition would show the theorem's sufficient conditions are not the operative mechanism, while a run that diverges under the condition would refute the claimed guarantee for the implemented method.","supporting_citations":[],"review_version":1}