PaperlayerView exact revision on arXiv

Source-linked AI summary

Beyond Client Averaging: A Client-Independent Second-Order Stationary-Bias Component in Stochastic SCAFFOLD

Yi-Ping Tang, Guan-Ju Peng

arXiv:2608.26765v1cs.LGmath.ST

TL;DR

Existing constant-step stochastic SCAFFOLD analysis leaves the first client-independent higher-order bias coefficient unresolved. This paper proves and mechanistically identifies that coefficient in a scalar homogeneous fixed-H setting, showing that client averaging removes the O(γ/N) layer but not a nonzero O(γ^2) layer.

  • Problem

    Prior work identifies an O(γ/N) stationary mean-bias layer and persistent higher-order bias, but leaves the first client-independent contribution unresolved at coefficient level.

  • Method

    The paper analyzes full-participation stochastic SCAFFOLD with one-dimensional homogeneous clients, fixed H, small constant γ, bounded additive noise, stationary laws, and local second-moment identities.

  • Results

    The known O(γ/N) bias decreases with N, while a closed-form client-independent γ^2 term persists and is generated by fresh noise and persistent control fluctuations through nonquadratic curvature.

  • Takeaways & Limitations

    Increasing N alone cannot reduce the client-independent component after the O(γ/N) layer becomes smaller; decreasing γ does, and coefficient-aware correction is a future direction.

  • Takeaways & Limitations

    The result is restricted to the one-dimensional homogeneous fixed-H setting and does not establish extensions to multidimensional or heterogeneous clients.

Abstract

from arXiv · show

Existing constant-step analysis of stochastic \Scaf{} identifies a leading $O(γ/N)$ stationary mean bias and shows that higher-order bias can persist as the client count increases, but does not identify the first client-independent contribution at coefficient level. For full-participation stochastic \Scaf{} with one-dimensional homogeneous clients, fixed local-step count $H$, and bounded additive gradient noise, we prove, uniformly over $N\ge2$, $$ \begin{aligned} \mathbb{E}_{π_{γ,N,H}}[x]-x^\star ={}& -\frac{f'''(x^\star)σ^2}{4f''(x^\star)^2}\fracγ{N}\\ &- \frac{f'''(x^\star)σ^2}{12f''(x^\star)} \frac{(H-1)(5H-1)}{H}γ^2 +O_H\!\left(\frac{γ^2}{N}+γ^3\right). \end{aligned} $$ Hence client averaging suppresses the leading $O(γ/N)$ bias but does not remove the client-independent $O(γ^2)$ component when its coefficient is nonzero. The mechanism is indirect: although the direct control contribution cancels pathwise in the linear global average, the controls still alter within-round local trajectories and their second moments. Fresh gradient noise and persistent control fluctuations therefore generate local second-moment corrections that nonquadratic curvature converts into stationary mean bias. The coefficient vanishes for quadratic objectives. Numerical experiments are consistent with the predicted coefficient, its persistence as client count increases, and the stated joint remainder. The result is restricted to the one-dimensional homogeneous fixed-$H$ setting.

1 Introduction

This section identifies the first client-independent stationary-bias coefficient in stochastic SCAFFOLD and explains why client averaging cannot remove it. In the stated scalar homogeneous setting, local trajectory fluctuations pass through nonquadratic curvature into a persistent O(γ^2) mean shift.

  • Motivation: Existing analysis leaves the first client-independent higher-order stationary-bias contribution unresolved at the coefficient level.Prior work identifies the leading O(γ/N) layer and persistence of higher-order bias as client count increases.
  • Setting: The result applies to full-participation stochastic SCAFFOLD with one-dimensional homogeneous clients, fixed H, sufficiently small γ, and bounded additive gradient noise.The theorem is uniform in N within this setting.
  • Main result: Client averaging suppresses the known O(γ/N) bias layer, while the displayed γ^2 layer is independent of N when its coefficient is nonzero.After removing the known γ/N layer, the normalized residual converges to the displayed γ^2 coefficient along joint N →∞ and γ →0 sequences.
  • Mechanism: Fresh stochastic-gradient noise and persistent control fluctuations modify local second moments before nonquadratic curvature converts them into stationary mean bias.Controls cancel in the linear server average but continue to affect intermediate local trajectories.
  • Evidence: Numerical checks test persistence with increasing client count, convergence toward the predicted coefficient, and disappearance when stochasticity or nonquadratic curvature is removed.The experiments are finite-setting consistency checks rather than a broader theorem.
  • Scope: The analysis does not cover multidimensional, heterogeneous-client, state-dependent-noise, or debiasing extensions, and is not uniform as H →∞.It also does not identify the complete finite-N coefficient of γ^2.

2 Related work

The related work connects federated averaging, SCAFFOLD, stationary-law analysis, and higher-order noise–nonlinearity effects. This paper builds on prior stationary SCAFFOLD results by identifying the first client-independent γ^2 coefficient in a restricted scalar setting.

  • Federated optimization: FedAvg and LocalSGD use several local stochastic-gradient steps before synchronization to reduce communication, while local trajectories can drift toward client-specific directions.SCAFFOLD adds control variates to track a common optimization direction more closely.
  • Stationary laws: Constant-step stochastic optimization is analyzed through invariant distributions and small-step characterizations of stationary stochastic-gradient dynamics.Prior work includes diffusion approximations and Gaussian/Lyapunov descriptions of scaled stationary laws.
  • Higher-order bias: Earlier studies show that Markovian noise, memory, and nonlinearity can create distinct components of constant-step stationary bias.These results place the paper’s noise–nonlinearity mechanism within a broader stationary-approximation literature.
  • Stochastic SCAFFOLD: Prior stochastic SCAFFOLD analysis establishes stationarity, geometric convergence, moment bounds, and a higher-order bias that increasing client count does not eliminate.The unresolved issue is the coefficient-level identity of the first client-independent contribution.
  • Position of this work: The paper resolves this gap with a closed-form N^0γ^2 coefficient decomposed into fresh within-round gradient noise and persistent SCAFFOLD control second moments.Quadratic objectives remove the f′′′-based second-moment-to-mean conversion, and the decomposition is not a theorem-level FedAvg comparison.

3 Setting and exact identities

The paper studies a homogeneous scalar full-participation SCAFFOLD round using a zero-sum control parametrization. Exact identities separate pathwise cancellation in the global average from controls’ influence on intermediate local trajectories and stationary bias.

  • Setting: The analysis deliberately removes client heterogeneity by using homogeneous scalar clients with fixed H ≥2 and all clients participating each round.The objective is smooth with bounded higher derivatives, and its minimizer is translated to zero.
  • Noise model: Fresh gradient noises are independent across clients, local steps, and rounds, mean-zero, variance σ^2, almost surely bounded, and not assumed symmetric.These assumptions isolate stochastic effects within the full-participation setting.
  • Round dynamics: Each client starts from the server model and performs H corrected stochastic-gradient steps before the server aggregates the resulting local states.The local recursion uses the objective gradient, a zero-sum control, and fresh noise.
  • Control parametrization: Zero-sum variables are an exact reparametrization of the standard full-participation SCAFFOLD server and client controls.The parametrization preserves the zero-sum condition under the control updates.
  • Exact identities: Averaging the unrolled local recursion makes the controls cancel pathwise from the linear global average, but they still alter intermediate local trajectories.Stationarity then allows those trajectory changes to re-enter the global mean through the nonlinear gradient map.

4 Main result: a client-independent second-order layer

Theorem 4.1 identifies a client-independent O(γ^2) stationary-bias coefficient alongside the known O(γ/N) layer, uniformly over client count for fixed H. Increasing N suppresses only the first layer; the second persists when nonzero.

  • Main theorem: Theorem 4.1 gives a uniform joint stationary-bias expansion for full participation and fixed H, with constants independent of N and γ.The stationary law exists for sufficiently small γ, and the theorem applies for every N≥2.
  • Client averaging: O(γ/N) decreases as N grows, whereas the client-independent O(γ^2) contribution does not.Thus client averaging suppresses the leading displayed layer but not the second-order layer when its coefficient is nonzero.
  • Crossover: N× = 3H a(H −1)(5H −1) γ−1 is the scale where the two displayed asymptotic layers have equal magnitude when both coefficients are nonzero.This is only a crossover scale for the displayed terms, not an exact finite-step threshold or total-bias curve.
  • Local computation: The client-independent coefficient grows with the fixed local-step count H through the factor associated with local computation.The theorem treats each H as fixed, while the factor is increasing over integers H≥2.
  • Objective curvature: For quadratic objectives, f′′′(x⋆)=0, so both displayed bias coefficients vanish.Quadratic analysis can therefore miss the second-moment-to-mean conversion studied here.
  • Joint asymptotics: After subtracting the known γ/N layer and normalizing by γ^2, the residual converges to the displayed client-independent coefficient along every joint sequence N→∞ and γ→0.Terms of order γ^2/N remain in the remainder, so this does not identify the complete fixed-N second-order coefficient.

5 Mechanism: how controls survive linear cancellation

The control term cancels from the linear client average, but controls still reshape within-round local trajectories and their second moments. Fresh gradient noise and persistent control fluctuations are then converted by nonquadratic curvature into stationary mean bias.

  • Linear aggregation: The client-average control term cancels pathwise from the global update, so no direct linear control term shifts the server model.The controls nevertheless remain active in the local dynamics.
  • Within-round local dynamics: Control fluctuations alter intermediate local trajectories and the points where subsequent stochastic gradients are evaluated.Nonlinear local updates therefore occur along control-dependent paths before the server averages client outputs.
  • Second moments: Both fresh within-round gradient noise and persistent round-start controls contribute at the client-independent γ^2 scale as N grows.The control-related second moment approaches σ^2/H with increasing N.
  • Nonlinear conversion: A local Taylor expansion near the optimum converts corrections in local second moments into a stationary mean shift through nonlinear curvature.This follows from inserting local moments into the exact stationary balance.
  • Fluctuation sources: The coefficient is assembled from direct local-gradient noise and the additional second moment carried by SCAFFOLD controls.Their sum produces the coefficient in Equation (9).

6 Proof overview

The proof first isolates all possible second-order contributions, then sharply expands local moments and controls higher signed moments so the intended fluctuation sources can be identified without contamination.

  • Identifiability: The proof must rule out competing client-independent γ^2 contributions from global second moments, local second moments, and higher signed moments.A formal Taylor expansion alone does not establish coefficient identifiability.
  • Moment control: Coarse moment bounds establish N-uniform scales for the global iterate, controls, and local displacements before the local recursion is expanded sharply.The sharp expansion exposes fresh noise and the round-start control second moment.
  • Remainder control: Global fourth and signed third moments place cubic and quartic Taylor contributions inside the target remainder.The reduced stationary balance then yields the theorem after substituting the global and local moment expansions.
  • Global second moment: The sharp global second-moment estimate prevents an additional client-independent γ^2 term in E[x^2] from contaminating the local-trajectory coefficient.A coarser O(γ/N + γ^2) bound would not suffice.
  • Delicate covariance: A coordinate-replacement argument recovers the extra 1/N factor needed to control the delicate covariance between fresh round noise and the nonlinear increment.Only one client path changes when one fresh-noise coordinate is removed, and averaging supplies the additional sensitivity factor.

7 Numerical checks of the predicted effect

The numerical checks test persistence with increasing client count, convergence toward the predicted coefficient, and disappearance when stochasticity or nonquadratic curvature is removed.

  • Experimental design: Eight-chain experiments estimate the stationary mean and normalize the residual after removing the known γ/N contribution.The study uses a smooth strongly convex objective, independent Rademacher noise with variance one, and 95% Student-t intervals across chains.
  • 7.1 Does the component survive increasing client count?: −0.1875: the normalized residual approaches a nonzero plateau as N increases at H = 2 and γ = 1/24.A regression in 1/N gives large-N intercept −0.189145 with 95% bootstrap interval [−0.190398, −0.188035].
  • 7.2 Does the statistic approach the coefficient?: −0.187214: the H = 2 extrapolated intercept over decreasing step sizes is consistent with the predicted coefficient B20(2).The 95% bootstrap interval is [−0.189250, −0.185175].
  • 7.2 Does the statistic approach the coefficient?: −0.592953: the smaller-step H = 4 study yields an intercept with 95% bootstrap interval [−0.595526, −0.590236].The scaled error remains between 1.38 and 1.52, consistent with the predicted finite-step order.
  • 7.3 Do the required ingredients matter?: Deterministic gradients and quadratic objectives produce stationary-mean intervals containing zero.For quadratic objectives, f′′′(x⋆) = 0; the experiments also include an H = 1 boundary check.
  • 7.3 Do the required ingredients matter?: Together, the experiments support persistence with client count, convergence toward the predicted coefficient, and dependence on stochastic nonquadratic dynamics.These are finite-setting consistency checks rather than proofs beyond the stated experimental settings.

8 Conclusion

In the homogeneous scalar fixed-H setting, stochastic SCAFFOLD has a client-suppressed O(γ/N) bias layer and a client-independent O(γ2) layer generated indirectly through local trajectories and curvature.

  • Conclusion: Stochastic SCAFFOLD has two stationary-bias layers: O(γ/N), suppressed by client averaging, and client-independent O(γ2), persistent when its coefficient is nonzero.The conclusion applies to full participation, one-dimensional homogeneous clients, bounded additive noise, and fixed H.
  • Mechanism: Fresh gradient noise and persistent control fluctuations modify local second moments, which nonquadratic curvature converts into a stationary mean shift.Controls cancel in the linear server average but still alter within-round local trajectories.
  • Scope: The coefficient vanishes for quadratic objectives because f′′′(x⋆) = 0.The supplied assumptions define the relevant curvature quantities at the optimum.
  • Scope: The result assumes one-dimensional homogeneous fixed-H dynamics with bounded additive fresh noise and a zero-sum control state.The analysis is not uniform as H →∞, and the zero-sum restriction is part of the theorem interface.

A.3 Earlier stationary results used in the analysis

The analysis imports stationary and moment results for stochastic SCAFFOLD, then establishes exact identities and uniform estimates needed to isolate the client-independent γ2 coefficient.

  • Imported stationary inputs: Earlier work provides stationarity, geometric convergence, coarse iterate moments, a leading control second moment, and the known O(γ/N) bias coefficient.These imported inputs are used under matched assumptions and sufficiently small step size.
  • A.3 Earlier stationary results used in the analysis: The present proof resolves the client-number-independent N0γ2 coefficient that earlier remainder bounds did not identify.Bounds such as O(γ2H) and O(γ3/2) alone do not establish a nonzero coefficient.
  • Exact identities: The exact recursions show pathwise cancellation of the linear control term in the client average.The cancellation requires no independence assumption and preserves the zero-sum control-state invariant.
  • Exact identities: Controls can still affect the global stationary mean by changing local trajectories before re-entering through the nonlinear gradient map.This mechanism is exact before any small-step expansion.
  • Uniform estimates: Uniform moment estimates and coordinate-replacement arguments control local displacements and fresh-noise covariances uniformly in N.The extra 1/N sensitivity is needed for the joint remainder.
  • Coefficient identification: The proof excludes additional client-independent γ2 contributions from the global second moment and higher-curvature terms, while leaving finite-N γ2/N coefficients unresolved.No complete fixed-N second-order expansion is claimed.

H Assembly proof of the main expansion

The proof assembles the stationary-bias expansion by isolating fresh-noise and control-second-moment sources, while establishing a remainder uniform in N for fixed H.

  • H Assembly proof of the main expansion: The proof combines exact stationary mean balance with local and global moment estimates to derive the main expansion.The assembly proceeds through intermediate second-moment identities and a common small-step threshold.
  • H Assembly proof of the main expansion: The client-independent γ^2 coefficient decomposes into direct local fresh-gradient-noise and persistent SCAFFOLD control-second-moment contributions.The decomposition follows the two terms in the exact local second-moment identity and is not claimed to be unique under arbitrary reparameterizations.
  • H Assembly proof of the main expansion: Finite-N corrections to the control-generated γ^2 term are retained in the γ^2/N remainder rather than included in the client-independent coefficient.The displayed coefficient isolates the N^0 contribution induced by the control second moment.
  • H Assembly proof of the main expansion: For fixed H, the common small-step threshold and remainder constant are independent of N and γ, although both may depend on H and fixed problem parameters.No closed-form threshold is claimed, and uniform control as H tends to infinity is not established.
  • H Assembly proof of the main expansion: The proof excludes hidden N-dependence by tracking explicit client-averaging factors and using inequalities whose constants do not depend on N or the relative rate of N and γ.The resulting remainder has an H-dependent constant but no N- or γ-dependent constant.

I.2 Uniform joint (γ, 1/N) interpretation

The result identifies the N^0γ^2 coefficient in a uniform joint expansion after removing the known γ/N layer, without asserting it is unconditionally the next or first nonzero term.

  • I.2 Uniform joint (γ, 1/N) interpretation: For any γ_k → 0 and N_k → ∞ with fixed H, the normalized residual converges to the identified N^0γ^2 coefficient without a relative-rate condition.Both remainder terms vanish along every such joint sequence.
  • I.2 Uniform joint (γ, 1/N) interpretation: The monomials γ/N and γ^2 have no fixed ordering along all two-parameter paths, so the γ^2 term should not be called unconditionally the next term.The precise statement is a uniform joint expansion after removing the known γ/N layer.
  • I.2 Uniform joint (γ, 1/N) interpretation: The theorem identifies the client-number-independent γ^2 coefficient, but does not establish that it is the first nonzero client-independent term when its coefficient may vanish.A nonzero-coefficient condition is required for that stronger interpretation.
  • I.2 Uniform joint (γ, 1/N) interpretation: The coefficient has a canonical source-wise decomposition into direct local-gradient noise and the persistent SCAFFOLD control second moment.This is a decomposition of the exact local second-moment identity, not a claim that all higher-order bias is caused by controls.
  • I.2 Uniform joint (γ, 1/N) interpretation: The result is not a complete finite-N second-order expansion and does not extend here to heterogeneous clients, multidimensional systems, or state-dependent noise.It also does not prove equality with a separately established general-H FedAvg coefficient.

J.2 Initial joint path and the recorded H = 4 discrepancy

The initial coarse-grid H = 4 study showed a finite-step discrepancy, while the smaller-step follow-up moved toward the predicted coefficient with an O(γ)-compatible residual.

  • J.2 Initial joint path and the recorded H = 4 discrepancy: H = 2 extrapolation is consistent with the target coefficient, whereas H = 4 extrapolation is offset on the initial finite-step grid.The H = 4 discrepancy was recorded as a contradiction candidate under the initial study criterion.
  • J.2 Initial joint path and the recorded H = 4 discrepancy: The H = 4 follow-up met its specified validity, directional-convergence, smallest-step-proximity, and O(γ)-compatibility criteria.Observed errors decreased from 0.02159 to 0.00787 while E(γ)/γ remained of constant order.
  • J.2 Initial joint path and the recorded H = 4 discrepancy: The smaller-step H = 4 normalized residual moves toward the predicted coefficient, while the scaled error remains of constant order.This behavior is consistent with the permitted O_H(γ) normalized remainder along N = 1/γ.
  • J.2 Initial joint path and the recorded H = 4 discrepancy: Deterministic gradients and quadratic objectives provide negative controls in which the displayed stochastic coefficients vanish.The H = 1 experiment is a boundary check outside the theorem’s stated H ≥ 2 domain.
Loading 2608.26765v1…