Theorem 10, p. 16 — DIGing converges R-linearly at the explicit rate λ for every step size 0 < α < 1.5(1−δ)²/(μ̄J₁)
ProvedDIGing.Undir.theorem_10Consider problem (1), , where the satisfy Assumption 4 (each is -Lipschitz) and Assumption 5 (-strong convexity with , some ), and let be its optimal solution. Let the time-varying undirected graphs and mixing matrices satisfy Assumption 1 with integer , and let
Let and let be generated by DIGing (Algorithm 1) with step size . Define
Then , and converges to at the global R-linear rate : there is a constant with
This is the paper's main result for undirected networks: with a fixed step size, gradient tracking over time-varying graphs converges geometrically to the exact optimum, with a rate that is explicit in , , , and .
Formalization Note. The page prints the step-size interval closed at ; at that endpoint the second formula gives , which is no geometric rate, and the proof needs ((39), p. 17). The endpoint is therefore excluded. "Doubly stochastic" in Assumption 1 includes nonnegative entries (Setting file). is given as the least upper bound of . Optimality of is a hypothesis; its existence and uniqueness is a separate item. Lean's is Real.rpow with exponent , applied to a positive base.
import Mathlib import Definitions.Def_DIGing_Undir_Common import Definitions.Def_DIGing_Undir_Setting
namespace DIGing.Undir
theorem theorem_10 {n p : ℕ} (f : Fin n → EuclideanSpace ℝ (Fin p) → ℝ) (Lc mu : Fin n → ℝ)
(h4 : Assumption4 f Lc) (h5 : Assumption5 f mu)
(xstar : EuclideanSpace ℝ (Fin p)) (hopt : ∀ z, objective f xstar ≤ objective f z)
(E : ℕ → SimpleGraph (Fin n)) (W : ℕ → Matrix (Fin n) (Fin n) ℝ) (B : ℕ)
(h1 : Assumption1 E W B)
(δ : ℝ) (hδ : IsLUB {d | ∃ k, B - 1 ≤ k ∧ d = deltaK W B k} δ)
(α : ℝ) (hα : 0 < α) (hαmax : α < alphaMax (J1 Lc mu B) δ (mubar mu))
(x y : ℕ → Stack n p) (hrun : IsDIGingRun f W α x y) :
0 < rateLam (J1 Lc mu B) δ (mubar mu) α B ∧ rateLam (J1 Lc mu B) δ (mubar mu) α B < 1 ∧
∃ C : ℝ, 0 < C ∧ ∀ k : ℕ,
frob (x k - ones xstar) ≤ C * rateLam (J1 Lc mu B) δ (mubar mu) α B ^ k := by sorry
end DIGing.Undir
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.