Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Convex FedAvg model and stochastic oracle

Definition
FedAvg_Model

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

convex-optimizationfederated-learningprobability

This 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 M≥1M\ge1M≥1 clients with convex differentiable LLL-smooth functions Fi:Rd→RF_i:\mathbb R^d\to\mathbb RFi​:Rd→R, L>0L>0L>0, and F=M−1∑iFiF=M^{-1}\sum_iF_iF=M−1∑i​Fi​. Let x⋆x^\starx⋆ minimize FFF, let x0x_0x0​ be deterministic, and let D=∥x0−x⋆∥D=\|x_0-x^\star\|D=∥x0​−x⋆∥. The finite-dimensional space permits d=0d=0d=0. On a standard Borel probability space (Ω,A,P)(\Omega,\mathcal A,\mathbb P)(Ω,A,P), Ftτ+k\mathcal F_{t\tau+k}Ftτ+k​ contains the full history before step (t,k)(t,k)(t,k). All MMM clients participate and use uniform weights. Starting from x0x_0x0​, xit,k+1=xit,k−ηgit,kx_i^{t,k+1}=x_i^{t,k}-\eta g_i^{t,k}xit,k+1​=xit,k​−ηgit,k​; 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 ∇Fi(xit,k)\nabla F_i(x_i^{t,k})∇Fi​(xit,k​), and their squared errors have expectations at most σ2\sigma^2σ2, with σ≥0\sigma\ge0σ≥0. The uniform heterogeneity condition is ∥∇Fi(x)−∇F(x)∥≤ζ\|\nabla F_i(x)-\nabla F(x)\|\le\zeta∥∇Fi​(x)−∇F(x)∥≤ζ for every i,xi,xi,x, with ζ≥0\zeta\ge0ζ≥0. Write xˉt,k=M−1∑ixit,k\bar x^{t,k}=M^{-1}\sum_i x_i^{t,k}xˉt,k=M−1∑i​xit,k​, At=τ−1∑k=1τ(F(xˉt,k)−F(x⋆))A_t=\tau^{-1}\sum_{k=1}^{\tau}(F(\bar x^{t,k})-F(x^\star))At​=τ−1∑k=1τ​(F(xˉt,k)−F(x⋆)), and A=T−1∑t=0T−1AtA=T^{-1}\sum_{t=0}^{T-1}A_tA=T−1∑t=0T−1​At​. 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.

Definition code
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
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, equations (15)–(17); Section 6.1.1, PDF p. 40, equations (11)–(14); Appendix D.1, PDF p. 87, equation (27).
Read-back

What the Lean code literally says, in plain math · gpt-6

ModelSpace. For every natural number ddd, the model space is Ed=R{0,…,d−1}E_d=\mathbb R^{\{0,\ldots,d-1\}}Ed​=R{0,…,d−1} equipped with the Euclidean inner product and norm ∥x∥=(∑a=0d−1xa2)1/2\|x\|=(\sum_{a=0}^{d-1}x_a^2)^{1/2}∥x∥=(∑a=0d−1​xa2​)1/2. The case d=0d=0d=0 is included and gives the vector space containing only its zero vector.

objective. For natural numbers d,Md,Md,M, a family fi:Ed→Rf_i:E_d\to\mathbb Rfi​:Ed​→R indexed by i∈{0,…,M−1}i\in\{0,\ldots,M-1\}i∈{0,…,M−1}, and x∈Edx\in E_dx∈Ed​, define F(x)=M−1∑i=0M−1fi(x)F(x)=M^{-1}\sum_{i=0}^{M-1}f_i(x)F(x)=M−1∑i=0M−1​fi​(x). This definition itself imposes no positivity, regularity, or convexity assumptions. Real inversion is totalized with 0−1=00^{-1}=00−1=0, so when M=0M=0M=0 the empty sum and hence F(x)F(x)F(x) are zero.

Problem. For natural numbers d,Md,Md,M, a problem is data consisting of M>0M>0M>0, functions fi:Ed→Rf_i:E_d\to\mathbb Rfi​:Ed​→R for 0≤i<M0\le i<M0≤i<M, parameters L,σ,ζ∈RL,\sigma,\zeta\in\mathbb RL,σ,ζ∈R, and points x0,x⋆∈Edx_0,x_\star\in E_dx0​,x⋆​∈Ed​, together with the following conditions: L>0L>0L>0, σ≥0\sigma\ge0σ≥0, ζ≥0\zeta\ge0ζ≥0; for every i,xi,xi,x, fif_ifi​ has gradient ∇fi(x)\nabla f_i(x)∇fi​(x) at xxx; every fif_ifi​ is convex on the whole space; for every i,x,yi,x,yi,x,y, ∥∇fi(x)−∇fi(y)∥≤L∥x−y∥\|\nabla f_i(x)-\nabla f_i(y)\|\le L\|x-y\|∥∇fi​(x)−∇fi​(y)∥≤L∥x−y∥; for every i,xi,xi,x, ∥∇fi(x)−∇F(x)∥≤ζ\|\nabla f_i(x)-\nabla F(x)\|\le\zeta∥∇fi​(x)−∇F(x)∥≤ζ, where F(x)=M−1∑ifi(x)F(x)=M^{-1}\sum_i f_i(x)F(x)=M−1∑i​fi​(x); and for every xxx, F(x⋆)≤F(x)F(x_\star)\le F(x)F(x⋆​)≤F(x). No uniqueness of x⋆x_\starx⋆​, clientwise minimization at x⋆x_\starx⋆​, strict positivity of σ\sigmaσ or ζ\zetaζ, or positive dimension is required. No such problem exists when M=0M=0M=0.

Run. Given natural numbers d,Md,Md,M, a problem as specified above, a standard Borel measurable space Ω\OmegaΩ, a probability measure μ\muμ on it, arbitrary natural numbers τ,T\tau,Tτ,T, and an arbitrary real η\etaη, the run structure is precisely the following data and conditions. For the specified τ,T,η\tau,T,\etaτ,T,η, a run consists of an increasing filtration (Hs)s∈N(\mathcal H_s)_{s\in\mathbb N}(Hs​)s∈N​ of sub-σ\sigmaσ-algebras of the ambient measurable space and functions xt,k,i,gt,k,i:Ω→Ex_{t,k,i},g_{t,k,i}:\Omega\to Ext,k,i​,gt,k,i​:Ω→E defined for every t,k∈Nt,k\in\mathbb Nt,k∈N and client iii. For every t<Tt<Tt<T, k≤τk\le\tauk≤τ, and iii, xt,k,ix_{t,k,i}xt,k,i​ is strongly Htτ+k\mathcal H_{t\tau+k}Htτ+k​-measurable and square-integrable against μ\muμ. For every t<Tt<Tt<T, k<τk<\tauk<τ, and iii, gt,k,ig_{t,k,i}gt,k,i​ is strongly Htτ+k+1\mathcal H_{t\tau+k+1}Htτ+k+1​-measurable and square-integrable, and the following hold μ\muμ-almost everywhere: Eμ[gt,k,i∣Htτ+k]=∇fi(xt,k,i)\mathbb E_\mu[g_{t,k,i}\mid\mathcal H_{t\tau+k}]=\nabla f_i(x_{t,k,i})Eμ​[gt,k,i​∣Htτ+k​]=∇fi​(xt,k,i​), Eμ[∥gt,k,i−∇fi(xt,k,i)∥2∣Htτ+k]≤σ2\mathbb E_\mu[\|g_{t,k,i}-\nabla f_i(x_{t,k,i})\|^2\mid\mathcal H_{t\tau+k}]\le\sigma^2Eμ​[∥gt,k,i​−∇fi​(xt,k,i​)∥2∣Htτ+k​]≤σ2, and xt,k+1,i=xt,k,i−ηgt,k,ix_{t,k+1,i}=x_{t,k,i}-\eta g_{t,k,i}xt,k+1,i​=xt,k,i​−ηgt,k,i​. For each such t,kt,kt,k, the whole family (gt,k,i)i=0M−1(g_{t,k,i})_{i=0}^{M-1}(gt,k,i​)i=0M−1​ is mutually conditionally independent given Htτ+k\mathcal H_{t\tau+k}Htτ+k​; explicitly, conditional probabilities of intersections of finitely many events {gt,k,i∈Ai}\{g_{t,k,i}\in A_i\}{gt,k,i​∈Ai​} with distinct clients and Borel sets Ai⊆EA_i\subseteq EAi​⊆E equal the products of their conditional probabilities almost everywhere. The initialization x0,0,i(ω)=x0x_{0,0,i}(\omega)=x_0x0,0,i​(ω)=x0​ holds for every client and every ω\omegaω, with no exceptional null set. For each ttt with t+1<Tt+1<Tt+1<T and each iii, synchronization satisfies xt+1,0,i=M−1∑jxt,τ,jx_{t+1,0,i}=M^{-1}\sum_jx_{t,\tau,j}xt+1,0,i​=M−1∑j​xt,τ,j​ almost everywhere. Define xˉt,k=M−1∑ixt,k,i\bar x_{t,k}=M^{-1}\sum_i x_{t,k,i}xˉt,k​=M−1∑i​xt,k,i​. There is no positivity condition on τ,T,η\tau,T,\etaτ,T,η in this structure. If T=0T=0T=0, all requirements guarded by t<Tt<Tt<T or t+1<Tt+1<Tt+1<T are vacuous, but initialization still applies. If τ=0\tau=0τ=0, there are no stochastic-gradient or local-update requirements, while the iterate conditions at k=0k=0k=0 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 t,kt,kt,k and outcome ω∈Ω\omega\in\Omegaω∈Ω, define its averaged iterate by xˉt,k(ω)=M−1∑i=0M−1xt,k,i(ω)\bar x_{t,k}(\omega)=M^{-1}\sum_{i=0}^{M-1}x_{t,k,i}(\omega)xˉt,k​(ω)=M−1∑i=0M−1​xt,k,i​(ω). This average uses every client, has deterministic weight M−1M^{-1}M−1, and is defined even outside t<Tt<Tt<T or k≤τk\le\tauk≤τ; the problem data ensure M>0M>0M>0.

roundLoss. For any such problem and run, any t∈Nt\in\mathbb Nt∈N, and ω∈Ω\omega\in\Omegaω∈Ω, define ℓt(ω)=τ−1∑k=0τ−1[M−1∑ifi(M−1∑jxt,k+1,j(ω))−M−1∑ifi(x⋆)]\ell_t(\omega)=\tau^{-1}\sum_{k=0}^{\tau-1}\bigl[M^{-1}\sum_i f_i(M^{-1}\sum_jx_{t,k+1,j}(\omega))-M^{-1}\sum_i f_i(x_\star)\bigr]ℓt​(ω)=τ−1∑k=0τ−1​[M−1∑i​fi​(M−1∑j​xt,k+1,j​(ω))−M−1∑i​fi​(x⋆​)]. Thus it averages the objective excesses at the client-averaged iterates with inner indices 1,…,τ1,\ldots,\tau1,…,τ, including τ\tauτ and excluding 000. It is defined for arbitrary ttt, and is zero if τ=0\tau=0τ=0 by the empty-sum and zero-inverse conventions.

avgLoss. For any such problem and run and ω∈Ω\omega\in\Omegaω∈Ω, define ℓ(ω)=T−1∑t=0T−1τ−1∑k=0τ−1[M−1∑ifi(M−1∑jxt,k+1,j(ω))−M−1∑ifi(x⋆)]\ell(\omega)=T^{-1}\sum_{t=0}^{T-1}\tau^{-1}\sum_{k=0}^{\tau-1}\bigl[M^{-1}\sum_i f_i(M^{-1}\sum_jx_{t,k+1,j}(\omega))-M^{-1}\sum_i f_i(x_\star)\bigr]ℓ(ω)=T−1∑t=0T−1​τ−1∑k=0τ−1​[M−1∑i​fi​(M−1∑j​xt,k+1,j​(ω))−M−1∑i​fi​(x⋆​)]. This is the average of objective values, evaluated at the individual averaged iterates specified in the formula. It is zero if T=0T=0T=0 or τ=0\tau=0τ=0.

distance. For any problem with d,M∈Nd,M\in\mathbb Nd,M∈N, define D=∥x0−x⋆∥D=\|x_0-x_\star\|D=∥x0​−x⋆​∥. It is nonnegative; it is zero whenever the two designated points coincide and always zero when d=0d=0d=0. No probability space or run is an argument of this definition.

shadowDistanceSq. For any such problem and run, t,k∈Nt,k\in\mathbb Nt,k∈N, and ω∈Ω\omega\in\Omegaω∈Ω, define At,k(ω)=∥M−1∑ixt,k,i(ω)−x⋆∥2A_{t,k}(\omega)=\|M^{-1}\sum_i x_{t,k,i}(\omega)-x_\star\|^2At,k​(ω)=∥M−1∑i​xt,k,i​(ω)−x⋆​∥2. The definition is valid for all indices, including those outside the run's constrained ranges.

clientDriftSq. For any such problem and run, t,k∈Nt,k\in\mathbb Nt,k∈N, client i∈{0,…,M−1}i\in\{0,\ldots,M-1\}i∈{0,…,M−1}, and ω∈Ω\omega\in\Omegaω∈Ω, define Bt,k,i(ω)=∥xt,k,i(ω)−M−1∑jxt,k,j(ω)∥2B_{t,k,i}(\omega)=\|x_{t,k,i}(\omega)-M^{-1}\sum_j x_{t,k,j}(\omega)\|^2Bt,k,i​(ω)=∥xt,k,i​(ω)−M−1∑j​xt,k,j​(ω)∥2. This is a separate quantity for every client and every natural-number pair of indices.

progressTerm. For any such problem and run, t∈Nt\in\mathbb Nt∈N, and ω∈Ω\omega\in\Omegaω∈Ω, define Qt(ω)=(∥M−1∑ixt,0,i(ω)−x⋆∥2−Eμ[∥M−1∑ixt,τ,i−x⋆∥2∣Htτ](ω))/(2ητ)Q_t(\omega)=\bigl(\|M^{-1}\sum_i x_{t,0,i}(\omega)-x_\star\|^2-\mathbb E_\mu[\|M^{-1}\sum_i x_{t,\tau,i}-x_\star\|^2\mid\mathcal H_{t\tau}](\omega)\bigr)/(2\eta\tau)Qt​(ω)=(∥M−1∑i​xt,0,i​(ω)−x⋆​∥2−Eμ​[∥M−1∑i​xt,τ,i​−x⋆​∥2∣Htτ​](ω))/(2ητ). Here H\mathcal HH is the run's filtration and conditional expectation is the library's selected function version, defined to be zero for nonintegrable inputs. No restriction t<Tt<Tt<T occurs in this definition. Real division by zero gives zero, so this whole quantity is zero if η=0\eta=0η=0 or τ=0\tau=0τ=0.

deviationTerm. For any such problem and run, t∈Nt\in\mathbb Nt∈N, and ω∈Ω\omega\in\Omegaω∈Ω, define Vt(ω)=ησ2/M+[L/(Mτ)]∑i=0M−1∑k=0τ−1Eμ[∥xt,k,i−M−1∑jxt,k,j∥2∣Htτ](ω)V_t(\omega)=\eta\sigma^2/M+[L/(M\tau)]\sum_{i=0}^{M-1}\sum_{k=0}^{\tau-1}\mathbb E_\mu[\|x_{t,k,i}-M^{-1}\sum_jx_{t,k,j}\|^2\mid\mathcal H_{t\tau}](\omega)Vt​(ω)=ησ2/M+[L/(Mτ)]∑i=0M−1​∑k=0τ−1​Eμ​[∥xt,k,i​−M−1∑j​xt,k,j​∥2∣Htτ​](ω). Every conditional expectation is taken given the beginning-of-round σ\sigmaσ-algebra, and each uses the library's selected version and nonintegrable-input zero convention. The inner indices are 0,…,τ−10,\ldots,\tau-10,…,τ−1. If τ=0\tau=0τ=0, the double-sum contribution is zero and the expression is ησ2/M\eta\sigma^2/Mησ2/M.

progressRHS. For any such problem and run, t∈Nt\in\mathbb Nt∈N, and ω∈Ω\omega\in\Omegaω∈Ω, define Ht(ω)=(∥M−1∑ixt,0,i(ω)−x⋆∥2−Eμ[∥M−1∑ixt,τ,i−x⋆∥2∣Htτ](ω))/(2ητ)+ησ2/M+[L/(Mτ)]∑i∑k=0τ−1Eμ[∥xt,k,i−M−1∑jxt,k,j∥2∣Htτ](ω)H_t(\omega)=\bigl(\|M^{-1}\sum_i x_{t,0,i}(\omega)-x_\star\|^2-\mathbb E_\mu[\|M^{-1}\sum_i x_{t,\tau,i}-x_\star\|^2\mid\mathcal H_{t\tau}](\omega)\bigr)/(2\eta\tau)+\eta\sigma^2/M+[L/(M\tau)]\sum_i\sum_{k=0}^{\tau-1}\mathbb E_\mu[\|x_{t,k,i}-M^{-1}\sum_jx_{t,k,j}\|^2\mid\mathcal H_{t\tau}](\omega)Ht​(ω)=(∥M−1∑i​xt,0,i​(ω)−x⋆​∥2−Eμ​[∥M−1∑i​xt,τ,i​−x⋆​∥2∣Htτ​](ω))/(2ητ)+ησ2/M+[L/(Mτ)]∑i​∑k=0τ−1​Eμ​[∥xt,k,i​−M−1∑j​xt,k,j​∥2∣Htτ​](ω). Division and conditional expectation have the same totalized conventions just stated; no positivity of η,τ\eta,\tauη,τ or bound on ttt is imposed by this definition.

driftRHS. For any problem, any natural number τ\tauτ, and any real η\etaη, define the scalar B=18τ2η2ζ2+4τη2σ2B=18\tau^2\eta^2\zeta^2+4\tau\eta^2\sigma^2B=18τ2η2ζ2+4τη2σ2. It uses the problem's nonnegative parameters ζ,σ\zeta,\sigmaζ,σ and does not depend on a run, a probability space, a round, or a client. It is zero when τ=0\tau=0τ=0 or η=0\eta=0η=0.

convergenceRHS. For any problem, natural numbers τ,T\tau,Tτ,T, and real η\etaη, define C=∥x0−x⋆∥2/(2ητT)+ησ2/M+4τη2Lσ2+18τ2η2Lζ2C=\|x_0-x_\star\|^2/(2\eta\tau T)+\eta\sigma^2/M+4\tau\eta^2L\sigma^2+18\tau^2\eta^2L\zeta^2C=∥x0​−x⋆​∥2/(2ητT)+ησ2/M+4τη2Lσ2+18τ2η2Lζ2. Natural numbers in this expression are cast to real numbers. This definition alone does not require positive τ,T,η\tau,T,\etaτ,T,η. In particular its first summand is zero, rather than infinite or undefined, whenever its denominator is zero; if η=0\eta=0η=0, the entire expression is zero.

optimizedStep. For any problem and natural numbers τ,T\tau,Tτ,T, put D=∥x0−x⋆∥D=\|x_0-x_\star\|D=∥x0​−x⋆​∥ and define η⋆=min⁡{1/(4L), M D/(τ T σ), D2/3/(τ2/3T1/3L1/3σ2/3), D2/3/(τT1/3L1/3ζ2/3)}\eta_\star=\min\{1/(4L),\,\sqrt M\,D/(\sqrt\tau\,\sqrt T\,\sigma),\,D^{2/3}/(\tau^{2/3}T^{1/3}L^{1/3}\sigma^{2/3}),\,D^{2/3}/(\tau T^{1/3}L^{1/3}\zeta^{2/3})\}η⋆​=min{1/(4L),M​D/(τ​T​σ),D2/3/(τ2/3T1/3L1/3σ2/3),D2/3/(τT1/3L1/3ζ2/3)}. 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 L,ML,ML,M are positive. The definition places no strict positivity requirement on D,σ,ζ,τ,TD,\sigma,\zeta,\tau,TD,σ,ζ,τ,T. All divisions by zero equal zero; consequently if any of D,σ,ζ,τ,TD,\sigma,\zeta,\tau,TD,σ,ζ,τ,T is zero, this minimum is zero.

optimizedRHS. For any problem and natural numbers τ,T\tau,Tτ,T, define C⋆=2L∥x0−x⋆∥2/(τT)+2σ∥x0−x⋆∥/MτT+5L1/3σ2/3∥x0−x⋆∥4/3/(τ1/3T2/3)+19L1/3ζ2/3∥x0−x⋆∥4/3/T2/3C_\star=2L\|x_0-x_\star\|^2/(\tau T)+2\sigma\|x_0-x_\star\|/\sqrt{M\tau T}+5L^{1/3}\sigma^{2/3}\|x_0-x_\star\|^{4/3}/(\tau^{1/3}T^{2/3})+19L^{1/3}\zeta^{2/3}\|x_0-x_\star\|^{4/3}/T^{2/3}C⋆​=2L∥x0​−x⋆​∥2/(τT)+2σ∥x0​−x⋆​∥/MτT​+5L1/3σ2/3∥x0​−x⋆​∥4/3/(τ1/3T2/3)+19L1/3ζ2/3∥x0​−x⋆​∥4/3/T2/3. Fractional powers are real powers of the displayed nonnegative bases. The formula is defined without requiring τ,T,D,σ,ζ\tau,T,D,\sigma,\zetaτ,T,D,σ,ζ to be positive; every zero denominator makes that summand zero. In particular if T=0T=0T=0 every summand is zero, whereas for τ=0\tau=0τ=0 only the final summand can remain nonzero.

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

  • Endorsed by Minghui · Sep 23, 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