SCAFFOLD objectives, option II updates, oracle, and output statistics
DefinitionSCAFFOLD_ModelFormalization note: a source-backed definition bundle for actual option II algorithm runs and output statistics, with explicit stochastic-oracle conventions. It asserts no convergence theorem.
Notation and probability model
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.
import Mathlib.Analysis.Calculus.Gradient.Basic
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
/-!
SCAFFOLD option II: Karimireddy et al., arXiv:1910.06378v4, Algorithm 1 (PDF p. 4),
Appendix B.1 (PDF p. 14), Appendix E (PDF pp. 25–26), equations (18)–(22).
The model uses the average-gradient control update, avoiding the sign typo in (19).
Sampling occurs after virtual client trajectories; these trajectories are independent of the
current sampled subset, as stipulated in the paragraph following (22).
-/
noncomputable section
open MeasureTheory ProbabilityTheory
open scoped BigOperators
namespace SCAFFOLD
abbrev Space (d : ℕ) := EuclideanSpace ℝ (Fin d)
def objective {d N : ℕ} (f : Fin N → Space d → ℝ) (x : Space d) : ℝ :=
(N : ℝ)⁻¹ * ∑ i, f i x
structure Problem (d N : ℕ) where
clients_pos : 0 < N
f : Fin N → Space d → ℝ
β : ℝ
σ : ℝ
x0 : Space d
smoothness_pos : 0 < β
noise_nonneg : 0 ≤ σ
hasGradient : ∀ i x, HasGradientAt (f i) (gradient (f i) x) x
smooth : ∀ i x y, ‖gradient (f i) x - gradient (f i) y‖ ≤ β * ‖x - y‖
def Convexity {d N : ℕ} (P : Problem d N) (μ : ℝ) : Prop :=
0 ≤ μ ∧ ∀ i x y, P.f i x + inner ℝ (gradient (P.f i) x) (y - x) +
μ / 2 * ‖y - x‖ ^ 2 ≤ P.f i y
def IsMinimizer {d N : ℕ} (P : Problem d N) (xstar : Space d) : Prop :=
∀ x, objective P.f xstar ≤ objective P.f x
/-- `none` chooses the K-sample warm start; `some c0` fixes deterministic controls. -/
abbrev Initialization (d N : ℕ) := Option (Fin N → Space d)
def roundTime (K r : ℕ) := K + r * (K + 1)
def effectiveStep (K : ℕ) (ηl ηg : ℝ) : ℝ := (K : ℝ) * ηl * ηg
variable {d N : ℕ} {Ω : Type*} [mΩ : MeasurableSpace Ω] [StandardBorelSpace Ω]
(P : Problem d N) (ν : Measure Ω) [IsProbabilityMeasure ν]
(S K T : ℕ) (ηl ηg : ℝ) (init : Initialization d N)
/-- A finite run with fresh conditional stochastic gradients and uniform client sampling.
No descent estimate or convergence conclusion is a field of this structure. -/
structure Run where
sample_pos : 0 < S
sample_le : S ≤ N
steps_pos : 0 < K
rounds_pos : 0 < T
history : Filtration ℕ mΩ
warm : ℕ → Fin N → Ω → Space d
x : ℕ → Ω → Space d
c : ℕ → Fin N → Ω → Space d
y : ℕ → ℕ → Fin N → Ω → Space d
g : ℕ → ℕ → Fin N → Ω → Space d
sample : ℕ → Ω → Finset (Fin N)
warm_adapted : ∀ k, k < K → ∀ i, StronglyMeasurable[history (k + 1)] (warm k i)
warm_memLp : ∀ k, k < K → ∀ i, MemLp (warm k i) 2 ν
warm_unbiased : ∀ k, k < K → ∀ i,
ν[warm k i | history k] =ᵐ[ν] fun _ ↦ gradient (P.f i) P.x0
warm_variance : ∀ k, k < K → ∀ i,
ν[(fun ω ↦ ‖warm k i ω - gradient (P.f i) P.x0‖ ^ 2) | history k]
≤ᵐ[ν] fun _ ↦ P.σ ^ 2
warm_independent : ∀ k, k < K → iCondIndepFun (history k) (history.le _) (warm k) ν
x_adapted : ∀ r, r ≤ T → StronglyMeasurable[history (roundTime K r)] (x r)
x_memLp : ∀ r, r ≤ T → MemLp (x r) 2 ν
c_adapted : ∀ r, r ≤ T → ∀ i,
StronglyMeasurable[history (roundTime K r)] (c r i)
c_memLp : ∀ r, r ≤ T → ∀ i, MemLp (c r i) 2 ν
y_adapted : ∀ r, r < T → ∀ k, k ≤ K → ∀ i,
StronglyMeasurable[history (roundTime K r + k)] (y r k i)
y_memLp : ∀ r, r < T → ∀ k, k ≤ K → ∀ i, MemLp (y r k i) 2 ν
g_adapted : ∀ r, r < T → ∀ k, k < K → ∀ i,
StronglyMeasurable[history (roundTime K r + k + 1)] (g r k i)
g_memLp : ∀ r, r < T → ∀ k, k < K → ∀ i, MemLp (g r k i) 2 ν
unbiased : ∀ r, r < T → ∀ k, k < K → ∀ i,
ν[g r k i | history (roundTime K r + k)] =ᵐ[ν]
fun ω ↦ gradient (P.f i) (y r k i ω)
variance : ∀ r, r < T → ∀ k, k < K → ∀ i,
ν[(fun ω ↦ ‖g r k i ω - gradient (P.f i) (y r k i ω)‖ ^ 2) |
history (roundTime K r + k)] ≤ᵐ[ν] fun _ ↦ P.σ ^ 2
independent : ∀ r, r < T → ∀ k, k < K →
iCondIndepFun (history (roundTime K r + k)) (history.le _) (g r k) ν
sample_card : ∀ r, r < T → ∀ᵐ ω ∂ν, (sample r ω).card = S
sample_adapted : ∀ r, r < T → ∀ A : Finset (Fin N),
StronglyMeasurable[history (roundTime K (r + 1))]
(fun ω ↦ if sample r ω = A then (1 : ℝ) else 0)
sample_uniform : ∀ r, r < T → ∀ A : Finset (Fin N),
ν[(fun ω ↦ if sample r ω = A then (1 : ℝ) else 0) |
history (roundTime K r + K)] =ᵐ[ν]
fun _ ↦ if A.card = S then (Nat.choose N S : ℝ)⁻¹ else 0
initial_x : x 0 =ᵐ[ν] fun _ ↦ P.x0
initial_c : ∀ i, c 0 i =ᵐ[ν] fun ω ↦
match init with
| some c0 => c0 i
| none => (K : ℝ)⁻¹ • ∑ k ∈ Finset.range K, warm k i ω
start : ∀ r, r < T → ∀ i, y r 0 i =ᵐ[ν] x r
local_update : ∀ r, r < T → ∀ k, k < K → ∀ i,
y r (k + 1) i =ᵐ[ν] fun ω ↦ y r k i ω -
ηl • (g r k i ω - c r i ω + (N : ℝ)⁻¹ • ∑ j, c r j ω)
control_update : ∀ r, r < T → ∀ i,
c (r + 1) i =ᵐ[ν] fun ω ↦ if i ∈ sample r ω then
(K : ℝ)⁻¹ • ∑ k ∈ Finset.range K, g r k i ω else c r i ω
server_update : ∀ r, r < T → x (r + 1) =ᵐ[ν] fun ω ↦
x r ω + (ηg / (S : ℝ)) • ∑ i ∈ sample r ω, (y r K i ω - x r ω)
variable {P ν S K T ηl ηg init}
def initialControlError (P : Problem d N) (c0 : Fin N → Space d) (xstar : Space d) : ℝ :=
(N : ℝ)⁻¹ * ∑ i, ‖c0 i - gradient (P.f i) xstar‖ ^ 2
def initialPotential (P : Problem d N) (S : ℕ) (h : ℝ)
(c0 : Fin N → Space d) (xstar : Space d) : ℝ :=
‖P.x0 - xstar‖ ^ 2 + 9 * (N : ℝ) * h ^ 2 / (S : ℝ) *
initialControlError P c0 xstar
def weight (μ h : ℝ) (r : ℕ) : ℝ := (1 - μ * h / 2)⁻¹ ^ (r + 1)
def weightSum (μ h : ℝ) (T : ℕ) : ℝ := ∑ r ∈ Finset.range T, weight μ h r
def expectedGap (A : Run P ν S K T ηl ηg init) (xstar : Space d) (r : ℕ) : ℝ :=
∫ ω, objective P.f (A.x r ω) - objective P.f xstar ∂ν
def weightedGap (A : Run P ν S K T ηl ηg init) (xstar : Space d) (μ : ℝ) : ℝ :=
(weightSum μ (effectiveStep K ηl ηg) T)⁻¹ * ∑ r ∈ Finset.range T,
weight μ (effectiveStep K ηl ηg) r * expectedGap A xstar r
def averageGradientSq (A : Run P ν S K T ηl ηg init) : ℝ :=
(T : ℝ)⁻¹ * ∑ r ∈ Finset.range T,
∫ ω, ‖gradient (objective P.f) (A.x r ω)‖ ^ 2 ∂ν
def convexRHS (P : Problem d N) (S K T : ℕ) (ηl ηg μ : ℝ)
(c0 : Fin N → Space d) (xstar : Space d) : ℝ :=
let h := effectiveStep K ηl ηg
initialPotential P S h c0 xstar / (h * weightSum μ h T) +
12 * h * P.σ ^ 2 / ((K : ℝ) * (S : ℝ)) * (1 + (S : ℝ) / ηg ^ 2)
def nonconvexRHS (P : Problem d N) (S K T : ℕ) (ηl ηg fLower : ℝ) : ℝ :=
let h := effectiveStep K ηl ηg
14 * (objective P.f P.x0 - fLower) / (h * (T : ℝ)) +
70 * P.β * h * P.σ ^ 2 / ((K : ℝ) * (S : ℝ)) * (1 + (S : ℝ) / ηg ^ 2)
end SCAFFOLD
Read-back
What the Lean code literally says, in plain math · gpt-6
Literal read-back of the model declarations
Read-back model: gpt-6.
Space. For each natural number , this denotes the real Euclidean space , represented by real coordinates indexed by , with its Euclidean inner product and norm. The value is included; the resulting space consists of one vector, the zero vector.
objective. For any natural numbers , any family of functions indexed by , and any , this is the real number . No differentiability, convexity, or positivity of is assumed here. If , the sum and the reciprocal are both zero, so the objective is zero. The dimension is also allowed.
Problem. For natural numbers , an element of this structure supplies a proof that , functions for every , real numbers , and a vector . It also supplies proofs that , , every has a gradient at every , with that gradient equal to the value denoted , and, for every , . The structure imposes no convexity, lower bound, or existence of a minimizer. No such structure exists for ; is permitted. The number has no further constraint in this declaration.
Convexity. Given natural , a problem consisting of differentiable functions with a common positive gradient Lipschitz bound, its other problem data, and a real number , this predicate means that and that, for every client and every , . The inner product is the real Euclidean inner product. The inequality is required separately for every component function, not only their mean. The case is included. When , the displayed inequalities hold automatically and the predicate reduces to .
IsMinimizer. Given natural , a problem with component functions , and a specified vector , this predicate says that for every . It asserts global minimality of that vector for the arithmetic mean, with no uniqueness or componentwise minimality requirement and without asserting that a minimizing vector exists. All problem assumptions, including differentiability, a common positive gradient Lipschitz bound, and nonnegative , remain part of the input. For , its sole vector satisfies this predicate.
Initialization. For any natural , an initialization is either absent, or is a specified deterministic family of vectors indexed by . This type alone imposes no condition on those vectors and performs no sampling or averaging. If , the supplied-family alternative contains the unique empty family and is still distinct from the absent alternative. The case is included.
roundTime. For any natural numbers , this is the natural number . Thus and . No positivity assumption occurs here; when , .
effectiveStep. For a natural number and arbitrary real numbers , this is , with regarded as a real number. Neither step size is assumed positive or nonzero. In particular, if , , or .
Run. Fix natural , a problem with functions having gradients everywhere and satisfying for a real , a real , and ; a type with a specified measurable structure that is standard Borel; a probability measure on that structure; natural numbers ; arbitrary real numbers ; and an initialization that is either absent or a deterministic family . A run supplies proofs that , , and , together with a filtration of the given measurable structure; vector-valued functions , , , , and ; and a function taking values in the finite subsets of . All time indices in these functions range over all natural numbers. Write , and take every conditional expectation, almost-everywhere equality, and almost-everywhere inequality below with respect to . For every and every , is strongly -measurable, belongs to , satisfies almost everywhere, and satisfies almost everywhere; for each such , the entire client-indexed family is conditionally independent given .
For every , and every are strongly -measurable and belong to . For every , , and , is strongly -measurable and belongs to . For every , , and , is strongly -measurable, belongs to , satisfies almost everywhere, and satisfies almost everywhere. For each such , the entire family is conditionally independent given .
For every , almost everywhere; for every fixed subset of the client indices, the real indicator is strongly -measurable and almost everywhere if , and equals zero almost everywhere otherwise. Thus the conditional distribution is specified given the history at , whereas indicator measurability is required at . Initially equals the problem's deterministic almost everywhere. For every , almost everywhere if the initialization supplies a family, and almost everywhere if it is absent. For every and , almost everywhere. For every , , and , the vector equality holds almost everywhere. For every and , when , and otherwise, with this piecewise equality required almost everywhere. Finally, for every , almost everywhere. All local recurrences and gradient conditions range over every client, including clients outside . Warm-up conditions are required even when a deterministic initialization is supplied. No conditions of the displayed types are imposed on function values outside their stated index ranges, and equality is not required on exceptional null sets. No positivity or upper bound is required of either step size, no convexity or minimizer is required, and and are included. A run cannot exist if , , , or .
initialControlError. For natural , a problem with differentiable component functions satisfying its common positive gradient Lipschitz bound, an arbitrary deterministic family , and any , this real number is . No minimizer, convexity, or relation between and a run is assumed. The problem's other data, including and its initial vector, are part of the input but do not occur in this expression. Its value is nonnegative; for , it is zero.
initialPotential. For natural , a problem with differentiable component functions , the problem's common positive gradient Lipschitz bound and nonnegative noise parameter, its initial vector , an arbitrary natural , a real , a deterministic family , and an arbitrary , this is . There is no requirement that , , , or minimize any function. Real division by zero is defined to be zero, so when , or when , this equals . For it is zero.
weight. For arbitrary real and a natural , this real number is . The exponent is the positive natural number . There are no sign or nonvanishing assumptions: if , the reciprocal and hence every weight are zero; if , the sign alternates with the exponent's parity. If , every weight is one.
weightSum. For arbitrary real and natural , this is . If , the empty sum is zero. No positivity of the summands or nonvanishing of their sum is assumed. If , every summand is zero; if the weights have alternating signs, cancellation is allowed. If , the value is the real number .
expectedGap. Fix natural , a problem with component functions having everywhere-defined gradients and a common positive gradient Lipschitz bound, its nonnegative noise parameter and initial vector, a standard Borel measurable space with probability measure , arbitrary real step sizes , either an absent initialization or a deterministic family of client vectors, and a run for those data. In particular the run requires , , and supplies the histories and random vectors subject to all the conditional-moment, independence, sampling, initialization, and recurrence conditions in the run declaration. For any and any natural , this is the real integral , where is the vector function supplied by . No minimality of or convexity is assumed, so a nonnegative gap is not asserted. The index is unrestricted, including , where the run's stated measurability and conditions on need not apply. The real integral is a total operation and equals zero if its integrand is not integrable. The case is included and gives zero.
weightedGap. Fix natural , a problem with differentiable component functions , their common positive gradient Lipschitz bound, a nonnegative noise parameter and an initial vector, a standard Borel measurable space with probability measure , arbitrary real step sizes , an absent or deterministic client-vector initialization, and a run satisfying the run declaration's conditions for these data, including , , and . For any vector and any real , put , , and . This definition is the real number
Here comes from , and each integral is the total real integral, assigned zero when its integrand is not integrable. The indices are through , so is not included. Neither convexity, minimality of , nonnegativity of , nor positive step sizes are required. A zero sum of weights makes the value zero because its reciprocal is zero; in particular this occurs when . Negative weights and cancellation are allowed. When , every weight is one and the expression is the arithmetic mean of the expected gaps. For it is zero.
averageGradientSq. Fix natural , a problem with component functions having gradients everywhere and a common positive gradient Lipschitz bound, its nonnegative noise parameter and initial vector, a standard Borel measurable space with probability measure , arbitrary real step sizes , an absent or deterministic client-vector initialization, and a run satisfying all the run declaration's conditions for these data, including , , and . With and the run's vector functions, this is . It averages the squared Euclidean norm of the gradient of the component mean, over indices through , excluding . There is no convexity, minimizer, lower-bound, or step-size sign assumption. Integrals use the total real integral convention, with value zero for nonintegrable integrands. The denominator is positive because a run is supplied. For the expression is zero.
convexRHS. For natural , a problem supplying differentiable functions with a common positive gradient Lipschitz bound, an initial vector , and a real noise parameter , arbitrary natural numbers , arbitrary real numbers , a deterministic vector family , and an arbitrary vector , put . This definition returns the real number
There is no run argument, no assumption that are positive or that , no sign restriction on either step size or on , no convexity assumption, and no assertion that is a minimizer. The family is arbitrary and need not initialize a run. This is only a definition of a number; it states no bound on any gap. Every reciprocal and division is real and total, with zero reciprocal at zero: a zero denominator makes the corresponding quotient zero. In particular makes the whole expression zero. When , only the first quotient is forced to zero; the noise term remains as written. For the first quotient is zero but the noise term need not be zero, since the supplied need not vanish.
nonconvexRHS. For natural , a problem supplying differentiable functions with a common positive gradient Lipschitz bound , a nonnegative real noise parameter , and an initial vector , arbitrary natural numbers , and arbitrary real numbers , put . This definition returns
No run, positive sample/step/round count, upper bound , or step-size sign condition is required. The real parameter is not assumed to bound any function from below, and the definition does not require that the component functions or their mean fail to be convex. It asserts no inequality involving gradients or any other quantity. All reciprocals and divisions use zero as the reciprocal of zero, so a zero denominator makes its quotient zero. Thus makes the entire expression zero, whereas forces only the first quotient to zero. The case is included, and the expression can still depend on the functions' values, , and the noise parameter.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.