Lemma 5, p. 10 — first arrow q → z: ‖z‖^{λ,K}_F ≤ L(1 + 1/λ)‖q‖^{λ,K}_F
ProvedDIGing.Undir.lemma_5distributed-optimizationlipschitz-gradientp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1small-gain
Let each satisfy Assumption 4 with constants , and let . Let be any sequence of matrices, any point, , and for , . Then for every and every ,
This is the first arrow of the cycle to which the small gain theorem is applied: successive gradient differences are controlled by the distance to the optimum.
Formalization Note. The statement uses only the Lipschitz bound, so it is stated for an arbitrary sequence and an arbitrary point , without the DIGing recursion, Assumption 5 or optimality of (all dropped; the statement is stronger).
Preamble
import Mathlib import Definitions.Def_DIGing_Undir_Common import Definitions.Def_DIGing_Undir_Setting
Formal statement
namespace DIGing.Undir
theorem lemma_5 {n p : ℕ} (f : Fin n → EuclideanSpace ℝ (Fin p) → ℝ) (Lc : Fin n → ℝ)
(h4 : Assumption4 f Lc) (x : ℕ → Stack n p) (xstar : EuclideanSpace ℝ (Fin p)) :
∀ K : ℕ, ∀ lam : ℝ, 0 < lam → lam < 1 →
ergK lam K (fun k => frob (zSeq f x k)) ≤
Lmax Lc * (1 + 1 / lam) * ergK lam K (fun k => frob (x k - ones xstar)) := by sorry
end DIGing.Undir
Source
Nedić, Olshevsky & Shi, arXiv:1607.03218v3, Lemma 5, p. 10 (q and z defined in §3.2, p. 10)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.