SCAFFOLD under Hessian Similarity: Sharp Convergence Rates

Zhirayr Tovmasyan; Slavomír Hanzely; Egor Shulgin; Peter Richtárik; Sebastian U. Stich

cs.LGOct 26, 2026

SCAFFOLD under Hessian Similarity: Sharp Convergence Rates

Authors: Zhirayr Tovmasyan, Slavomír Hanzely, Egor Shulgin, Peter Richtárik, Sebastian U. Stich

Organizations: King Abdullah University of Science and Technology (KAUST) · CISPA Helmholtz Center for Information Security · Mohamed bin Zayed University of Artificial Intelligence (MBZUAI)

Abstract

One of the main challenges of federated learning is heterogeneous data split among the clients, leading to biased local updates called client drift. The SCAFFOLD algorithm (Karimireddy et al., 2020) corrects client drift with control variates, but its relation to the similarity of client data is not yet fully understood: the original similarity-based guarantees cover only quadratics with a stronger second-order similarity assumption, and a follow-up weakly convex analysis (Luo et al., 2025) obtains a $\sqrt{Lδ}$ dependence for $L$ -smooth losses with averaged Hessian similarity $δ$ . We analyze SCAFFOLD with minibatch-based control variates and establish linear dependence on Hessian similarity beyond quadratics, for both convex and nonconvex objectives. In particular, for convex objectives with exact gradients, $R$ SCAFFOLD rounds with $K$ local steps lead to an objective gap of order $(L/K+δ)D_0^2/R$ , where $D_0$ is the initial distance to a minimizer. When $K=Θ(L/δ)$ , it improves the minibatch SGD rate by a factor $Θ(L/δ)$ . For nonconvex objectives, we prove an analogous stationarity guarantee under uniform Hessian similarity for a client-selection variant. In both settings, we extend these guarantees to stochastic gradients and prove matching lower bounds for the analyzed methods with constant local stepsizes. We also show that, under partial participation, even identical clients need not obtain the full communication benefit of additional local steps.

Figures & tables

Method	Communication rounds	Stochastic gradient evaluations a	Exact gradient evaluations b
Minibatch SGD ( Woodworth et al., 2020a, )	$\dfrac{LD_{0}^{2}}{\varepsilon}$	$\dfrac{LD_{0}^{2}}{\varepsilon}+\dfrac{\sigma^{2}D_{0}^{2}}{N\varepsilon^{2}}$	$0$
SCAFFOLD, Option II ( Karimireddy et al.,, 2020 , Theorem III)	$\dfrac{LD_{0}^{2}}{\varepsilon}$	$\dfrac{LD_{0}^{2}}{\varepsilon}+\dfrac{\sigma^{2}D_{0}^{2}}{N\varepsilon^{2}}$	$0$
FedRed-SGD ( Jiang et al., 2024a, , Theorem 9)	$\dfrac{\delta D_{0}^{2}}{\varepsilon}$	$\dfrac{LD_{0}^{2}}{\varepsilon}+\dfrac{\sigma^{2}D_{0}^{2}}{\varepsilon^{2}}$	$\dfrac{\delta D_{0}^{2}}{\varepsilon}$
S-DANE with SGD ( Jiang et al., 2024b, , Corollary 21)	$\dfrac{\delta D_{0}^{2}}{\varepsilon}$	$\dfrac{LD_{0}^{2}}{\varepsilon}+\dfrac{L\sigma^{2}D_{0}^{2}}{\delta\varepsilon^{2}}$	$\dfrac{\delta D_{0}^{2}}{\varepsilon}$
This work ( $B=K$ )	$\dfrac{\delta D_{0}^{2}}{\varepsilon}$	$\dfrac{LD_{0}^{2}}{\varepsilon}+\dfrac{\sigma^{2}D_{0}^{2}}{\varepsilon^{2}}$	$0$

Table 1: Comparison of communication and computation complexities of stochastic federated learning methods under full participation for achieving

\mathbb{E}[f(\widehat{x})]-f^{\star}\leq\varepsilon

, where

0<\varepsilon\leq\delta D_{0}^{2}

. We assume that the local objectives are convex and

L

-Lipschitz smooth ( Assumption 1 ), and satisfy

\delta

-averaged Hessian similarity ( Assumption 3 ),

0<\delta\leq L

. We report upper bounds for the non-accelerated implementations with appropriately chosen number of local steps and minibatch sizes (see Appendix A.11 for details). Computation is measured by the number of stochastic gradient evaluations per client across all communication rounds, including initialization. Constants and logarithmic factors are suppressed. Our analysis improves SCAFFOLD’s communication complexity from order

LD_{0}^{2}/\varepsilon

\delta D_{0}^{2}/\varepsilon

, matching that of regularized methods without requiring exact-gradient evaluations.

Figure 1: Number of communication rounds deterministic SCAFFOLD needs to reach

f(\bar{x}^{R})-f^{\star}\leq 10^{-5}

. Dashed curves use theoretical stepsizes, and solid curves use tuned stepsizes. Our theory predicts that increasing the number of local steps reduces communication until client similarity limits further gains.

Figure 2: Server test accuracies on CIFAR-10 with

K=40

for the IID (left) and Dirichlet (right) partitions, reporting means

\pm

standard deviations over three runs. Both SCAFFOLD variants outperform minibatch SGD on the IID partition, but this advantage disappears on the heterogeneous partition.

Appendix figures & tables9 assets

Supplementary material from the paper’s appendix.

Appendix

Method / assumptions	Optimization term	Stochastic terms
Minibatch SGD ( Luo et al.,, 2025 , Lemma 1) No similarity assumption; stochastic	$\displaystyle\frac{LF_{0}}{R}$	$\displaystyle\sigma\sqrt{\frac{LF_{0}}{NKR}}$
SCAFFOLD a ( Karimireddy et al.,, 2020 ) No similarity assumption; stochastic	$\displaystyle\frac{LF_{0}}{R}$	$\displaystyle\sigma\sqrt{\frac{LF_{0}}{NKR}}$
SCAFFOLD b ( Luo et al.,, 2025 ) Averaged similarity; stochastic	$\displaystyle\left(\frac{L}{K}+\sqrt{L\delta}+\rho\right)\frac{F_{0}}{R}$	$\displaystyle\sigma\sqrt{\frac{LF_{0}}{NKR}}+\left(\frac{L^{2}F_{0}^{2}\sigma^{2}}{KR^{2}}\right)^{1/3}$
FedRed-SGD c ( Jiang et al., 2024a, ) Uniform similarity; exact controls	$\displaystyle\frac{\bar{\delta}F_{0}}{R}$	$\displaystyle\sigma\sqrt{\frac{\bar{\delta}F_{0}}{R}}$
CE-LSGD d ( Patel et al.,, 2022 ) Uniform similarity; two-point oracle	$\displaystyle\left(\frac{\bar{L}}{\sqrt{K}}+\bar{\delta}\right)\frac{F_{0}}{R}$	$\displaystyle\frac{\sigma^{2}}{NKR}+\left(\frac{\sigma\bar{L}F_{0}}{NKR}\right)^{2/3}$
This work ( $B=K$ ) Uniform similarity; stochastic	$\displaystyle\left(\frac{L}{K}+\bar{\delta}\right)\frac{F_{0}}{R}$	$\displaystyle\sigma\sqrt{\frac{LF_{0}}{KR}}$

Appendix

Table 2: Nonconvex convergence guarantees under full participation. The sum of the last two columns bounds

\mathbb{E}\left\lVert\nabla f(\widehat{x})\right\rVert^{2}

at the specified output, up to universal constants. Here

L=L_{\mathrm{loc}}

F_{0}=f(x^{0})-f_{\inf}

, and

\sigma^{2}

bounds within-client gradient variance. The parameters

\delta

and

\bar{\delta}

denote averaged and uniform Hessian similarity, respectively. For minibatch SGD,

K

is the per-client batch size; otherwise it describes local work, subject to the notes below.

Figure 3: Effective stepsizes

\alpha=K\eta_{\ell}

for the quadratic experiment in Figure 1 . Dashed curves use the theoretical rule; solid curves show the tuned choices.

Partition	Method	$K$	Stepsize	Test accuracy (%)
IID	SCAFFOLD averaging	10	$0.1$	$71.68\pm 1.65$
	SCAFFOLD selection	10	$0.01$	$53.14\pm 3.18$
	Minibatch SGD	10	$0.01$	$37.25\pm 3.74$
	SCAFFOLD averaging	40	$0.2$	$88.54\pm 0.62$
	SCAFFOLD selection	40	$0.01$	$78.73\pm 0.51$
	Minibatch SGD	40	$0.01$	$35.88\pm 2.25$

Appendix

Table 3: Selected constant stepsizes and test accuracy at round

400

. Accuracies are percentages, reported as mean

\pm

sample standard deviation over three runs.

Figure 4: Additional CIFAR-10 results for

K=10

: server test accuracy versus communication rounds (left) and gradient-sample evaluations, including controls (right). Curves show means and bands show sample standard deviations over three runs. Figure 2 and Figure 6 give the corresponding

K=40

results.

Figure 5: Server training loss for

K=10

(left) and

K=40

(right), evaluated without augmentation on the fixed

5{,}000

-image training subset. Curves show means and bands show sample standard deviations over three runs.

Figure 6: CIFAR-10 with

K=40

: server test accuracy versus gradient-sample evaluations, including controls, for IID (left) and Dirichlet (right) partitions. Curves show means and bands show sample standard deviations over three runs.

Figure 7: Averaged and uniform gradient disagreement along the

K=40

trajectories, using

256

examples per client and relative radius

10^{-2}

. Curves show means of the three-direction maxima; bands show sample standard deviations over three runs. Vertical axes are logarithmic.

Partition	Method	$\widehat{\delta}_{\mathrm{avg}}$	$\widehat{\delta}_{\max}$	$\widehat{L}_{\mathrm{loc}}$	$\widehat{L}_{g}$
IID	Averaging	$0.049\pm 0.003$	$0.057\pm 0.003$	$0.061\pm 0.003$	$0.017\pm 0.001$
	Selection	$0.338\pm 0.017$	$0.363\pm 0.019$	$0.406\pm 0.029$	$0.164\pm 0.026$
	Minibatch SGD	$0.860\pm 0.036$	$0.884\pm 0.036$	$1.013\pm 0.018$	$0.461\pm 0.045$
Dirichlet $0.1$	Averaging	$3.322\pm 0.551$	$5.642\pm 0.893$	$7.715\pm 2.328$	$2.583\pm 1.314$
	Selection	$2.745\pm 0.156$	$4.519\pm 0.274$	$5.567\pm 0.687$	$1.688\pm 0.610$
	Minibatch SGD	$1.434\pm 0.021$	$2.680\pm 0.168$	$2.947\pm 0.261$	$0.513\pm 0.053$

Appendix

Table 4: Gradient-difference measurements at round

400

, with relative radius

10^{-2}

and

256

examples per client. Values are means

\pm

sample standard deviations over three runs.

Figure 8: Similarity and global sensitivity relative to local sensitivity at round

400

, using relative radius

10^{-2}

and

256

examples per client. Bars show mean per-seed ratios and error bars show sample standard deviations over three runs. The dashed line represents

\widehat{L}_{\mathrm{loc}}/\widehat{L}_{\mathrm{loc}}=1

Federated Learning

Federated learning trains shared models across data holders without requiring them to pool their raw data.

See all 951 papers

Aug 26, 2026

How Edge of Stability Hinders SCAFFOLD in Federated Optimization

In federated learning, it is well known that heterogeneous data can (in theory) slow down optimization, and much effort has been directed at designing optimization algorithms that are unaffected by data heterogeneity, such as the SCAFFOLD algorithm. Yet, despite strong theoretical guarantees, SCAFFOLD does not usually outperform the much simpler FedAvg in practice. In this work, we propose that this gap is due to the presence of Edge of Stability (EoS) and progressive sharpening in federated optimization, supported by extensive empirical probing. First, we find that EoS-like dynamics occur with both FedAvg and SCAFFOLD under a variety of architectures and hyperparameters. We observe that the equilibrium value of the sharpness is inversely proportional to the learning rate (as in GD), and interestingly, the degree of data heterogeneity (but not the number of local steps) also affects the equilibrium value. Most importantly, we observe that SCAFFOLD's ability to estimate the gradient of the global objective is severely degraded at the EoS, as measured by the correlation between sharpness and SCAFFOLD's error in estimating the global gradient along the optimization trajectory. This suggests a mechanism for SCAFFOLD's lackluster performance in deep learning: with high sharpness at the EoS, SCAFFOLD cannot reliably estimate the global gradient.

Anant Khandelwal, Michael Crawshaw, Mingrui Liu

Georgia Institute of Technology, College of Computing · George Mason University, Department of Computer Science · Flatiron Institute, Center for Computational Mathematics

Federated Learning Non-IID Federated Learning Edge of Stability

Ask PDF

Apr 28, 2026

Subspace Optimization for Efficient Federated Learning under Heterogeneous Data

Federated learning increasingly operates in a large-model regime where communication, memory, and computation are all scarce. Typically, non-IID client data induce drift that degrades the stability and performance of local training. Existing remedies such as SCAFFOLD introduce heterogeneity-correction mechanisms to address this challenge, but they incur substantial extra communication and memory overhead. This paper proposes a subspace optimization method for federated learning (SSF), which performs heterogeneity-corrected optimization in a low-dimensional subspace using only projected quantities, while preserving full-dimensional control information through a backfill-style update that retains residual components whenever the active subspace changes. Under standard smoothness and bounded-variance assumptions, SSF attains a non-asymptotic rate of order

\widetilde{\mathcal{O}}(1/T+1/\sqrt{NKT})

. Experiments show favorable accuracy--efficiency trade-offs under heterogeneous data.

Shuchen Zhu, Zhengyang Huang, Yuqi Xu +1

Peking University · Beihang University

Subspace Optimization Non-IID Federated Learning Federated Learning Heterogeneous Federated Learning

Ask PDF

Jul 16, 2026

What's in a Smoothness Constant? Tighter Rates for Local SGD with Bounded Second-order Heterogeneity

Local SGD, also known as Federated Averaging, is a widely used distributed optimization algorithm. Although Local SGD often outperforms alternatives such as Mini-batch SGD in practice, theory still only partially explains when and why local updates help under realistic data heterogeneity. Recent work by [Patel et al., 2025] shows that a bounded second-order heterogeneity assumption captures the efficiency of Local SGD for strongly convex objectives, and conjectures that the same principle extends to the general convex setting. In this paper, we prove this conjecture by establishing an improved convergence guarantee for Local SGD on general convex objectives under bounded second-order heterogeneity. We also improve the best-known lower bounds for Local SGD in this setting, showing that our upper bounds are nearly tight. Together, these results provide a sharper, more fine-grained convergence theory for Local SGD. As a further application of our techniques, we provide a lower bound for serial SGD with replacement, showing how second-order heterogeneity captures the impact of rare high-curvature clients.

Kumar Kshitij Patel, Rustem Islamov, Sebastian U Stich +3

Department of Mathematics and Computer Science University of Basel Basel, Switzerland 4001 · Simons Institute for the Theory of Computing, Berkeley · Department of Data Science New Jersey Institute of Technology Newark, NJ, USA 07102

Optimization Convergence Analysis Stochastic Optimization Convergence Federated Learning Stochastic Gradient Descent

Ask PDF

Abstract

Federated Learning

Explore similar work

How Edge of Stability Hinders SCAFFOLD in Federated Optimization

Subspace Optimization for Efficient Federated Learning under Heterogeneous Data

What's in a Smoothness Constant? Tighter Rates for Local SGD with Bounded Second-order Heterogeneity