Proof of Theorem 8.1, eq. (23) — conditional second-moment decomposition (corrected: unbiased aggregate)
ProvedVHmGA.Convergence.eq_23Throughout, is -smooth with gradient map and , i.e. for all . On a probability space the iterates follow the update (18), , from a fixed starting point , with step sizes . For each a -algebra is fixed with respect to which is measurable (the paper's "conditioning on "; or the history up to are both allowed). The aggregate is integrable and conditionally unbiased, , and its conditional mean-square error obeys (19):
Below, means .
Then for every , is integrable and, almost surely,
This is the bias–variance split of the second moment of the aggregate, eq. (23) in the proof of Theorem 8.1. It converts the second-moment term of (21) into the gradient norm plus the noise level (19).
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: the middle term is printed as E[‖g̃_t − ∇F(w_t)‖²] without '| w_t' → the middle term is the conditional expectation E[‖g̃_t − ∇F(w_t)‖² | G_t]; reason: the left side is conditional, and the next step '≤ σ²_total' invokes the conditional bound (19); the unconditional reading would make the equality between a random variable and a number
import Mathlib import Definitions.Def_ConvexOptAlg_SmoothGD_Defs import Definitions.Def_VHmGA_Convergence_Defs set_option autoImplicit false open MeasureTheory
namespace VHmGA.Convergence
theorem eq_23 {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 : 0 ≤ α) (hα1 : α < 1)
(hrun : IsVerifiedSGDRun μ g η w1 w gt m (sigmaTotalSq σ σDP σa α))
(t : ℕ) (ht : 1 ≤ t) :
Integrable (fun ω => ‖gt t ω‖ ^ 2) μ ∧
μ[fun ω => ‖gt t ω‖ ^ 2 | m t] =ᵐ[μ] (fun ω =>
‖g (w t ω)‖ ^ 2 + μ[fun ω' => ‖gt t ω' - g (w t ω')‖ ^ 2 | m t] ω) ∧
μ[fun ω => ‖gt t ω‖ ^ 2 | m t] ≤ᵐ[μ] (fun ω =>
‖g (w t ω)‖ ^ 2 + sigmaTotalSq σ σDP σa α) := by sorry
end VHmGA.Convergence
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.