Federated optimization trains one model using objectives held by many clients. Performing several local updates between communication rounds saves communication, but clients with different objectives can move in different directions. SCAFFOLD maintains a correction for each client to address this disagreement, including when only some clients participate. Karimireddy et al. establish convergence without a bound on how similar the client objectives are. The relevant result is Theorem III, Section 5, PDF p. 5.
SCAFFOLD: Convergence with Client Sampling concerns that known result's formalization. Its exact targets are finite-round bounds from the Appendix E analysis, covering strongly convex, general convex, and nonconvex objectives. The paper's FedAvg results and its separate quadratic-acceleration theorem are outside this scope.
There are clients, with differentiable objectives . The global objective is . Every client gradient is -Lipschitz, where . A stochastic gradient query is conditionally unbiased and has conditional squared-error expectation at most , with . Current queries on different clients are conditionally independent given the full history. These make precise the fresh-oracle interpretation of A4–A5, Appendix B.1, PDF p. 14.
Each of rounds selects a uniform subset of clients, where . Each selected client takes local steps. Let be the server model, its stored client control variates, and . With constant local and global step sizes and , a client starts at and uses
Option II replaces a participating client's control with and retains every other control. These are Algorithm 1, PDF p. 4, and Appendix E, equations (18)–(21), PDF pp. 25–26. Write for the effective step size.
Four milestones support a root goal that is the conjunction of the two convergence statements below.
GradientGrowth states, for convex clients and a global minimizer ,
This is Appendix B.1, equation (9), PDF p. 14. PerturbedStrongConvexity states, for each -strongly convex client and ,
as in Appendix C, Lemma 5, PDF p. 17.
ConvexFiniteRoundConvergence allows arbitrary deterministic initial controls . Assume all clients are -strongly convex with , including ordinary convexity when , and fix a minimizer of . Define
For and , the target is
This is a finite-round formulation of Appendix E.1, Lemma 15, PDF p. 30; its case is the first bound on PDF p. 31.
NonconvexFiniteRoundConvergence assumes a lower bound for and initializes every client control with fresh gradients at . Put . For , establish
This is the explicit finite-round consequence targeted from Appendix E.2, Lemma 19, PDF p. 34, with the initialization specified on PDF pp. 31 and 35. The full-client warm start's communication cost is separate from these optimization rounds.
The bounds quantify optimization progress under stochastic gradients, several local steps, and partial participation. They permit arbitrarily different client objectives within the stated smoothness and convexity assumptions. Their output is a weighted random server iterate, represented by its expected loss, or a uniform random server iterate for the squared-gradient guarantee; this follows the output convention in equation (22), PDF p. 26.
The mathematical convergence analysis is published. The open work here is a Lean proof under the explicit stochastic-run model. The proposed statements do not themselves supply a machine-checked convergence proof. A completed development would provide reusable results about sampled finite averages, adaptive gradient queries, and optimization with stored noisy controls.
Local gradients are evaluated at different client states, and inactive clients retain controls computed in earlier rounds. Consequently, treating the server update as a centralized stochastic-gradient step discards both local disagreement and stale-control error. The challenge is to control these quantities while preserving their dependence on earlier randomness, as reflected in Appendix E.1–E.2, PDF pp. 26–35.
The source also needs careful transcription. The printed Theorem VII nonconvex noise term on PDF p. 25 differs from Lemma 19 in its smoothness and sampling factors, while output indices differ between equation (22) and the finite sum on p. 31. The exact targets above use the proof's finite-round constants and explicit indexing; they do not claim a verbatim formalization of every printed asymptotic rate.
SCAFFOLD.Space is finite-dimensional real Euclidean space;
SCAFFOLD.Problem records differentiable client objectives and smoothness.
SCAFFOLD.Run records a standard Borel probability space, full-history
filtration, measurable square-integrable iterates and oracle samples, and
the concrete updates. Virtual local paths are generated before a fresh
uniform size- subset is sampled, as permitted by the paragraph after
equation (22), PDF p. 26.
The conventions include , , zero noise, and . The output indices are precisely . Convex initial controls are deterministic; the nonconvex branch uses the specified stochastic warm start. The run definition assumes no descent inequality or convergence conclusion. Contributions should establish the four named propositions and necessary analysis/probability infrastructure while retaining these semantics.
namespace SCAFFOLD
theorem FiniteRoundConvergence :
(
∀ (d N : ℕ) (P : Problem d N) (Ω : Type u) [MeasurableSpace Ω]
[StandardBorelSpace Ω] (ν : Measure Ω) [IsProbabilityMeasure ν]
(S K T : ℕ) (ηl ηg μ : ℝ) (c0 : Fin N → Space d) (xstar : Space d),
Convexity P μ → IsMinimizer P xstar → 0 < ηl → 1 ≤ ηg →
effectiveStep K ηl ηg ≤ 1 / (81 * P.β) →
μ * effectiveStep K ηl ηg ≤ (S : ℝ) / (15 * (N : ℝ)) →
∀ A : Run P ν S K T ηl ηg (some c0),
weightedGap A xstar μ ≤ convexRHS P S K T ηl ηg μ c0 xstar
) ∧ (
∀ (d N : ℕ) (P : Problem d N) (Ω : Type u) [MeasurableSpace Ω]
[StandardBorelSpace Ω] (ν : Measure Ω) [IsProbabilityMeasure ν]
(S K T : ℕ) (ηl ηg fLower : ℝ),
(∀ x, fLower ≤ objective P.f x) → 0 < ηl → 1 ≤ ηg →
effectiveStep K ηl ηg ≤
Real.rpow ((S : ℝ) / (N : ℝ)) (2 / 3 : ℝ) / (24 * P.β) →
∀ A : Run P ν S K T ηl ηg none,
averageGradientSq A ≤ nonconvexRHS P S K T ηl ηg fLower
) := by sorry
end SCAFFOLDThe goal is the conjunction of the following two uniformly quantified finite-round guarantees.
Let and . Set , for , and . Then and
The case has uniform weights and ; gives geometric weights. No division by is used, and zero noise or zero initial distance is allowed.
For the full-client -sample warm start, put and suppose . Then
This includes , , , and under the specified initialization.
Formalization note: this is an explicit, paper-derived formulation of the finite-round convergence guarantees underlying Theorem III, not a literal formalization of its big- notation or a claim about last iterates. Rate optimization and initialization communication accounting are further corollaries, not extra hypotheses. The two branches use their stated, different initializations. The source audit documents the appendix sign, drift-index, control-expectation, and asymptotic-summary issues; none of those ambiguous expressions is used as a model assumption.
Source: Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank J. Reddi, Sebastian U. Stich, and Ananda Theertha Suresh, SCAFFOLD: Stochastic Controlled Averaging for Federated Learning, ICML 2020; arXiv:1910.06378v4, https://arxiv.org/abs/1910.06378v4; Section 5, PDF p. 5, Theorem III; Appendix E, PDF p. 25, Theorem VII; Appendix E.1, PDF p. 30, Lemma 15 and PDF p. 31 averaging display; Appendix E.2, PDF p. 34, Lemma 19 and PDF p. 35 final paragraph.
There are clients, a model space (including ), differentiable client losses with -Lipschitz gradients, , and . The starting point is deterministic and bounds within-client stochastic-gradient standard deviation. A run has rounds, local steps, clients per round, local step , global step , and . All random variables live on a standard Borel probability space with a filtration containing the full history. States and gradient samples are square integrable; gradient samples are conditionally unbiased, have conditional squared error at most , and are independent across clients conditional on each step's history. These are explicit fresh-oracle and finite-moment conventions.
Every round first defines virtual paths for all clients, starting at :
Then an -element subset is sampled uniformly, conditionally independently of these paths given the past. Equivalently, its conditional distribution given the entire completed virtual-path history is uniform. Only selected clients update their controls to ; other controls persist. The server update is . This is option II of Algorithm 1, with the average-gradient form of Appendix E. The model contains the algorithm and oracle laws, not any convergence inequality.
For convex targets, minimizes , and the client losses obey
The initial client controls are arbitrary deterministic vectors and the server control is their average. Define
For nonconvex targets, for all ; a minimizer need not exist. Each is instead initialized by averaging fresh stochastic gradients at , with the same conditional oracle assumptions. These full-client initialization queries are additional to the optimization rounds.
The output is a sampled pre-round server iterate among , represented by its expected loss or squared-gradient statistic. No last-iterate or pathwise guarantee is asserted. Sources: Section 2, PDF p. 2; Algorithm 1, PDF p. 4; Appendix B.1, PDF p. 14, assumptions A3–A5; Appendix E, PDF pp. 25–26, equations (18)–(22), Remark 10; Appendix E.2, PDF pp. 31 and 35, equations (26)–(27) and final warm-start paragraph. Primary reference: Karimireddy et al., SCAFFOLD: Stochastic Controlled Averaging for Federated Learning, ICML 2020, https://arxiv.org/abs/1910.06378v4.
No open leaves. Every sub-goal is proved or awaiting decomposition.