Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 10, p. 16 — DIGing converges R-linearly at the explicit rate λ for every step size 0 < α < 1.5(1−δ)²/(μ̄J₁)

Proved
DIGing.Undir.theorem_10

by mikedeng1 · Oct 9, 2026 · Mathlib 0df444a (Lean v4.33.1)

distributed-optimizationgradient-trackinglinear-convergencep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1time-varying-graphs

Consider problem (1), min⁡x∈Rpf(x)=1n∑i=1nfi(x)\min_{x\in\mathbb R^p}f(x)=\frac1n\sum_{i=1}^nf_i(x)minx∈Rp​f(x)=n1​∑i=1n​fi​(x), where the fif_ifi​ satisfy Assumption 4 (each ∇fi\nabla f_i∇fi​ is LiL_iLi​-Lipschitz) and Assumption 5 (μi\mu_iμi​-strong convexity with μi≥0\mu_i\ge0μi​≥0, some μi>0\mu_i>0μi​>0), and let x∗x^*x∗ be its optimal solution. Let the time-varying undirected graphs E(k)E(k)E(k) and mixing matrices W(k)W(k)W(k) satisfy Assumption 1 with integer B≥1B\ge1B≥1, and let

δ=sup⁡k≥B−1σmax⁡{WB(k)−1n11⊤},J1=3κˉB2(1+4nκˉ).\delta=\sup_{k\ge B-1}\sigma_{\max}\Big\{W_B(k)-\tfrac1n\mathbf 1\mathbf 1^\top\Big\},\qquad J_1=3\bar\kappa B^2\big(1+4\sqrt n\sqrt{\bar\kappa}\big).δ=k≥B−1sup​σmax​{WB​(k)−n1​11⊤},J1​=3κˉB2(1+4n​κˉ​).

Let 0<α<1.5(1−δ)2/(μˉJ1)0<\alpha<1.5(1-\delta)^2/(\bar\mu J_1)0<α<1.5(1−δ)2/(μˉ​J1​) and let x(k)\mathbf x(k)x(k) be generated by DIGing (Algorithm 1) with step size α\alphaα. Define

λ={1−αμˉ1.52B,α≤1.5(J12+(1−δ2)J1−δJ1)2μˉJ1(J1+1)2,αμˉJ11.5+δB,otherwise.\lambda=\begin{cases}\sqrt[2B]{1-\dfrac{\alpha\bar\mu}{1.5}}, & \alpha\le\dfrac{1.5\big(\sqrt{J_1^2+(1-\delta^2)J_1}-\delta J_1\big)^2}{\bar\mu J_1(J_1+1)^2},\\[2ex] \sqrt[B]{\sqrt{\dfrac{\alpha\bar\mu J_1}{1.5}}+\delta}, & \text{otherwise.}\end{cases}λ=⎩⎨⎧​2B1−1.5αμˉ​​​,B1.5αμˉ​J1​​​+δ​,​α≤μˉ​J1​(J1​+1)21.5(J12​+(1−δ2)J1​​−δJ1​)2​,otherwise.​

Then 0<λ<10<\lambda<10<λ<1, and x(k)\mathbf x(k)x(k) converges to x∗=1(x∗)⊤\mathbf x^*=\mathbf 1(x^*)^\topx∗=1(x∗)⊤ at the global R-linear rate O(λk)O(\lambda^k)O(λk): there is a constant C>0C>0C>0 with

∥x(k)−1(x∗)⊤∥F≤Cλkfor all k=0,1,…\|\mathbf x(k)-\mathbf 1(x^*)^\top\|_F\le C\lambda^k\qquad\text{for all }k=0,1,\dots∥x(k)−1(x∗)⊤∥F​≤Cλkfor all k=0,1,…

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 BBB, nnn, δ\deltaδ, μˉ\bar\muμˉ​ and κˉ\bar\kappaκˉ.

Formalization Note. The page prints the step-size interval closed at 1.5(1−δ)2/(μˉJ1)1.5(1-\delta)^2/(\bar\mu J_1)1.5(1−δ)2/(μˉ​J1​); at that endpoint the second formula gives λ=1\lambda=1λ=1, which is no geometric rate, and the proof needs λB<1\lambda^B<1λB<1 ((39), p. 17). The endpoint is therefore excluded. "Doubly stochastic" in Assumption 1 includes nonnegative entries (Setting file). δ\deltaδ is given as the least upper bound of {δ(k):k≥B−1}\{\delta(k):k\ge B-1\}{δ(k):k≥B−1}. Optimality of x∗x^*x∗ is a hypothesis; its existence and uniqueness is a separate item. Lean's ⋅m\sqrt[m]{\cdot}m⋅​ is Real.rpow with exponent 1/m1/m1/m, applied to a positive base.

Preamble
import Mathlib
import Definitions.Def_DIGing_Undir_Common
import Definitions.Def_DIGing_Undir_Setting
Formal statement
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
Source
Nedić, Olshevsky & Shi, arXiv:1607.03218v3, Theorem 10, p. 16 (R-linear: footnote 1, p. 1)
Human review
  • Endorsed by Shuze Chen · Oct 9, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 9, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me