Characterizing Client-Independent Stationary Bias for SCAFFOLD and FedAvg in Federated Learning

Yi-Ping Tang; Guan-Ju Peng

cs.LGAug 27, 2026

Characterizing Client-Independent Stationary Bias for SCAFFOLD and FedAvg in Federated Learning

Authors: Yi-Ping Tang, Guan-Ju Peng

Organizations: Both authors are with the Graduate Institute of Data Science and Information Computing, National Chung Hsing University, Taichung, Taiwan.

Abstract

Even when all clients optimize the same strongly convex objective, the global model parameters produced by constant-step federated learning may still have a stationary mean that differs from the minimizer. Does increasing the number of clients eliminate this bias, or can some components persist? Answering this question clarifies the limits of client averaging. To this end, we study two federated learning algorithms, \Scaf{} and matched \FedAvg{}, under full participation, a sufficiently smooth objective, and independent bounded additive gradient noise. Analyzing global stationary balance and within-round local fluctuations yields multidimensional expansions with a shared $γ/N$ term and explicit client-independent $γ^2$ coefficients, where $γ$ is the step size and $N$ is the client count. The \Scaf{} coefficient combines the ordinary local-update contribution found in \FedAvg{} with an additional persistent-control contribution. Although zero-sum controls cancel from the direct server increment, they change local second moments, which interact with third-order curvature to shift the stationary mean. For fixed dimension $d$ and local-step count $H$ , a remainder of $O_{H,d}(γ^2/N+γ^3)$ , uniform in $N$ for sufficiently small $γ$ , identifies the second-order coefficients along arbitrary joint small-step, large-client limits after removing the shared leading term. Controlled experiments assess the predicted coefficients. In real-data analyses, finite-tail mean displacement can account for a substantial share of averaged-model parameter error, and a post-hoc comparison shows directional agreement with the derived curvature--noise structure.

Figures & tables

Analysis	Characterization beyond the shared leading term
SCAFFOLD , Mangold et al. [8, Theorem 5.3]	$O(\gamma^{2}H+\gamma^{3/2})$
FedAvg , Mangold et al. [9, Theorem 3]	$O(\gamma^{2}H+\gamma^{3/2})$
FedAvg , Mangold et al. [9, Theorem 4] , with $f_{c}=f$	$O(\gamma^{2}H^{2}+\gamma^{3/2}H)$
This work, Theorems 4.1 and 4.2	$\gamma^{2}B_{20}^{\mathcal{A}}(H)$ ${}+O_{H,d}(\gamma^{2}/N+\gamma^{3})$

Table 1: Analytical resolution beyond the shared leading bias term. Each entry characterizes

b^{\mathcal{A}}_{\gamma,N,H}-(\gamma/N)B_{11}

in the common-objective, additive-noise setting. Prior bounds leave the client-independent second-order coefficient unresolved; the last row identifies it explicitly and bounds the residual.

Study	$H$	Grid	Target vector	Estimated intercept vector
SCAFFOLD	2	P	$(-0.0480040,\,-0.0600050)$	$(-0.0476713,\,-0.0595811)$
SCAFFOLD	4	P	$(-0.1520127,\,-0.1900159)$	$(-0.1502614,\,-0.1874524)$
SCAFFOLD	4	S	$(-0.1520127,\,-0.1900159)$	$(-0.1514772,\,-0.1893273)$
FedAvg	2	P	$(-0.0320027,\,-0.0400033)$	$(-0.0320430,\,-0.0400539)$
FedAvg	4	P	$(-0.0960080,\,-0.1200100)$	$(-0.0959717,\,-0.1198059)$
FedAvg	4	S	$(-0.0960080,\,-0.1200100)$	$(-0.0959727,\,-0.1199590)$

Table 2: Analytical coefficient vectors and fitted finite-grid intercepts. Individual rows target

B_{20}^{\mathcal{A}}(H)

; matched-pair rows target

B_{20}^{\mathrm{ctrl}}(H)

. P and S denote the primary and smaller-step joint grids in Table 7 . Values are rounded to seven decimal places; simultaneous intervals are in Table 11 .

Panel of Figure 1 — Figure 1: Matched SCAFFOLD – FedAvg coefficient estimates for (a) $H=2$ and (b) $H=4$ on the primary joint grids. The ordinate is $\widehat{D}_{j}$ from Equation ( 34 ). Circles and squares show the two coordinates, dotted lines show finite-grid linear fits, and dashed horizontal lines give the analytical targets. Open diamonds at $\delta=0$ mark the fitted intercepts. Pointwise bars use simultaneous Student- $t$ intervals; intercept bars use simultaneous seed-block-bootstrap intervals.

Panel of Figure 2 — Figure 2: Client-count dependence at fixed step size, shown by coordinate. The ordinate is $\widehat{\mathcal{C}}^{\textnormal{{SCAFFOLD}}}_{j}$ from Equation ( 33 ): the mean-bias estimate after subtracting the shared $\gamma/N$ term and dividing by $\gamma^{2}$ . Dotted lines give finite-grid fits and open diamonds their intercepts at $1/N=0$ . Dashed horizontal lines give the joint-limit references $B_{20}^{\textnormal{{SCAFFOLD}}}(2)$ ; a fixed step size permits an $O(\gamma)$ offset. Bars show simultaneous Student- $t$ intervals at grid points and seed-block-bootstrap intervals for fitted intercepts.

$H$	$j$	Estimate	Target	Nominal interval
2	1	$-0.01599546$	$-0.01600134$	$[-0.01601159,\,-0.01597933]$
2	2	$-0.01999408$	$-0.02000167$	$[-0.02001422,\,-0.01997394]$
4	1	$-0.05595226$	$-0.05600469$	$[-0.05601109,\,-0.05589342]$
4	2	$-0.06993656$	$-0.07000586$	$[-0.07000999,\,-0.06986314]$
8	1	$-0.13962104$	$-0.14001171$	$[-0.13983973,\,-0.13940235]$
8	2	$-0.17449119$	$-0.17501464$	$[-0.17476345,\,-0.17421894]$

Table 3: Control-coefficient estimates on the independent Cartesian grid. Each row compares the fitted intercept with

B_{20}^{\mathrm{ctrl}}(H)

. Intervals are nominal 95% run-seed intervals.

$\rho$	Noise law	Target	Estimate	Simultaneous interval
$-1/4$	Symmetric	$0.021875$	$0.02187858$	$[0.02184128,\ 0.02191589]$
$0$	Symmetric	$0.000000$	$-0.00002056$	$[-0.00006150,\ 0.00002039]$
$+1/4$	Symmetric	$-0.021875$	$-0.02185115$	$[-0.02189536,\ -0.02180693]$
$+1/4$	Asymmetric	$-0.021875$	$-0.02188179$	$[-0.02193153,\ -0.02183205]$
Symmetric minus asymmetric ( $\rho=1/4$ )		$0.000000$	$0.00003064$	$[-0.00003564,\ 0.00009692]$

Table 4: Contraction and noise-law checks for the first coordinate of the matched coefficient at

H=4

. The covariance controls predict positive, zero, and negative coefficients; the last row compares noise laws with identical covariance. Intervals are approximate simultaneous 95% sampling intervals for the prespecified 36-scalar family.

Figure 3: Finite-tail mean displacement under a fixed sampling budget. Each category gives a client-count/minibatch allocation

(N,m)

with

Nm=256

. The ordinate is the signed projection in Equation ( 35 ), scaled by

10^{3}

. Bars are nominal 95% run-seed intervals; small offsets distinguish the algorithms at the same allocation.

Setting	$\widehat{\delta}_{v}^{\rm S}$	$\widehat{\delta}_{v}^{\rm F}$	$\widehat{V}^{\rm S}$	$\widehat{V}^{\rm F}$
$H=4,\ \gamma=\gamma_{b}$	$0.9567$	$0.6851$	$2.3621$	$2.3613$
$H=4,\ \gamma=\gamma_{b}/2$	$0.3547$	$0.2796$	$1.1723$	$1.1722$
$H=4,\ \gamma=\gamma_{b}/4$	$0.0622$	$0.0420$	$0.5860$	$0.5860$
$H=2,\ \gamma=\gamma_{b}$	$0.3402$	$0.2474$	$2.3601$	$2.3599$

Table 5: Step-size and local-step comparisons for the shared objective at

N=32,m=8

. All entries are multiplied by

10^{3}

\widehat{\delta}_{v}

is signed finite-tail mean displacement and

\widehat{V}

is raw-checkpoint parameter variance. S: SCAFFOLD; F: FedAvg.

Panel of Figure 4 — Figure 4: Parameter-error decomposition after temporal model averaging. The panels compare estimated squared mean displacement $\widehat{U}_{K}$ with averaged-output variance $\widehat{V}_{K}$ over windows of $K$ batches in the primary shared-objective configuration. Each batch contains 1,280 rounds. Bars are approximate simultaneous 95% primary-family intervals. The symmetric-log axis is linear between $-10^{-5}$ and $10^{-5}$ and retains negative sampling-corrected estimates and intervals crossing zero.

$H$	$N$	$m$	$\gamma/\gamma_{b}$	Cosine	Projection ratio	Relative residual
2	32	8	$1$	$0.997719$	$0.938327$	$0.088505$
4	8	32	$1$	$0.996500$	$0.715730$	$0.290542$
4	32	8	$1/4$	$0.997252$	$0.935781$	$0.094644$
4	32	8	$1/2$	$0.998972$	$0.867499$	$0.138225$
4	32	8	$1$	$0.998994$	$0.784711$	$0.218151$
4	128	2	$1$	$0.999254$	$0.796703$	$0.205615$

Table 6: Post-hoc comparison of the analytical proxy

p=p_{\gamma,H,m}

and the 124-dimensional finite-tail mean difference

\widehat{\Delta}_{K}

K=64

. Cosine

=p^{\top}\widehat{\Delta}_{K}/(\|p\|\|\widehat{\Delta}_{K}\|)

; projection ratio

=p^{\top}\widehat{\Delta}_{K}/\|p\|^{2}

; relative residual

=\|\widehat{\Delta}_{K}-p\|/\|p\|

. All six nonzero-proxy configurations are shown; the

H=1

checks and sampling intervals are in Appendix C.4.4 .

Appendix figures & tables17 assets

Supplementary material from the paper’s appendix.

Appendix

Comparison	$d$ ; $H$	Client counts and step sizes	Runs
Primary joint grid	$2$ ; $2,4$	$\begin{gathered}N\in\{12,16,24,32,48\},\\ \gamma=1/N.\end{gathered}$ (77)	8
Smaller-step joint grid	$2$ ; $4$	$\begin{gathered}N\in\{64,96,128,192\},\\ \gamma=1/N.\end{gathered}$ (78)	8
Fixed-step client count	$2$ ; $2$	$N\in\{8,16,32,64,128\}$ ; $\gamma=1/24$	8
Five-dimensional	$5$ ; $2,4$	$N\in\{32,48,64,96,128\}$ ; $\gamma=1/N$	8
Leading coefficient	$2$ ; $1,2,4,8$	$N=32$ ; $\gamma\in\{1/64,1/128,1/256,1/512\}$	12
Cartesian control coefficient	$2$ ; $2,4,8$	$N\in\{32,64,128\}$ ; $\gamma\in\{1/128,1/256,1/512\}$	12

Appendix

Table 7: Controlled experimental settings. Runs are independent simulation units per configuration; the matched studies use algorithm pairs. The smaller-step path supplements

H=4

on the primary joint grid. Structural-check settings are given in Table 19 .

Study	Heuristic time scale	Burn-in	Batch length	Batches
Joint grid, fixed step, and $d=5$	$m_{\rm mix}=\lceil(\mu_{\rm mix}H\gamma)^{-1}\rceil$ ; $\mu_{\rm mix}=0.85$ ( $d=2$ ), $0.8037572789$ ( $d=5$ )	$100m_{\rm mix}$	$20m_{\rm mix}$	100
Cartesian/local step	$\tau_{0}=\lceil(0.85H\gamma)^{-1}\rceil$	$50\tau_{0}$	$10\tau_{0}$	64
Contraction/noise law	$\tau=\lceil(0.6H\gamma)^{-1}\rceil$	$50\tau$	$10\tau$	64
Real-data training	$\tau_{0}=\lceil(\lambda H\gamma)^{-1}\rceil$	$50\tau_{0}$	$10\tau_{0}$	64

Appendix

Table 8: Run schedules. Burn-in and batch length are measured in communication rounds. The real-data regularization parameter

\lambda

is given in Table 20 .

Study	Interval construction	Coordinate levels / simultaneous family
Joint grid and fixed step, $d=2$	Pointwise Student- $t$ (7 degrees of freedom); 2,000 seed-block bootstrap draws for intercepts	Coordinate level $0.975$ ; bootstrap quantiles $(0.0125,0.9875)$
Five-dimensional	Pointwise Student- $t$ (7 degrees of freedom); 5,000 bootstrap draws	Coordinate level $0.99$ ; quantiles $(0.005,0.995)$
Cartesian/local step	Student- $t$ (11 degrees of freedom); Bonferroni adjustment; 2,000 bootstrap draws for sensitivity	16 leading coordinates; 6 control coordinates; 12 $H$ contrasts; 2 coordinates for $H=4-3.5(H=2)$
Contraction/noise law	4,000 within-cell bootstrap draws; centered standardized maximum; marginal and Bonferroni- $t$ sensitivity	36 scalars: 24 coefficient coordinates, 6 law contrasts, 6 covariance contrasts
Real-data allocation	Nominal jackknife- $t$ intervals; adjusted contrast intervals	105 cellwise projections; separate 36 allocation/configuration contrasts
Model averaging	19,999 paired-seed bootstrap draws; centered standardized maximum; delete-one-seed Bonferroni- $t$ sensitivity	Separate primary (196), secondary (392), and diagnostic (1,176) families

Appendix

Table 9: Sampling-uncertainty procedures. Simultaneous families are specified separately for the listed estimands. All resampling preserves matched algorithm outputs and their coordinates.

Law	Support	Probabilities	$\mathbb{E}[z_{i}^{3}]$	$\mathbb{E}[z_{i}^{4}]$
Symmetric	$(-1,1)$	$(1/2,1/2)$	$0$	$1$
Asymmetric	$(\sqrt{2},-1/\sqrt{2})$	$(1/3,2/3)$	$1/\sqrt{2}$	$3/2$

Appendix

Table 10: Covariance-matched scalar noise laws. Both have mean zero and variance one. Symmetric noise is used at

\rho=-1/4,0,1/4

; asymmetric noise is also tested at

\rho=1/4

Study	$H$	Grid	Coordinate 1 interval	Coordinate 2 interval
S	2	P	$[-0.0482374,-0.0471965]$	$[-0.0602886,-0.0589883]$
S	4	P	$[-0.1508906,-0.1497518]$	$[-0.1882351,-0.1868165]$
S	4	S	$[-0.1522435,-0.1507781]$	$[-0.1902854,-0.1884530]$
F	2	P	$[-0.0326464908,-0.0313780188]$	$[-0.0408082738,-0.0392220804]$
F	4	P	$[-0.0965774402,-0.0953321996]$	$[-0.1205630991,-0.1190074303]$
F	4	S	$[-0.0964743358,-0.0953790293]$	$[-0.1205859653,-0.1192168647]$

Appendix

Table 11: Simultaneous 95% seed-block-bootstrap intervals for the joint-grid coefficients in Table 2 . S: SCAFFOLD; F: FedAvg; D: matched difference. P and S identify the primary and smaller-step grids.

$j$	$\|e_{\Delta}\|$ at $\delta_{\min}$	$\|e_{\Delta}\|$ at $\delta_{\max}$	$\|e_{\Delta}\|/\delta$ range	Log–log slope
1	$0.0015750$	$0.0202050$	$[0.121,0.151]$	$0.927$
2	$0.0020785$	$0.0263460$	$[0.158,0.200]$	$0.923$

Appendix

Table 12: Matched

H=4

grid-point residuals against

\delta=\gamma+1/N

. The last two columns summarize the observed residual scale across the combined grid.

Panel of Figure 5 — Figure 5: Matched $H=4$ finite-grid sensitivity. (a) Smaller-step estimates (circles and squares), finite-grid linear fits (dotted), and analytical targets (dashed). Open diamonds at $\delta=0$ mark the fitted intercepts. (b) Absolute residuals versus $\delta=\gamma+1/N$ across all nine points on logarithmic axes; lines connect the observed residuals. The scaled residuals and log–log slopes are given in Table 12 . Pointwise bars in (a) use simultaneous Student- $t$ intervals; intercept bars use seed-block-bootstrap intervals.

$j$	95% simultaneous CI	Intercept $-$ theory
1	$[-0.0489079,-0.0483504]$	$-0.0006102$
2	$[-0.0607622,-0.0600656]$	$-0.0003902$

Appendix

Table 13: Sampling intervals and offsets for the fixed-step extrapolated intercepts in Figure 2 .

$H$	$j$	$\widehat{\beta}_{0,j}$	Theory	95% simultaneous CI
2	1	$-0.0140655061$	$-0.0140249988$	$[-0.0142709800,-0.0138295249]$
2	2	$-0.0457104417$	$-0.0455796216$	$[-0.0463785328,-0.0449434842]$
2	3	$0.0322203570$	$0.0321284384$	$[0.0316797243,0.0326913914]$
2	4	$-0.0340954937$	$-0.0339978616$	$[-0.0345938212,-0.0335234201]$
2	5	$0.0160014114$	$0.0159557997$	$[0.0157329196,0.0162353381]$
4	1	$-0.0444005615$	$-0.0444124962$	$[-0.0446094313,-0.0441636371]$

Appendix

Table 14: Five-dimensional SCAFFOLD coefficient targets, fitted intercepts, and nominal simultaneous 95% bootstrap intervals.

$H$	Alg.	Estimate 1	Interval 1	Estimate 2	Interval 2
1	S	$-0.024531$	$[-0.024960,-0.024102]$	$-0.030664$	$[-0.031200,-0.030127]$
1	F	$-0.024531$	$[-0.024960,-0.024102]$	$-0.030664$	$[-0.031200,-0.030127]$
2	S	$-0.024432$	$[-0.025068,-0.023795]$	$-0.030554$	$[-0.031349,-0.029758]$
2	F	$-0.024413$	$[-0.025051,-0.023774]$	$-0.030525$	$[-0.031323,-0.029728]$
4	S	$-0.025169$	$[-0.025953,-0.024385]$	$-0.031537$	$[-0.032517,-0.030557]$
4	F	$-0.024799$	$[-0.025574,-0.024024]$	$-0.031044$	$[-0.032013,-0.030075]$

Appendix

Table 15: Independent leading-coefficient fits with nominal 95% intervals. S: SCAFFOLD; F: FedAvg. The targets are

B_{11,1}=-0.02445943

and

B_{11,2}=-0.03057429

for every

H

;

H=1

checks the boundary recursion.

Condition / contrast	Alg.	Estimate 1	Interval 1	Estimate 2	Interval 2
$-1/4$ , sym.	S	$56.0908$	$[42.4573,\ 69.7243]$	$2.6156$	$[-4.5559,\ 9.7871]$
$-1/4$ , sym.	F	$34.2122$	$[20.5757,\ 47.8487]$	$2.6118$	$[-4.5609,\ 9.7844]$
$0$ , sym.	S	$4.6861$	$[-18.0942,\ 27.4663]$	$2.4973$	$[-6.0117,\ 11.0064]$
$0$ , sym.	F	$4.7066$	$[-18.0689,\ 27.4822]$	$2.5118$	$[-5.9994,\ 11.0230]$
$+1/4$ , sym.	S	$-46.8325$	$[-67.9207,\ -25.7443]$	$2.2185$	$[-4.0669,\ 8.5038]$
$+1/4$ , sym.	F	$-24.9813$	$[-46.0714,\ -3.8913]$	$2.2414$	$[-4.0463,\ 8.5291]$

Appendix

Table 16: Additional contraction and noise-law results: individual coefficients and contrasts, and the paired second coordinate. Estimates and interval endpoints are multiplied by

10^{3}

. S: SCAFFOLD ; F: FedAvg ; D: matched difference. Targets follow Equation ( 82 ). The law contrast is symmetric minus asymmetric at

\rho=1/4

; the covariance contrast is

\rho=1/4

minus

-1/4

with symmetric noise. Intervals use the primary family in Table 4 .

Quantity	Target	Estimate	Simultaneous interval
SCAFFOLD coefficient	$-0.059375$	$-0.01675171$	$[-0.05907084,0.02556741]$
FedAvg coefficient	$-0.0375$	$0.00510137$	$[-0.03721159,0.04741432]$
SCAFFOLD covariance contrast	$-0.11875$	$-0.06840058$	$[-0.11872928,-0.01807187]$

Appendix

Table 17: First-coordinate sensitivity after removing the largest step in the contraction study. The first two rows use

\rho=1/4

and symmetric noise; the last row is the signed-covariance contrast.

$H$	$N$	$j$	$\widehat{C}_{\rm bal}$	$\widehat{C}_{\rm dir}$	$\|\Delta\widehat{b}\|$	$3\operatorname{SE}_{\rm comb}$
2	16	2	$-0.0408082$	$0.924598$	$0.00377112$	$0.00331567$
2	48	1	$-0.0323449$	$3.070686$	$0.00134680$	$0.00115744$
4	16	2	$-0.1080240$	$0.841309$	$0.00370833$	$0.00334677$
4	48	1	$-0.0933450$	$2.615233$	$0.00117560$	$0.00110953$

Appendix

Table 18: The four direct–balance discrepancies in the primary FedAvg study. The diagnostic uses the unnormalized difference

|\Delta\widehat{b}|

; the normalized statistics are also shown.

Check	Configuration
Orthogonal rotation	$Q=\left(\begin{smallmatrix}0.8660254037844386&-0.5\\ 0.5&0.8660254037844386\end{smallmatrix}\right)$ ( $30^{\circ}$ ); $H\in\{2,4\}$ ; $(N,\gamma)\in\{(16,1/16),(64,1/64)\}$ ; 4 paired runs per configuration, 16 paths in total
Affine translation	$N\in\{8,32\}$ ; $H\in\{2,4,8\}$ ; $a_{c}=\pm\rho u$ , $\rho\in\{0,0.25,0.5,1\}$ ; $\gamma=1/128$ ; 24 configurations of 2,000 rounds

Appendix

Table 19: Structural consistency checks. Corresponding initial states and noise realizations are used within each comparison.

Component	Specification
Training data	32,512 of 32,561 rows selected by a fixed random permutation to allow equal disjoint partitions
Features and penalty	Each 123-feature row divided by $\max\{1,\\|z_{i}\\|\}$ , then augmented with an intercept; $y_{i}\in\{0,1\}$ ; all 124 parameters regularized with $\lambda=0.01$
Client objectives	Shared: all clients use the same data; disjoint IID: random partition; label skew: two label-sorted shards per client. Disjoint regimes use one primary and two alternative partitions
Minibatches and base step	Sampling with replacement; $L_{\rm sample}=0.51$ ; $\gamma_{b}=0.1/L_{\rm sample}=0.1960784314$
Fixed-budget allocations	$Nm=256$ ; $(N,m)\in\{(8,32),(32,8),(128,2)\}$ ; $H=4$ , $\gamma=\gamma_{b}$
Additional shared-objective runs	Three step-size/local-step variants (Table 5 ) and three $H=1$ checks; nine shared-objective configurations in total

Appendix

Table 20: Real-data settings. All training configurations use twelve independent SCAFFOLD – FedAvg pairs. Windows within a run share its trajectory. The two longer-run pilots are analyzed separately.

Shared objective: additional error and loss measurements
$N$	MSE (S)	MSE (F)	Test loss (S)	Test loss (F)
8	$2.3511$	$2.3509$	$0.424981$	$0.424983$
32	$2.3629$	$2.3618$	$0.424961$	$0.424970$
128	$2.3745$	$2.3655$	$0.424889$	$0.424922$

Appendix

Table 21: Additional finite-tail allocation results at

H=4

\gamma_{b}

, and

Nm=256

. The upper panel supplements Figure 3 with error and loss measurements; the lower panel reports disjoint partitions. Projection intervals are nominal 95% intervals. Raw-checkpoint MSE is multiplied by

10^{3}

; held-out loss is averaged over the per-run tail-average models. S: SCAFFOLD; F: FedAvg.

Quantity	SCAFFOLD	FedAvg
$\widehat{M}_{K}$	$17.267\ [15.383,19.151]$	$10.878\ [9.459,12.297]$
Train objective gap	$0.725\ [0.630,0.819]$	$0.361\ [0.295,0.426]$
Held-out log loss	$0.424889\ [0.424879,0.424899]$	$0.424922\ [0.424912,0.424932]$
Paired difference	Estimate [simultaneous interval]
$\Delta\widehat{U}_{K}$	$6.378\ [5.848,6.908]$
$\Delta\widehat{V}_{K}$	$0.011\ [-0.036,0.058]$

Appendix

Table 22: Additional longest-window model-averaging statistics at

K=64

, with approximate simultaneous 95% primary-family intervals. Parameter errors and training gaps are multiplied by

10^{6}

; test loss is unscaled. The component shares and total-MSE contrast are reported in Section 6.4 .

Stochastic Optimization

Stochastic optimization studies how to find good decisions or model parameters when objectives, data, or feedback are random or noisy.

See all 212 papers

Oct 26, 2026

SCAFFOLD under Hessian Similarity: Sharp Convergence Rates

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.

Zhirayr Tovmasyan, Slavomír Hanzely, Egor Shulgin +2

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

Federated Learning Heterogeneous Federated Learning Federated Learning Aggregation

Ask PDF

Sep 14, 2026

Steady-State Convergence of Stochastic Approximation

For constant-stepsize stochastic approximation (SA), the iterates converge in distribution to a stationary law that depends on the stepsize

α.

Steady-state convergence (SSC) concerns the limit of the scaled stationary distribution as

α\downarrow 0.

Existing SSC theory requires i.i.d. or additive noise and global differentiability of the mean operator, and yields suboptimal rates. We develop a unified SSC theory for constant-stepsize contractive SA driven by Markovian, multiplicative noise, covering both locally differentiable and locally nondifferentiable mean operators. A key methodological contribution is a multi-step universality framework that progressively reduces the original stochastic recursion to tractable auxiliary dynamics while preserving its steady-state limit. Under local quadratic linearization at the fixed point, we obtain a Gaussian approximation of the scaled steady state at the optimal rate

O(\sqrtα)

in Wasserstein-2 distance, which further gives finite-time Gaussian approximations for the raw iterates. In the locally nondifferentiable regime, we establish a general SSC result and show that the leading-order asymptotic bias can be of order

\sqrtα

, in contrast to the

α

-order bias in the smooth regime. We apply the theory to Markovian linear SA and asynchronous Q-learning, neither of which is covered by prior results. We further propose a bias-reduction scheme for Q-learning that requires no knowledge of the local smoothness regime, validated by numerical experiments.

Yixuan Zhang, Qiaomin Xie

Department of Industrial & Systems Engineering, University of Wisconsin–Madison

Stochastic Approximation Q-Learning

Ask PDF

Oct 7, 2026

Stationary Bias and Extrapolation in Nonlinear Two-Timescale Stochastic Approximation

Constant-step stochastic approximation generally has a nonzero stationary mean error that persists under time averaging. This paper studies that error for nonlinear two-timescale recursions driven by an exogenous finite-state Markov chain. Under stated smoothness assumptions and conditions on the stationary distribution, we derive a first-order bias expansion whose error bound remains uniform as the slow step size becomes much smaller than the fast step size. Fast-manifold coordinates keep the associated covariance equation regular in this limit. For fast step

η

and slow step

\varepsilon

, the expansion reveals a mixed contribution

\varepsilon^2/η

alongside terms linear in each step size. This dependence matters for bias reduction: along power-law step-size paths, the bias exponents need not be integers, so Richardson--Romberg extrapolation requires weights matched to the path. An exactly solvable nonlinear Markov example verifies the coefficients. We verify localization for temporal-difference learning and compare finite-run extrapolation at equal update budgets. For finite runs, we bound the initialization error of tail averages on both timescales under an additional coupling assumption. In the special case of additive independent noise, signed third-moment cancellation yields a sharper remainder.

A. Ch. Madhusudanarao, Rahul Singh

Department of Computer Science and Automation Indian Institute of Science, Bengaluru, India · Laboratoire de Recherche de l’EPITA, Paris, France

Richardson Extrapolation Stochastic Approximation Two-Timescale Stochastic Approximation

Ask PDF

Abstract

Stochastic Optimization

Explore similar work

SCAFFOLD under Hessian Similarity: Sharp Convergence Rates

Steady-State Convergence of Stochastic Approximation

Stationary Bias and Extrapolation in Nonlinear Two-Timescale Stochastic Approximation