Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 8.1 — 1T∑t=1TE∥∇F(wt)∥2≤2(F(w1)−F∗)ηT+Lησtotal2\frac1T\sum_{t=1}^T\mathbb E\|\nabla F(w_t)\|^2\le\frac{2(F(w_1)-F^*)}{\eta T}+L\eta\sigma^2_{\mathrm{total}}T1​∑t=1T​E∥∇F(wt​)∥2≤ηT2(F(w1​)−F∗)​+Lησtotal2​ (corrected: unbiased aggregate)

Proved
VHmGA.Convergence.theorem_8_1

by mikedeng1 · Nov 11, 2026 · Mathlib 0df444a (Lean v4.33.1)

conditional-expectationnonconvex-optimizationp2o-batch-stoc27ap2o-correctedp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1sgd

This is the convergence theorem of the VHmGA framework (Theorem 8.1, with the explicit constant of eq. (28) from its proof).

Throughout, F:Rd→RF:\mathbb R^d\to\mathbb RF:Rd→R is LLL-smooth with gradient map g=∇Fg=\nabla Fg=∇F and L>0L>0L>0, i.e. ∥∇F(w)−∇F(w′)∥≤L∥w−w′∥\|\nabla F(w)-\nabla F(w')\|\le L\|w-w'\|∥∇F(w)−∇F(w′)∥≤L∥w−w′∥ for all w,w′w,w'w,w′. On a probability space (Ω,F,P)(\Omega,\mathcal F,\mathbb P)(Ω,F,P) the iterates follow the update (18), wt+1=wt−ηtg~tw_{t+1}=w_t-\eta_t\tilde g_twt+1​=wt​−ηt​g~​t​, from a fixed starting point w1w_1w1​, with step sizes ηt>0\eta_t>0ηt​>0. For each t≥1t\ge1t≥1 a σ\sigmaσ-algebra Gt⊆F\mathcal G_t\subseteq\mathcal FGt​⊆F is fixed with respect to which wtw_twt​ is measurable (the paper's "conditioning on wtw_twt​"; Gt=σ(wt)\mathcal G_t=\sigma(w_t)Gt​=σ(wt​) or the history up to ttt are both allowed). The aggregate g~t\tilde g_tg~​t​ is integrable and conditionally unbiased, E[g~t∣Gt]=∇F(wt)\mathbb E[\tilde g_t\mid\mathcal G_t]=\nabla F(w_t)E[g~​t​∣Gt​]=∇F(wt​), and its conditional mean-square error obeys (19):

E[∥g~t−∇F(wt)∥2 ∣ Gt]≤σtotal2=σ2+σDP2+α1−ασa2,0≤α<1.\mathbb E\big[\|\tilde g_t-\nabla F(w_t)\|^2\,\big|\,\mathcal G_t\big]\le\sigma^2_{\mathrm{total}}=\sigma^2+\sigma^2_{\mathrm{DP}}+\frac{\alpha}{1-\alpha}\sigma_a^2,\qquad 0\le\alpha<1 .E[∥g~​t​−∇F(wt​)∥2​Gt​]≤σtotal2​=σ2+σDP2​+1−αα​σa2​,0≤α<1.

Below, E[ ⋅∣wt]\mathbb E[\,\cdot\mid w_t]E[⋅∣wt​] means E[ ⋅∣Gt]\mathbb E[\,\cdot\mid\mathcal G_t]E[⋅∣Gt​].

Assume moreover that the step is constant, ηt=η\eta_t=\etaηt​=η with 0<η≤1/L0<\eta\le1/L0<η≤1/L, and let F∗F^*F∗ be a lower bound of FFF: F∗≤F(w)F^*\le F(w)F∗≤F(w) for all www. Then for every number of iterations T≥1T\ge1T≥1, ∥∇F(wt)∥2\|\nabla F(w_t)\|^2∥∇F(wt​)∥2 is integrable for t=1,…,Tt=1,\dots,Tt=1,…,T and

1T∑t=1TE[∥∇F(wt)∥2]≤2 (F(w1)−F∗)ηT+Lη σtotal2.\frac1T\sum_{t=1}^{T}\mathbb E\big[\|\nabla F(w_t)\|^2\big]\le\frac{2\,(F(w_1)-F^*)}{\eta T}+L\eta\,\sigma^2_{\mathrm{total}} .T1​t=1∑T​E[∥∇F(wt​)∥2]≤ηT2(F(w1​)−F∗)​+Lησtotal2​.

The average squared gradient norm along the trajectory thus decays like 1/T1/T1/T up to a noise floor Lησtotal2L\eta\sigma^2_{\mathrm{total}}Lησtotal2​, in which the verification layer, the privacy noise and the surviving adversarial contributions enter only through σtotal2\sigma^2_{\mathrm{total}}σtotal2​. For nonconvex FFF a small average gradient norm is the standard notion of approximate stationarity.

Differences from the source:

  • correction: the only hypotheses on the aggregate are L-smoothness of F and the conditional MSE bound (19); 'unbiased' is said of honest workers' gradients only → the run also assumes E[g̃_t | G_t] = ∇F(w_t) a.s.; reason: under (19) alone the statement is false: d = 1, F(w) = w²/2 (L = 1, F* = 0), g̃_t ≡ w_t + s with s > 0, w_1 = −s gives w_t ≡ −s, conditional MSE s² = σ²_total (σ = s, σ_DP = σ_a = α = 0), and violates the inequality; the paper's proof uses unbiasedness to remove the cross term in (21) and for the equality in (23)
  • generalization: conditioning on w_t ('accounts for the parameter history up to iteration t') → conditioning on any σ-algebra G_t ⊆ F for which w_t is G_t-measurable; reason: σ(w_t) and the history σ-algebra are both admissible G_t, so the paper's statement is an instance
  • generalization: corrupted fraction α < 1/3 → 0 ≤ α < 1; reason: the bound only needs α/(1−α) to be defined; α ∈ [0, 1/3) is an instance
  • generalization: F is the global risk (1), a finite sum of local risks → F is any L-smooth function ℝ^d → ℝ; reason: only L-smoothness is used; the finite sum (1) with an L-smooth total is an instance
  • encoding: expectations of F(w_t), ‖∇F(w_t)‖² and ‖g̃_t‖² are used without comment → their integrability is asserted as additional conclusions; reason: Lean's integral and conditional expectation of a non-integrable function are 0; asserting integrability makes the inequality about the genuine expectations and does not change any instance
  • encoding: σ², σ²_DP, σ²_a are variances (nonnegative reals) → squares σ^2, σDP^2, σa^2 of real parameters σ, σDP, σa; reason: every nonnegative real is the square of a real, so the set of admissible values of σ²_total is the same
  • reading: η in (22) is not specified; §8.1 has a time-varying η_t > 0 and the text before the theorem mentions diminishing schedules such as η_t = 1/√t → constant step η_t = η with 0 < η ≤ 1/L; reason: the bound contains a single η and the proof fixes 'a sufficiently small constant learning rate η_t = η ≤ 1/L'; for unrestricted η it is false (F(w) = w²/2, g̃_t = ∇F(w_t), η = 3 gives w_t = (−2)^{t−1} w_1)
  • generalization: F* = inf_w F(w) → F* is any lower bound of F; reason: inf_w F(w) is a lower bound, so the paper's case is an instance
  • generalization: upper bound O((F(w_1) − F*)/(ηT) + Lησ²_total) → the explicit bound 2(F(w_1) − F*)/(ηT) + Lησ²_total; reason: this is the paper's own constant from (28); since F(w_1) − F* ≥ 0 and Lησ²_total ≥ 0 it implies (22) with O-constant 2
  • reading: (28) ends with '= O(1/√T)' → not stated; reason: it is a remark in the proof, not a clause of (22): for fixed η and σ_total > 0 the right side tends to Lησ²_total ≠ 0, so it holds only for a T-dependent step η ∝ 1/√T, which the theorem does not fix
Preamble
import Mathlib
import Definitions.Def_ConvexOptAlg_SmoothGD_Defs
import Definitions.Def_VHmGA_Convergence_Defs

set_option autoImplicit false
open MeasureTheory
Formal statement
namespace VHmGA.Convergence

theorem theorem_8_1 {d : ℕ} {Ω : Type*} [MeasurableSpace Ω] {μ : Measure Ω}
    {F : EuclideanSpace ℝ (Fin d) → ℝ}
    {g : EuclideanSpace ℝ (Fin d) → EuclideanSpace ℝ (Fin d)} {L η : ℝ}
    {σ σDP σa α : ℝ} {w1 : EuclideanSpace ℝ (Fin d)}
    {w gt : ℕ → Ω → EuclideanSpace ℝ (Fin d)} {m : ℕ → MeasurableSpace Ω}
    (hF : ConvexOptAlg.SmoothGD.IsBetaSmooth F g L) (hL : 0 < L)
    (hη : 0 < η) (hηL : η ≤ 1 / L) (hα0 : 0 ≤ α) (hα1 : α < 1)
    (hrun : IsVerifiedSGDRun μ g (fun _ => η) w1 w gt m (sigmaTotalSq σ σDP σa α))
    {Fstar : ℝ} (hFstar : ∀ x, Fstar ≤ F x) (T : ℕ) (hT : 1 ≤ T) :
    (∀ t ∈ Finset.Icc 1 T, Integrable (fun ω => ‖g (w t ω)‖ ^ 2) μ) ∧
    1 / (T : ℝ) * ∑ t ∈ Finset.Icc 1 T, ∫ ω, ‖g (w t ω)‖ ^ 2 ∂μ ≤
      2 * (F w1 - Fstar) / (η * T) + L * η * sigmaTotalSq σ σDP σa α := by sorry

end VHmGA.Convergence
Source
Jean Rosemond Dora, Ladislav Hluchý, STOC 2027 submission #955 (October 2026), Theorem 8.1, eq. (22), p. 6, with the explicit constant of eq. (28), proof of Theorem 8.1, p. 7
Human review
  • Endorsed by Shuze Chen · Nov 11, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Nov 11, 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