Proof of Theorem 8.1, eq. (25) — per-step bound for a constant step η ≤ 1/L (corrected: unbiased aggregate)
ProvedVHmGA.Convergence.eq_25Throughout, 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 .
Assume moreover that the step is constant, for all , with . Then for every , , and are integrable and
This is eq. (25) of the proof of Theorem 8.1: for the coefficient in (24) is at least . Summing it over gives the telescoped bound (26).
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
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_25 {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 α))
(t : ℕ) (ht : 1 ≤ t) :
Integrable (fun ω => F (w t ω)) μ ∧
Integrable (fun ω => F (w (t + 1) ω)) μ ∧
Integrable (fun ω => ‖g (w t ω)‖ ^ 2) μ ∧
η / 2 * ∫ ω, ‖g (w t ω)‖ ^ 2 ∂μ ≤ ∫ ω, F (w t ω) ∂μ - ∫ ω, F (w (t + 1) ω) ∂μ
+ L * η ^ 2 / 2 * sigmaTotalSq σ σDP σa α := by sorry
end VHmGA.Convergence
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.