Federated optimization studies learning when data and computation are spread across clients. Communicating after every stochastic gradient step can be costly, so clients often take several steps before averaging their models. The difficulty is that different clients can optimize different objective functions. Their models then move apart between communication rounds. A convergence guarantee must account for both stochastic gradient noise and this disagreement. Wang et al. give an explicit analysis of this tradeoff in A Field Guide to Federated Optimization, Section 6.1.
The relevant historical sequence is the introduction of FedAvg by McMahan et al.
in 2017, the development of local-SGD convergence analyses reviewed by Wang et al.,
and the unified illustrative analysis in the 2021 field guide. The present target
is that guide's known convex convergence theorem, rather than a new conjecture
about arbitrary federated learning. The remaining open task is a Lean proof of
the stated result. The mission is categorized as ResearchPaper: it formalizes a specific known
result rather than proposing a new mathematical conjecture.
There are clients and a parameter vector in . Client has a differentiable convex objective . The global objective is . Every local gradient is -Lipschitz for the same . Fix a global minimizer of and a deterministic initial model , and write .
Every client participates in every round. Each of rounds consists of local steps with constant learning rate . If is client 's state after local steps of round , its next state is . At the next round all clients restart from the average of the preceding round's terminal states. The shadow iterate is ; it is defined even at local steps where clients do not communicate.
On a probability space , the history before a step contains all past oracle draws. The stochastic gradients are conditionally unbiased, their conditional squared errors have expectation at most , and the different clients' current gradients are conditionally independent. The heterogeneity bound is for every client and every point, where . These are the assumptions of Section 6.1.1, PDF p. 40, equations (11)–(14), with the history and independence convention used explicitly in Appendix D.1 immediately after equation (27), PDF p. 87.
The principal goal is Theorem 1, equation (15). For , establish
Two source milestones describe the intermediate results. Lemma 1 bounds the conditional average loss within a round by the decrease of squared distance to the minimizer, plus a noise term and a sum of client disagreements. Lemma 2 bounds each conditional squared disagreement by . Both are stated on PDF p. 41, Section 6.1.2, with proofs in Appendix D, PDF pp. 86–88. They remain genuine open proof obligations; the algorithm model does not assume either estimate.
An additional milestone records the same theorem's tuned-step consequence, equations (16)–(17), in the regime . With
the same expected loss is at most
The principal goal includes zero-noise and zero-heterogeneity cases. The extra positivity conditions apply only to the printed tuned-step formula, whose denominators otherwise require separate conventions.
The bound separates an initial-distance term, a noise term improved by the number of clients, and two costs of local updates. It quantifies how local work interacts with stochastic noise and differing client objectives. Its conclusion concerns the average objective gap along the post-update shadow sequence; it does not assert the same bound for every last iterate or for the average of client losses. These distinctions follow directly from the quantity defined in equation (14).
A completed formalization would provide reusable checked components for stochastic optimization: finite client averages, history-conditioned oracle assumptions, per-round potential estimates, and disagreement bounds. The paper supplies the mathematical proof; this draft supplies checked statements and definitions. No convergence proof is claimed by creating or compiling the proposal.
The average update evaluates each gradient at its own client's state. It therefore does not directly equal a centralized stochastic-gradient step at the shadow iterate. A proof must control that discrepancy quantitatively, preserve the conditioning on the round's starting history, and justify the noise improvement using independent client sampling. Ignoring the sampling relationship can invalidate the advertised bound even for scalar quadratic objectives.
The model uses finite-dimensional real Euclidean space, including the harmless zero-dimensional case, and a standard Borel probability space. A filtration indexed by records the full past. Local states and gradients carry explicit measurability and finite-second-moment conditions. These probability conventions support actual Bochner and conditional expectations; integrals are not treated as arbitrary total functions without analytic obligations.
The local objectives, global objective, gradients, iterates, and shadow averages are concrete functions. The model assumes neither a drift bound nor a progress bound. Source hypotheses are uniform in the model point, and the minimizer is an actual minimizer of the averaged objective. Unequal weighting, partial client participation, nonconvex objectives, adaptive step sizes, and privacy mechanisms are outside this particular theorem. Contributions should prove the named source lemmas or their necessary analytic infrastructure while retaining these statements.
namespace FedAvg
theorem ConvexFedAvgConvergence :
∀ (d M : ℕ) (P : Problem d M) (Ω : Type u) [MeasurableSpace Ω]
[StandardBorelSpace Ω] (μ : Measure Ω) [IsProbabilityMeasure μ]
(τ T : ℕ) (η : ℝ),
0 < τ → 0 < T → 0 < η → η ≤ 1 / (4 * P.L) →
∀ R : Run P μ τ T η, (∫ ω, avgLoss R ω ∂μ) ≤ convergenceRHS P τ T η := by sorry
end FedAvgFor and ,
Formalization note: direct source theorem, precisely equation (15). Zero noise, zero heterogeneity, and zero initial distance are included. The quantity is average post-update shadow loss, not a last-iterate guarantee.
Source: Jianyu Wang et al., A Field Guide to Federated Optimization, arXiv:2107.06917v1, https://arxiv.org/abs/2107.06917v1; Section 6.1.2, PDF p. 41, Theorem 1, equation (15).
There are clients with convex differentiable -smooth functions , , and . Let minimize , let be deterministic, and let . The finite-dimensional space permits . On a standard Borel probability space , contains the full history before step . All clients participate and use uniform weights. Starting from , ; each subsequent round starts all clients at the preceding round's terminal average. The states are history-measurable and square integrable; gradients are measurable at the next step and square integrable. Conditional on the current history, client gradients are independent, have means , and their squared errors have expectations at most , with . The uniform heterogeneity condition is for every , with . Write , , and . Conditional statements hold almost surely.
Formalization note: the model makes the source's full-history stochastic-oracle convention explicit. Independence is used in Appendix D.1 immediately after equation (27), PDF p. 87. The moment/measurability and standard Borel conditions are explicit analytic conventions. No convergence or intermediate bound is assumed in the model. The source is Wang et al., A Field Guide to Federated Optimization, Section 6.1.1, PDF p. 40, equations (11)–(14), and Section 6.1.2, PDF p. 41, Theorem 1: https://arxiv.org/abs/2107.06917v1.
No open leaves. Every sub-goal is proved or awaiting decomposition.