Lemma 3, (17), p. 419 — ‖∇f(x̄) − h(x)‖ ≤ (L/√n)‖x − 1x̄‖
ProvedStochGradTrack.Const.lemma_3consensusdistributed-optimizationlipschitz-gradientp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let each be -Lipschitz. For every stacked with average , writing and ,
The page states this for the iterates ; it bounds how far the averaged local gradients are from the true gradient at the average, in terms of the consensus error.
Formalization Note. The page says "for all " about ; the claim holds for every stacked and is stated so. Only the Lipschitz half of Assumption 2 is used. is the Frobenius norm.
Preamble
import Mathlib import Definitions.Def_StochGradTrack_Const_Model
Formal statement
namespace StochGradTrack.Const
open MeasureTheory ProbabilityTheory Matrix
theorem lemma_3 {n p : ℕ} (gradf : Fin n → E p → E p) (L : ℝ)
(hL : ∀ i (x x' : E p), ‖gradf i x - gradf i x'‖ ≤ L * ‖x - x'‖) (x : Stack n p) :
‖gradAvg gradf (avg x) - hAvg gradf x‖ ≤ L / Real.sqrt n * Real.sqrt (consErr x) := by sorry
end StochGradTrack.Const
Source
Pu & Nedić, Math. Program. 187 (2021), Lemma 3 with (17), p. 419
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.