Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

SCAFFOLD objectives, option II updates, oracle, and output statistics

Definition
SCAFFOLD_Model

by Minghui · Sep 23, 2026 · Mathlib c5ea003 (Lean v4.30.0)

federated-learningprobabilitystochastic-optimization

Formalization 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 N≥1N\ge1N≥1 clients, a model space Rd\mathbb R^dRd (including d=0d=0d=0), differentiable client losses fif_ifi​ with β\betaβ-Lipschitz gradients, β>0\beta>0β>0, and f=N−1∑ifif=N^{-1}\sum_i f_if=N−1∑i​fi​. The starting point x0x^0x0 is deterministic and σ≥0\sigma\ge0σ≥0 bounds within-client stochastic-gradient standard deviation. A run has T≥1T\ge1T≥1 rounds, K≥1K\ge1K≥1 local steps, 1≤S≤N1\le S\le N1≤S≤N clients per round, local step ηl>0\eta_l>0ηl​>0, global step ηg≥1\eta_g\ge1ηg​≥1, and h=Kηlηgh=K\eta_l\eta_gh=Kηl​ηg​. All random variables live on a standard Borel probability space (Ω,A,ν)(\Omega,\mathcal A,\nu)(Ω,A,ν) 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 σ2\sigma^2σ2, 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 yi,0r=xry_{i,0}^r=x^ryi,0r​=xr:

yi,k+1r=yi,kr−ηl(gi,kr−cir+cr),cr=N−1∑icir.y_{i,k+1}^r=y_{i,k}^r-\eta_l(g_{i,k}^r-c_i^r+c^r),\qquad c^r=N^{-1}\sum_i c_i^r.yi,k+1r​=yi,kr​−ηl​(gi,kr​−cir​+cr),cr=N−1i∑​cir​.

Then an SSS-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 K−1∑k=0K−1gi,krK^{-1}\sum_{k=0}^{K-1}g_{i,k}^rK−1∑k=0K−1​gi,kr​; other controls persist. The server update is xr+1=xr+(ηg/S)∑i∈Sr(yi,Kr−xr)x^{r+1}=x^r+(\eta_g/S)\sum_{i\in\mathcal S_r}(y_{i,K}^r-x^r)xr+1=xr+(ηg​/S)∑i∈Sr​​(yi,Kr​−xr). 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, x⋆x^\starx⋆ minimizes fff, and the client losses obey

fi(y)≥fi(x)+⟨∇fi(x),y−x⟩+μ2∥y−x∥2,μ≥0.f_i(y)\ge f_i(x)+\langle\nabla f_i(x),y-x\rangle +\frac\mu2\|y-x\|^2,\qquad \mu\ge0.fi​(y)≥fi​(x)+⟨∇fi​(x),y−x⟩+2μ​∥y−x∥2,μ≥0.

The initial client controls ci0c_i^0ci0​ are arbitrary deterministic vectors and the server control is their average. Define

C0=1N∑i∥ci0−∇fi(x⋆)∥2,V0=∥x0−x⋆∥2+9Nh2SC0.C_0=\frac1N\sum_i\|c_i^0-\nabla f_i(x^\star)\|^2,\qquad V_0=\|x^0-x^\star\|^2+\frac{9Nh^2}{S}C_0.C0​=N1​i∑​∥ci0​−∇fi​(x⋆)∥2,V0​=∥x0−x⋆∥2+S9Nh2​C0​.

For nonconvex targets, flow≤f(x)f_{\rm low}\le f(x)flow​≤f(x) for all xxx; a minimizer need not exist. Each ci0c_i^0ci0​ is instead initialized by averaging KKK fresh stochastic gradients at x0x^0x0, with the same conditional oracle assumptions. These full-client initialization queries are additional to the TTT optimization rounds.

The output is a sampled pre-round server iterate among x0,…,xT−1x^0,\ldots,x^{T-1}x0,…,xT−1, 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.

Definition code
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
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 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); Appendix E.2, PDF p. 31, equations (26)–(27), and PDF p. 35 final paragraph.
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 ddd, this denotes the real Euclidean space Rd\mathbb R^dRd, represented by real coordinates indexed by {0,…,d−1}\{0,\ldots,d-1\}{0,…,d−1}, with its Euclidean inner product and norm. The value d=0d=0d=0 is included; the resulting space consists of one vector, the zero vector.

objective. For any natural numbers d,Nd,Nd,N, any family of functions fi:Rd→Rf_i:\mathbb R^d\to\mathbb Rfi​:Rd→R indexed by i∈{0,…,N−1}i\in\{0,\ldots,N-1\}i∈{0,…,N−1}, and any x∈Rdx\in\mathbb R^dx∈Rd, this is the real number N−1∑i=0N−1fi(x)N^{-1}\sum_{i=0}^{N-1}f_i(x)N−1∑i=0N−1​fi​(x). No differentiability, convexity, or positivity of NNN is assumed here. If N=0N=0N=0, the sum and the reciprocal are both zero, so the objective is zero. The dimension d=0d=0d=0 is also allowed.

Problem. For natural numbers d,Nd,Nd,N, an element of this structure supplies a proof that N>0N>0N>0, functions fi:Rd→Rf_i:\mathbb R^d\to\mathbb Rfi​:Rd→R for every 0≤i<N0\le i<N0≤i<N, real numbers β,σ\beta,\sigmaβ,σ, and a vector x0∈Rdx_0\in\mathbb R^dx0​∈Rd. It also supplies proofs that β>0\beta>0β>0, σ≥0\sigma\ge0σ≥0, every fif_ifi​ has a gradient at every xxx, with that gradient equal to the value denoted ∇fi(x)\nabla f_i(x)∇fi​(x), and, for every i,x,yi,x,yi,x,y, ∥∇fi(x)−∇fi(y)∥≤β∥x−y∥\|\nabla f_i(x)-\nabla f_i(y)\|\le\beta\|x-y\|∥∇fi​(x)−∇fi​(y)∥≤β∥x−y∥. The structure imposes no convexity, lower bound, or existence of a minimizer. No such structure exists for N=0N=0N=0; d=0d=0d=0 is permitted. The number σ\sigmaσ has no further constraint in this declaration.

Convexity. Given natural d,Nd,Nd,N, a problem PPP consisting of N>0N>0N>0 differentiable functions fi:Rd→Rf_i:\mathbb R^d\to\mathbb Rfi​:Rd→R with a common positive gradient Lipschitz bound, its other problem data, and a real number μ\muμ, this predicate means that μ≥0\mu\ge0μ≥0 and that, for every client iii and every x,y∈Rdx,y\in\mathbb R^dx,y∈Rd, fi(x)+⟨∇fi(x),y−x⟩+(μ/2)∥y−x∥2≤fi(y)f_i(x)+\langle\nabla f_i(x),y-x\rangle+(\mu/2)\|y-x\|^2\le f_i(y)fi​(x)+⟨∇fi​(x),y−x⟩+(μ/2)∥y−x∥2≤fi​(y). The inner product is the real Euclidean inner product. The inequality is required separately for every component function, not only their mean. The case μ=0\mu=0μ=0 is included. When d=0d=0d=0, the displayed inequalities hold automatically and the predicate reduces to μ≥0\mu\ge0μ≥0.

IsMinimizer. Given natural d,Nd,Nd,N, a problem PPP with N>0N>0N>0 component functions fi:Rd→Rf_i:\mathbb R^d\to\mathbb Rfi​:Rd→R, and a specified vector x⋆∈Rdx_\star\in\mathbb R^dx⋆​∈Rd, this predicate says that N−1∑i=0N−1fi(x⋆)≤N−1∑i=0N−1fi(x)N^{-1}\sum_{i=0}^{N-1}f_i(x_\star)\le N^{-1}\sum_{i=0}^{N-1}f_i(x)N−1∑i=0N−1​fi​(x⋆​)≤N−1∑i=0N−1​fi​(x) for every x∈Rdx\in\mathbb R^dx∈Rd. 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 σ\sigmaσ, remain part of the input. For d=0d=0d=0, its sole vector satisfies this predicate.

Initialization. For any natural d,Nd,Nd,N, an initialization is either absent, or is a specified deterministic family of vectors ci0∈Rdc_i^0\in\mathbb R^dci0​∈Rd indexed by 0≤i<N0\le i<N0≤i<N. This type alone imposes no condition on those vectors and performs no sampling or averaging. If N=0N=0N=0, the supplied-family alternative contains the unique empty family and is still distinct from the absent alternative. The case d=0d=0d=0 is included.

roundTime. For any natural numbers K,rK,rK,r, this is the natural number tr=K+r(K+1)t_r=K+r(K+1)tr​=K+r(K+1). Thus t0=Kt_0=Kt0​=K and tr+1=tr+K+1t_{r+1}=t_r+K+1tr+1​=tr​+K+1. No positivity assumption occurs here; when K=0K=0K=0, tr=rt_r=rtr​=r.

effectiveStep. For a natural number KKK and arbitrary real numbers ηl,ηg\eta_l,\eta_gηl​,ηg​, this is h=Kηlηgh=K\eta_l\eta_gh=Kηl​ηg​, with KKK regarded as a real number. Neither step size is assumed positive or nonzero. In particular, h=0h=0h=0 if K=0K=0K=0, ηl=0\eta_l=0ηl​=0, or ηg=0\eta_g=0ηg​=0.

Run. Fix natural d,Nd,Nd,N, a problem PPP with N>0N>0N>0 functions fi:Rd→Rf_i:\mathbb R^d\to\mathbb Rfi​:Rd→R having gradients everywhere and satisfying ∥∇fi(u)−∇fi(v)∥≤β∥u−v∥\|\nabla f_i(u)-\nabla f_i(v)\|\le\beta\|u-v\|∥∇fi​(u)−∇fi​(v)∥≤β∥u−v∥ for a real β>0\beta>0β>0, a real σ≥0\sigma\ge0σ≥0, and x0∈Rdx_0\in\mathbb R^dx0​∈Rd; a type Ω\OmegaΩ with a specified measurable structure that is standard Borel; a probability measure ν\nuν on that structure; natural numbers S,K,TS,K,TS,K,T; arbitrary real numbers ηl,ηg\eta_l,\eta_gηl​,ηg​; and an initialization that is either absent or a deterministic family ci0∈Rdc_i^0\in\mathbb R^dci0​∈Rd. A run supplies proofs that 0<S≤N0<S\le N0<S≤N, K>0K>0K>0, and T>0T>0T>0, together with a filtration (Fn)n∈N(\mathcal F_n)_{n\in\mathbb N}(Fn​)n∈N​ of the given measurable structure; vector-valued functions wk,i(ω)w_{k,i}(\omega)wk,i​(ω), xr(ω)x_r(\omega)xr​(ω), cr,i(ω)c_{r,i}(\omega)cr,i​(ω), yr,k,i(ω)y_{r,k,i}(\omega)yr,k,i​(ω), and gr,k,i(ω)g_{r,k,i}(\omega)gr,k,i​(ω); and a function Jr(ω)J_r(\omega)Jr​(ω) taking values in the finite subsets of {0,…,N−1}\{0,\ldots,N-1\}{0,…,N−1}. All time indices in these functions range over all natural numbers. Write tr=K+r(K+1)t_r=K+r(K+1)tr​=K+r(K+1), and take every conditional expectation, almost-everywhere equality, and almost-everywhere inequality below with respect to ν\nuν. For every k<Kk<Kk<K and every iii, wk,iw_{k,i}wk,i​ is strongly Fk+1\mathcal F_{k+1}Fk+1​-measurable, belongs to L2(ν)L^2(\nu)L2(ν), satisfies Eν[wk,i∣Fk]=∇fi(x0)\mathbb E_\nu[w_{k,i}\mid\mathcal F_k]=\nabla f_i(x_0)Eν​[wk,i​∣Fk​]=∇fi​(x0​) almost everywhere, and satisfies Eν[∥wk,i−∇fi(x0)∥2∣Fk]≤σ2\mathbb E_\nu[\|w_{k,i}-\nabla f_i(x_0)\|^2\mid\mathcal F_k]\le\sigma^2Eν​[∥wk,i​−∇fi​(x0​)∥2∣Fk​]≤σ2 almost everywhere; for each such kkk, the entire client-indexed family (wk,i)i=0N−1(w_{k,i})_{i=0}^{N-1}(wk,i​)i=0N−1​ is conditionally independent given Fk\mathcal F_kFk​. For every r≤Tr\le Tr≤T, xrx_rxr​ and every cr,ic_{r,i}cr,i​ are strongly Ftr\mathcal F_{t_r}Ftr​​-measurable and belong to L2(ν)L^2(\nu)L2(ν). For every r<Tr<Tr<T, k≤Kk\le Kk≤K, and iii, yr,k,iy_{r,k,i}yr,k,i​ is strongly Ftr+k\mathcal F_{t_r+k}Ftr​+k​-measurable and belongs to L2(ν)L^2(\nu)L2(ν). For every r<Tr<Tr<T, k<Kk<Kk<K, and iii, gr,k,ig_{r,k,i}gr,k,i​ is strongly Ftr+k+1\mathcal F_{t_r+k+1}Ftr​+k+1​-measurable, belongs to L2(ν)L^2(\nu)L2(ν), satisfies Eν[gr,k,i∣Ftr+k]=∇fi(yr,k,i)\mathbb E_\nu[g_{r,k,i}\mid\mathcal F_{t_r+k}]=\nabla f_i(y_{r,k,i})Eν​[gr,k,i​∣Ftr​+k​]=∇fi​(yr,k,i​) almost everywhere, and satisfies Eν[∥gr,k,i−∇fi(yr,k,i)∥2∣Ftr+k]≤σ2\mathbb E_\nu[\|g_{r,k,i}-\nabla f_i(y_{r,k,i})\|^2\mid\mathcal F_{t_r+k}]\le\sigma^2Eν​[∥gr,k,i​−∇fi​(yr,k,i​)∥2∣Ftr​+k​]≤σ2 almost everywhere. For each such r,kr,kr,k, the entire family (gr,k,i)i=0N−1(g_{r,k,i})_{i=0}^{N-1}(gr,k,i​)i=0N−1​ is conditionally independent given Ftr+k\mathcal F_{t_r+k}Ftr​+k​. For every r<Tr<Tr<T, ∣Jr∣=S|J_r|=S∣Jr​∣=S almost everywhere; for every fixed subset AAA of the client indices, the real indicator 1{Jr=A}\mathbf 1_{\{J_r=A\}}1{Jr​=A}​ is strongly Ftr+1\mathcal F_{t_{r+1}}Ftr+1​​-measurable and Eν[1{Jr=A}∣Ftr+K]=(NS)−1\mathbb E_\nu[\mathbf 1_{\{J_r=A\}}\mid\mathcal F_{t_r+K}]=\binom NS^{-1}Eν​[1{Jr​=A}​∣Ftr​+K​]=(SN​)−1 almost everywhere if ∣A∣=S|A|=S∣A∣=S, and equals zero almost everywhere otherwise. Thus the conditional distribution is specified given the history at tr+Kt_r+Ktr​+K, whereas indicator measurability is required at tr+K+1=tr+1t_r+K+1=t_{r+1}tr​+K+1=tr+1​. Initially x0(ω)x_0(\omega)x0​(ω) equals the problem's deterministic x0x_0x0​ almost everywhere. For every iii, c0,i(ω)=ci0c_{0,i}(\omega)=c_i^0c0,i​(ω)=ci0​ almost everywhere if the initialization supplies a family, and c0,i(ω)=K−1∑k=0K−1wk,i(ω)c_{0,i}(\omega)=K^{-1}\sum_{k=0}^{K-1}w_{k,i}(\omega)c0,i​(ω)=K−1∑k=0K−1​wk,i​(ω) almost everywhere if it is absent. For every r<Tr<Tr<T and iii, yr,0,i=xry_{r,0,i}=x_ryr,0,i​=xr​ almost everywhere. For every r<Tr<Tr<T, k<Kk<Kk<K, and iii, the vector equality yr,k+1,i=yr,k,i−ηl(gr,k,i−cr,i+N−1∑j=0N−1cr,j)y_{r,k+1,i}=y_{r,k,i}-\eta_l\bigl(g_{r,k,i}-c_{r,i}+N^{-1}\sum_{j=0}^{N-1}c_{r,j}\bigr)yr,k+1,i​=yr,k,i​−ηl​(gr,k,i​−cr,i​+N−1∑j=0N−1​cr,j​) holds almost everywhere. For every r<Tr<Tr<T and iii, cr+1,i(ω)=K−1∑k=0K−1gr,k,i(ω)c_{r+1,i}(\omega)=K^{-1}\sum_{k=0}^{K-1}g_{r,k,i}(\omega)cr+1,i​(ω)=K−1∑k=0K−1​gr,k,i​(ω) when i∈Jr(ω)i\in J_r(\omega)i∈Jr​(ω), and cr+1,i(ω)=cr,i(ω)c_{r+1,i}(\omega)=c_{r,i}(\omega)cr+1,i​(ω)=cr,i​(ω) otherwise, with this piecewise equality required almost everywhere. Finally, for every r<Tr<Tr<T, xr+1(ω)=xr(ω)+(ηg/S)∑i∈Jr(ω)(yr,K,i(ω)−xr(ω))x_{r+1}(\omega)=x_r(\omega)+(\eta_g/S)\sum_{i\in J_r(\omega)}(y_{r,K,i}(\omega)-x_r(\omega))xr+1​(ω)=xr​(ω)+(ηg​/S)∑i∈Jr​(ω)​(yr,K,i​(ω)−xr​(ω)) almost everywhere. All local recurrences and gradient conditions range over every client, including clients outside JrJ_rJr​. 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 d=0d=0d=0 and σ=0\sigma=0σ=0 are included. A run cannot exist if S=0S=0S=0, S>NS>NS>N, K=0K=0K=0, or T=0T=0T=0.

initialControlError. For natural d,Nd,Nd,N, a problem PPP with N>0N>0N>0 differentiable component functions fi:Rd→Rf_i:\mathbb R^d\to\mathbb Rfi​:Rd→R satisfying its common positive gradient Lipschitz bound, an arbitrary deterministic family ci0∈Rdc_i^0\in\mathbb R^dci0​∈Rd, and any x⋆∈Rdx_\star\in\mathbb R^dx⋆​∈Rd, this real number is N−1∑i=0N−1∥ci0−∇fi(x⋆)∥2N^{-1}\sum_{i=0}^{N-1}\|c_i^0-\nabla f_i(x_\star)\|^2N−1∑i=0N−1​∥ci0​−∇fi​(x⋆​)∥2. No minimizer, convexity, or relation between ci0c_i^0ci0​ and a run is assumed. The problem's other data, including σ≥0\sigma\ge0σ≥0 and its initial vector, are part of the input but do not occur in this expression. Its value is nonnegative; for d=0d=0d=0, it is zero.

initialPotential. For natural d,Nd,Nd,N, a problem PPP with N>0N>0N>0 differentiable component functions fi:Rd→Rf_i:\mathbb R^d\to\mathbb Rfi​:Rd→R, the problem's common positive gradient Lipschitz bound and nonnegative noise parameter, its initial vector x0x_0x0​, an arbitrary natural SSS, a real hhh, a deterministic family ci0∈Rdc_i^0\in\mathbb R^dci0​∈Rd, and an arbitrary x⋆∈Rdx_\star\in\mathbb R^dx⋆​∈Rd, this is ∥x0−x⋆∥2+(9Nh2/S)(N−1∑i=0N−1∥ci0−∇fi(x⋆)∥2)\|x_0-x_\star\|^2+(9Nh^2/S)\bigl(N^{-1}\sum_{i=0}^{N-1}\|c_i^0-\nabla f_i(x_\star)\|^2\bigr)∥x0​−x⋆​∥2+(9Nh2/S)(N−1∑i=0N−1​∥ci0​−∇fi​(x⋆​)∥2). There is no requirement that S>0S>0S>0, S≤NS\le NS≤N, h>0h>0h>0, or x⋆x_\starx⋆​ minimize any function. Real division by zero is defined to be zero, so when S=0S=0S=0, or when h=0h=0h=0, this equals ∥x0−x⋆∥2\|x_0-x_\star\|^2∥x0​−x⋆​∥2. For d=0d=0d=0 it is zero.

weight. For arbitrary real μ,h\mu,hμ,h and a natural rrr, this real number is ((1−μh/2)−1)r+1((1-\mu h/2)^{-1})^{r+1}((1−μh/2)−1)r+1. The exponent is the positive natural number r+1r+1r+1. There are no sign or nonvanishing assumptions: if 1−μh/2=01-\mu h/2=01−μh/2=0, the reciprocal and hence every weight are zero; if 1−μh/2<01-\mu h/2<01−μh/2<0, the sign alternates with the exponent's parity. If μh=0\mu h=0μh=0, every weight is one.

weightSum. For arbitrary real μ,h\mu,hμ,h and natural TTT, this is WT(μ,h)=∑r=0T−1((1−μh/2)−1)r+1W_T(\mu,h)=\sum_{r=0}^{T-1}((1-\mu h/2)^{-1})^{r+1}WT​(μ,h)=∑r=0T−1​((1−μh/2)−1)r+1. If T=0T=0T=0, the empty sum is zero. No positivity of the summands or nonvanishing of their sum is assumed. If 1−μh/2=01-\mu h/2=01−μh/2=0, every summand is zero; if the weights have alternating signs, cancellation is allowed. If μh=0\mu h=0μh=0, the value is the real number TTT.

expectedGap. Fix natural d,N,S,K,Td,N,S,K,Td,N,S,K,T, a problem PPP with N>0N>0N>0 component functions fi:Rd→Rf_i:\mathbb R^d\to\mathbb Rfi​:Rd→R having everywhere-defined gradients and a common positive gradient Lipschitz bound, its nonnegative noise parameter and initial vector, a standard Borel measurable space Ω\OmegaΩ with probability measure ν\nuν, arbitrary real step sizes ηl,ηg\eta_l,\eta_gηl​,ηg​, either an absent initialization or a deterministic family of client vectors, and a run AAA for those data. In particular the run requires 0<S≤N0<S\le N0<S≤N, K>0K>0K>0, T>0T>0T>0 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 x⋆∈Rdx_\star\in\mathbb R^dx⋆​∈Rd and any natural rrr, this is the real integral ∫Ω(N−1∑i=0N−1fi(xr(ω))−N−1∑i=0N−1fi(x⋆)) dν(ω)\int_\Omega\bigl(N^{-1}\sum_{i=0}^{N-1}f_i(x_r(\omega))-N^{-1}\sum_{i=0}^{N-1}f_i(x_\star)\bigr)\,d\nu(\omega)∫Ω​(N−1∑i=0N−1​fi​(xr​(ω))−N−1∑i=0N−1​fi​(x⋆​))dν(ω), where xrx_rxr​ is the vector function supplied by AAA. No minimality of x⋆x_\starx⋆​ or convexity is assumed, so a nonnegative gap is not asserted. The index rrr is unrestricted, including r>Tr>Tr>T, where the run's stated measurability and L2L^2L2 conditions on xrx_rxr​ need not apply. The real integral is a total operation and equals zero if its integrand is not integrable. The case d=0d=0d=0 is included and gives zero.

weightedGap. Fix natural d,N,S,K,Td,N,S,K,Td,N,S,K,T, a problem PPP with N>0N>0N>0 differentiable component functions fi:Rd→Rf_i:\mathbb R^d\to\mathbb Rfi​:Rd→R, their common positive gradient Lipschitz bound, a nonnegative noise parameter and an initial vector, a standard Borel measurable space Ω\OmegaΩ with probability measure ν\nuν, arbitrary real step sizes ηl,ηg\eta_l,\eta_gηl​,ηg​, an absent or deterministic client-vector initialization, and a run AAA satisfying the run declaration's conditions for these data, including 0<S≤N0<S\le N0<S≤N, K>0K>0K>0, and T>0T>0T>0. For any vector x⋆∈Rdx_\star\in\mathbb R^dx⋆​∈Rd and any real μ\muμ, put h=Kηlηgh=K\eta_l\eta_gh=Kηl​ηg​, a=(1−μh/2)−1a=(1-\mu h/2)^{-1}a=(1−μh/2)−1, and F(z)=N−1∑i=0N−1fi(z)F(z)=N^{-1}\sum_{i=0}^{N-1}f_i(z)F(z)=N−1∑i=0N−1​fi​(z). This definition is the real number

(∑r=0T−1ar+1)−1∑r=0T−1ar+1∫Ω(F(xr(ω))−F(x⋆)) dν(ω).\left(\sum_{r=0}^{T-1}a^{r+1}\right)^{-1}\sum_{r=0}^{T-1}a^{r+1}\int_\Omega\bigl(F(x_r(\omega))-F(x_\star)\bigr)\,d\nu(\omega).(r=0∑T−1​ar+1)−1r=0∑T−1​ar+1∫Ω​(F(xr​(ω))−F(x⋆​))dν(ω).

Here xrx_rxr​ comes from AAA, and each integral is the total real integral, assigned zero when its integrand is not integrable. The indices are 000 through T−1T-1T−1, so xTx_TxT​ is not included. Neither convexity, minimality of x⋆x_\starx⋆​, nonnegativity of μ\muμ, 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 1−μh/2=01-\mu h/2=01−μh/2=0. Negative weights and cancellation are allowed. When h=0h=0h=0, every weight is one and the expression is the arithmetic mean of the TTT expected gaps. For d=0d=0d=0 it is zero.

averageGradientSq. Fix natural d,N,S,K,Td,N,S,K,Td,N,S,K,T, a problem PPP with N>0N>0N>0 component functions fi:Rd→Rf_i:\mathbb R^d\to\mathbb Rfi​:Rd→R having gradients everywhere and a common positive gradient Lipschitz bound, its nonnegative noise parameter and initial vector, a standard Borel measurable space Ω\OmegaΩ with probability measure ν\nuν, arbitrary real step sizes ηl,ηg\eta_l,\eta_gηl​,ηg​, an absent or deterministic client-vector initialization, and a run AAA satisfying all the run declaration's conditions for these data, including 0<S≤N0<S\le N0<S≤N, K>0K>0K>0, and T>0T>0T>0. With F(z)=N−1∑i=0N−1fi(z)F(z)=N^{-1}\sum_{i=0}^{N-1}f_i(z)F(z)=N−1∑i=0N−1​fi​(z) and xrx_rxr​ the run's vector functions, this is T−1∑r=0T−1∫Ω∥∇F(xr(ω))∥2 dν(ω)T^{-1}\sum_{r=0}^{T-1}\int_\Omega\|\nabla F(x_r(\omega))\|^2\,d\nu(\omega)T−1∑r=0T−1​∫Ω​∥∇F(xr​(ω))∥2dν(ω). It averages the squared Euclidean norm of the gradient of the component mean, over indices 000 through T−1T-1T−1, excluding TTT. 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 TTT is positive because a run is supplied. For d=0d=0d=0 the expression is zero.

convexRHS. For natural d,Nd,Nd,N, a problem PPP supplying N>0N>0N>0 differentiable functions fi:Rd→Rf_i:\mathbb R^d\to\mathbb Rfi​:Rd→R with a common positive gradient Lipschitz bound, an initial vector x0x_0x0​, and a real noise parameter σ≥0\sigma\ge0σ≥0, arbitrary natural numbers S,K,TS,K,TS,K,T, arbitrary real numbers ηl,ηg,μ\eta_l,\eta_g,\muηl​,ηg​,μ, a deterministic vector family ci0∈Rdc_i^0\in\mathbb R^dci0​∈Rd, and an arbitrary vector x⋆∈Rdx_\star\in\mathbb R^dx⋆​∈Rd, put h=Kηlηgh=K\eta_l\eta_gh=Kηl​ηg​. This definition returns the real number

∥x0−x⋆∥2+9Nh2S(1N∑i=0N−1∥ci0−∇fi(x⋆)∥2)h∑r=0T−1((1−μh/2)−1)r+1+12hσ2KS(1+Sηg2).\frac{\displaystyle\|x_0-x_\star\|^2+\frac{9Nh^2}{S}\left(\frac1N\sum_{i=0}^{N-1}\|c_i^0-\nabla f_i(x_\star)\|^2\right)}{\displaystyle h\sum_{r=0}^{T-1}\left((1-\mu h/2)^{-1}\right)^{r+1}}+\frac{12h\sigma^2}{KS}\left(1+\frac{S}{\eta_g^2}\right).hr=0∑T−1​((1−μh/2)−1)r+1∥x0​−x⋆​∥2+S9Nh2​(N1​i=0∑N−1​∥ci0​−∇fi​(x⋆​)∥2)​+KS12hσ2​(1+ηg2​S​).

There is no run argument, no assumption that S,K,TS,K,TS,K,T are positive or that S≤NS\le NS≤N, no sign restriction on either step size or on μ\muμ, no convexity assumption, and no assertion that x⋆x_\starx⋆​ is a minimizer. The family ci0c_i^0ci0​ 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 h=0h=0h=0 makes the whole expression zero. When T=0T=0T=0, only the first quotient is forced to zero; the noise term remains as written. For d=0d=0d=0 the first quotient is zero but the noise term need not be zero, since the supplied σ\sigmaσ need not vanish.

nonconvexRHS. For natural d,Nd,Nd,N, a problem PPP supplying N>0N>0N>0 differentiable functions fi:Rd→Rf_i:\mathbb R^d\to\mathbb Rfi​:Rd→R with a common positive gradient Lipschitz bound β>0\beta>0β>0, a nonnegative real noise parameter σ\sigmaσ, and an initial vector x0x_0x0​, arbitrary natural numbers S,K,TS,K,TS,K,T, and arbitrary real numbers ηl,ηg,flower\eta_l,\eta_g,f_{\mathrm{lower}}ηl​,ηg​,flower​, put h=Kηlηgh=K\eta_l\eta_gh=Kηl​ηg​. This definition returns

14(N−1∑i=0N−1fi(x0)−flower)hT+70βhσ2KS(1+Sηg2).\frac{14\left(N^{-1}\sum_{i=0}^{N-1}f_i(x_0)-f_{\mathrm{lower}}\right)}{hT}+\frac{70\beta h\sigma^2}{KS}\left(1+\frac{S}{\eta_g^2}\right).hT14(N−1∑i=0N−1​fi​(x0​)−flower​)​+KS70βhσ2​(1+ηg2​S​).

No run, positive sample/step/round count, upper bound S≤NS\le NS≤N, or step-size sign condition is required. The real parameter flowerf_{\mathrm{lower}}flower​ 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 h=0h=0h=0 makes the entire expression zero, whereas T=0T=0T=0 forces only the first quotient to zero. The case d=0d=0d=0 is included, and the expression can still depend on the functions' values, flowerf_{\mathrm{lower}}flower​, and the noise parameter.

Human review
  • Endorsed by Shuze Chen · Sep 24, 2026

    Confirmed by the moderator at approval.

  • Endorsed by Minghui · Sep 24, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me