Convex FedAvg model and stochastic oracle
DefinitionFedAvg_ModelThis definition bundle specifies the objectives, algorithm, oracle, and numerical quantities used by Lemmas 1–2 and Theorem 1. It proves none of those estimates.
Notation and probability model
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.
import Mathlib.Analysis.Calculus.Gradient.Basic
import Mathlib.Analysis.Convex.Function
import Mathlib.Analysis.InnerProductSpace.PiL2
import Mathlib.Analysis.Normed.Lp.MeasurableSpace
import Mathlib.Analysis.SpecialFunctions.Pow.Real
import Mathlib.MeasureTheory.Function.L2Space
import Mathlib.Probability.Independence.Conditional
import Mathlib.Probability.Process.Adapted
/-!
Model for Wang et al., *A Field Guide to Federated Optimization*, arXiv:2107.06917v1,
Section 6.1.1, PDF p. 40, equations (11)--(14). Conditional independence of client
gradients is the oracle convention explicitly used in Appendix D.1, PDF pp. 86--87,
equation (27). All second moments below are genuine integrable random variables.
-/
noncomputable section
open MeasureTheory ProbabilityTheory
open scoped BigOperators
namespace FedAvg
abbrev ModelSpace (d : ℕ) := EuclideanSpace ℝ (Fin d)
def objective {d M : ℕ} (f : Fin M → ModelSpace d → ℝ) (x : ModelSpace d) : ℝ :=
(M : ℝ)⁻¹ * ∑ i, f i x
structure Problem (d M : ℕ) where
clients_pos : 0 < M
f : Fin M → ModelSpace d → ℝ
L : ℝ
σ : ℝ
ζ : ℝ
x0 : ModelSpace d
xstar : ModelSpace d
smoothness_pos : 0 < L
noise_nonneg : 0 ≤ σ
heterogeneity_nonneg : 0 ≤ ζ
hasGradient : ∀ i x, HasGradientAt (f i) (gradient (f i) x) x
convex : ∀ i, ConvexOn ℝ Set.univ (f i)
smooth : ∀ i x y, ‖gradient (f i) x - gradient (f i) y‖ ≤ L * ‖x - y‖
heterogeneous : ∀ i x, ‖gradient (f i) x - gradient (objective f) x‖ ≤ ζ
optimal : ∀ x, objective f xstar ≤ objective f x
variable {d M : ℕ} {Ω : Type*} [mΩ : MeasurableSpace Ω] [StandardBorelSpace Ω]
(P : Problem d M) (μ : Measure Ω) [IsProbabilityMeasure μ] (τ T : ℕ) (η : ℝ)
/-- A finite FedAvg run. The history index `t * τ + k` counts local stochastic steps. -/
structure Run where
history : Filtration ℕ mΩ
x : ℕ → ℕ → Fin M → Ω → ModelSpace d
g : ℕ → ℕ → Fin M → Ω → ModelSpace d
x_adapted : ∀ t, t < T → ∀ k, k ≤ τ → ∀ i,
StronglyMeasurable[history (t * τ + k)] (x t k i)
x_squareIntegrable : ∀ t, t < T → ∀ k, k ≤ τ → ∀ i, MemLp (x t k i) 2 μ
g_adapted : ∀ t, t < T → ∀ k, k < τ → ∀ i,
StronglyMeasurable[history (t * τ + k + 1)] (g t k i)
g_squareIntegrable : ∀ t, t < T → ∀ k, k < τ → ∀ i, MemLp (g t k i) 2 μ
unbiased : ∀ t, t < T → ∀ k, k < τ → ∀ i,
μ[g t k i | history (t * τ + k)] =ᵐ[μ] fun ω ↦ gradient (P.f i) (x t k i ω)
variance : ∀ t, t < T → ∀ k, k < τ → ∀ i,
μ[(fun ω ↦ ‖g t k i ω - gradient (P.f i) (x t k i ω)‖ ^ 2) |
history (t * τ + k)] ≤ᵐ[μ] fun _ ↦ P.σ ^ 2
independent : ∀ t, t < T → ∀ k, k < τ →
iCondIndepFun (history (t * τ + k)) (history.le _) (g t k) μ
initial : ∀ i ω, x 0 0 i ω = P.x0
local_update : ∀ t, t < T → ∀ k, k < τ → ∀ i,
x t (k + 1) i =ᵐ[μ] fun ω ↦ x t k i ω - η • g t k i ω
synchronize : ∀ t, t + 1 < T → ∀ i,
x (t + 1) 0 i =ᵐ[μ] fun ω ↦ (M : ℝ)⁻¹ • ∑ j, x t τ j ω
variable {P μ τ T η}
def shadow (R : Run P μ τ T η) (t k : ℕ) (ω : Ω) : ModelSpace d :=
(M : ℝ)⁻¹ • ∑ i, R.x t k i ω
def roundLoss (R : Run P μ τ T η) (t : ℕ) (ω : Ω) : ℝ :=
(τ : ℝ)⁻¹ * ∑ k ∈ Finset.range τ,
(objective P.f (shadow R t (k + 1) ω) - objective P.f P.xstar)
def avgLoss (R : Run P μ τ T η) (ω : Ω) : ℝ :=
(T : ℝ)⁻¹ * ∑ t ∈ Finset.range T, roundLoss R t ω
def distance (P : Problem d M) : ℝ := ‖P.x0 - P.xstar‖
def shadowDistanceSq (R : Run P μ τ T η) (t k : ℕ) (ω : Ω) : ℝ :=
‖shadow R t k ω - P.xstar‖ ^ 2
def clientDriftSq (R : Run P μ τ T η) (t k : ℕ) (i : Fin M) (ω : Ω) : ℝ :=
‖R.x t k i ω - shadow R t k ω‖ ^ 2
def progressTerm (R : Run P μ τ T η) (t : ℕ) (ω : Ω) : ℝ :=
(shadowDistanceSq R t 0 ω - μ[shadowDistanceSq R t τ | R.history (t * τ)] ω) /
(2 * η * (τ : ℝ))
def deviationTerm (R : Run P μ τ T η) (t : ℕ) (ω : Ω) : ℝ :=
η * P.σ ^ 2 / (M : ℝ) + P.L / ((M : ℝ) * (τ : ℝ)) *
∑ i, ∑ k ∈ Finset.range τ, μ[clientDriftSq R t k i | R.history (t * τ)] ω
def progressRHS (R : Run P μ τ T η) (t : ℕ) (ω : Ω) : ℝ :=
progressTerm R t ω + deviationTerm R t ω
def driftRHS (P : Problem d M) (τ : ℕ) (η : ℝ) : ℝ :=
18 * (τ : ℝ) ^ 2 * η ^ 2 * P.ζ ^ 2 + 4 * (τ : ℝ) * η ^ 2 * P.σ ^ 2
def convergenceRHS (P : Problem d M) (τ T : ℕ) (η : ℝ) : ℝ :=
distance P ^ 2 / (2 * η * (τ : ℝ) * (T : ℝ)) + η * P.σ ^ 2 / (M : ℝ) +
4 * (τ : ℝ) * η ^ 2 * P.L * P.σ ^ 2 +
18 * (τ : ℝ) ^ 2 * η ^ 2 * P.L * P.ζ ^ 2
/-- Section 6.1.2, PDF p. 41, equation (16), used only in its nondegenerate regime. -/
def optimizedStep (P : Problem d M) (τ T : ℕ) : ℝ :=
min (1 / (4 * P.L))
(min (Real.sqrt (M : ℝ) * distance P /
(Real.sqrt (τ : ℝ) * Real.sqrt (T : ℝ) * P.σ))
(min (Real.rpow (distance P) (2 / 3 : ℝ) /
(Real.rpow (τ : ℝ) (2 / 3 : ℝ) * Real.rpow (T : ℝ) (1 / 3 : ℝ) *
Real.rpow P.L (1 / 3 : ℝ) * Real.rpow P.σ (2 / 3 : ℝ)))
(Real.rpow (distance P) (2 / 3 : ℝ) /
((τ : ℝ) * Real.rpow (T : ℝ) (1 / 3 : ℝ) *
Real.rpow P.L (1 / 3 : ℝ) * Real.rpow P.ζ (2 / 3 : ℝ)))))
/-- Section 6.1.2, PDF p. 41, equation (17). -/
def optimizedRHS (P : Problem d M) (τ T : ℕ) : ℝ :=
2 * P.L * distance P ^ 2 / ((τ : ℝ) * (T : ℝ)) +
2 * P.σ * distance P / Real.sqrt ((M : ℝ) * (τ : ℝ) * (T : ℝ)) +
5 * Real.rpow P.L (1 / 3 : ℝ) * Real.rpow P.σ (2 / 3 : ℝ) *
Real.rpow (distance P) (4 / 3 : ℝ) /
(Real.rpow (τ : ℝ) (1 / 3 : ℝ) * Real.rpow (T : ℝ) (2 / 3 : ℝ)) +
19 * Real.rpow P.L (1 / 3 : ℝ) * Real.rpow P.ζ (2 / 3 : ℝ) *
Real.rpow (distance P) (4 / 3 : ℝ) / Real.rpow (T : ℝ) (2 / 3 : ℝ)
end FedAvg
Read-back
What the Lean code literally says, in plain math · gpt-6
ModelSpace. For every natural number , the model space is equipped with the Euclidean inner product and norm . The case is included and gives the vector space containing only its zero vector.
objective. For natural numbers , a family indexed by , and , define . This definition itself imposes no positivity, regularity, or convexity assumptions. Real inversion is totalized with , so when the empty sum and hence are zero.
Problem. For natural numbers , a problem is data consisting of , functions for , parameters , and points , together with the following conditions: , , ; for every , has gradient at ; every is convex on the whole space; for every , ; for every , , where ; and for every , . No uniqueness of , clientwise minimization at , strict positivity of or , or positive dimension is required. No such problem exists when .
Run. Given natural numbers , a problem as specified above, a standard Borel measurable space , a probability measure on it, arbitrary natural numbers , and an arbitrary real , the run structure is precisely the following data and conditions. For the specified , a run consists of an increasing filtration of sub--algebras of the ambient measurable space and functions defined for every and client . For every , , and , is strongly -measurable and square-integrable against . For every , , and , is strongly -measurable and square-integrable, and the following hold -almost everywhere: , , and . For each such , the whole family is mutually conditionally independent given ; explicitly, conditional probabilities of intersections of finitely many events with distinct clients and Borel sets equal the products of their conditional probabilities almost everywhere. The initialization holds for every client and every , with no exceptional null set. For each with and each , synchronization satisfies almost everywhere. Define . There is no positivity condition on in this structure. If , all requirements guarded by or are vacuous, but initialization still applies. If , there are no stochastic-gradient or local-update requirements, while the iterate conditions at and any applicable synchronization requirements remain. The values at all natural-number indices still exist even when the stated hypotheses do not constrain them. Square-integrability includes almost-everywhere strong measurability and finiteness of the second norm moment.
shadow. For any such run and any natural numbers and outcome , define its averaged iterate by . This average uses every client, has deterministic weight , and is defined even outside or ; the problem data ensure .
roundLoss. For any such problem and run, any , and , define . Thus it averages the objective excesses at the client-averaged iterates with inner indices , including and excluding . It is defined for arbitrary , and is zero if by the empty-sum and zero-inverse conventions.
avgLoss. For any such problem and run and , define . This is the average of objective values, evaluated at the individual averaged iterates specified in the formula. It is zero if or .
distance. For any problem with , define . It is nonnegative; it is zero whenever the two designated points coincide and always zero when . No probability space or run is an argument of this definition.
shadowDistanceSq. For any such problem and run, , and , define . The definition is valid for all indices, including those outside the run's constrained ranges.
clientDriftSq. For any such problem and run, , client , and , define . This is a separate quantity for every client and every natural-number pair of indices.
progressTerm. For any such problem and run, , and , define . Here is the run's filtration and conditional expectation is the library's selected function version, defined to be zero for nonintegrable inputs. No restriction occurs in this definition. Real division by zero gives zero, so this whole quantity is zero if or .
deviationTerm. For any such problem and run, , and , define . Every conditional expectation is taken given the beginning-of-round -algebra, and each uses the library's selected version and nonintegrable-input zero convention. The inner indices are . If , the double-sum contribution is zero and the expression is .
progressRHS. For any such problem and run, , and , define . Division and conditional expectation have the same totalized conventions just stated; no positivity of or bound on is imposed by this definition.
driftRHS. For any problem, any natural number , and any real , define the scalar . It uses the problem's nonnegative parameters and does not depend on a run, a probability space, a round, or a client. It is zero when or .
convergenceRHS. For any problem, natural numbers , and real , define . Natural numbers in this expression are cast to real numbers. This definition alone does not require positive . In particular its first summand is zero, rather than infinite or undefined, whenever its denominator is zero; if , the entire expression is zero.
optimizedStep. For any problem and natural numbers , put and define . This is the minimum of exactly these four real numbers, with the fractional exponents interpreted using the library's real-power operation and square roots using its real square-root operation. All bases here are nonnegative and are positive. The definition places no strict positivity requirement on . All divisions by zero equal zero; consequently if any of is zero, this minimum is zero.
optimizedRHS. For any problem and natural numbers , define . Fractional powers are real powers of the displayed nonnegative bases. The formula is defined without requiring to be positive; every zero denominator makes that summand zero. In particular if every summand is zero, whereas for only the final summand can remain nonzero.
Confirmed by the mission captain (proposal self-audit).