Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

(117), proof of Theorem 7.2, p. 31 — ℒ̂_k − ℒ_k ≤ −α_kℒ̂_k + (1 + α_k)(f(y_k) − f(x_{k+1})) + (α_k²/(2γ_k) − (1 + α_k)/(2L))‖G_f(y_k)‖²

Proved
NAGFlow.APGM.eq_117

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

accelerated-gradientlyapunov-functionp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1proximal-gradient

Let VVV be a real Hilbert space, f=h+gf=h+gf=h+g with h∈Sμ,L1,1h\in\mathcal S^{1,1}_{\mu,L}h∈Sμ,L1,1​ (0≤μ≤L<∞0\le\mu\le L<\infty0≤μ≤L<∞) and g:V→R∪{+∞}g:V\to\mathbb R\cup\{+\infty\}g:V→R∪{+∞} proper, closed and convex, and let x∗∈dom⁡gx^*\in\operatorname{dom}gx∗∈domg minimise fff. Let (xk,yk,vk,γk)(x_k,y_k,v_k,\gamma_k)(xk​,yk​,vk​,γk​) be a run of the semi-implicit scheme (115) with γ0>0\gamma_0>0γ0​>0 and arbitrary step sizes αk>0\alpha_k>0αk​>0, started at x0∈dom⁡gx_0\in\operatorname{dom}gx0​∈domg. With

Lk=f(xk)−f(x∗)+γk2∥vk−x∗∥2,L^k=f(yk)−f(x∗)+γk+12∥vk+1−x∗∥2(84),\mathcal L_k=f(x_k)-f(x^*)+\frac{\gamma_k}2\|v_k-x^*\|^2,\qquad \widehat{\mathcal L}_k=f(y_k)-f(x^*)+\frac{\gamma_{k+1}}2\|v_{k+1}-x^*\|^2\quad(84),Lk​=f(xk​)−f(x∗)+2γk​​∥vk​−x∗∥2,Lk​=f(yk​)−f(x∗)+2γk+1​​∥vk+1​−x∗∥2(84),

and Gf(yk)=L(yk−xk+1)\mathcal G_f(y_k)=L(y_k-x_{k+1})Gf​(yk​)=L(yk​−xk+1​), for every kkk

L^k−Lk≤−αkL^k+(1+αk)(f(yk)−f(xk+1))+αk22γk∥Gf(yk)∥2−1+αk2L∥Gf(yk)∥2.(117)\widehat{\mathcal L}_k-\mathcal L_k\le-\alpha_k\widehat{\mathcal L}_k+(1+\alpha_k)\big(f(y_k)-f(x_{k+1})\big)+\frac{\alpha_k^2}{2\gamma_k}\|\mathcal G_f(y_k)\|^2-\frac{1+\alpha_k}{2L}\|\mathcal G_f(y_k)\|^2.\qquad(117)Lk​−Lk​≤−αk​Lk​+(1+αk​)(f(yk​)−f(xk+1​))+2γk​αk2​​∥Gf​(yk​)∥2−2L1+αk​​∥Gf​(yk​)∥2.(117)

With the step size Lαk2=γk(1+αk)L\alpha_k^2=\gamma_k(1+\alpha_k)Lαk2​=γk​(1+αk​) the last two terms cancel, and the identity f(yk)−f(xk+1)=L^k−Lk+1f(y_k)-f(x_{k+1})=\widehat{\mathcal L}_k-\mathcal L_{k+1}f(yk​)−f(xk+1​)=Lk​−Lk+1​ turns (117) into the contraction (116).

Formalization Note. No step-size rule is assumed: (117) holds for every αk>0\alpha_k>0αk​>0. The point yky_kyk​ may lie outside dom⁡g\operatorname{dom}gdomg; there the page's f(yk)f(y_k)f(yk​) is +∞+\infty+∞. In the encoding f(yk)f(y_k)f(yk​) is a real number, and it enters both sides with total coefficient 111, so the inequality does not depend on the value ggg takes at yky_kyk​; no hypothesis yk∈dom⁡gy_k\in\operatorname{dom}gyk​∈domg is added. The hypothesis x0∈dom⁡gx_0\in\operatorname{dom}gx0​∈domg is added: without it the page's L0\mathcal L_0L0​ is +∞+\infty+∞ and the case k=0k=0k=0 is void (xk∈dom⁡gx_k\in\operatorname{dom}gxk​∈domg for k≥1k\ge1k≥1 follows from the prox step). x∗x^*x∗ minimises fff over dom⁡g\operatorname{dom}gdomg (argmin fff nonempty, p. 2).

Preamble
import Mathlib
import Definitions.Def_NAGFlow_APGM_Setting
Formal statement
namespace NAGFlow.APGM

/-- Inequality (117) (Luo & Chen, arXiv:1909.03145v4, proof of Theorem 7.2, p. 31). Let
`h ∈ S^{1,1}_{μ,L}` with `0 ≤ μ ≤ L < ∞`, `g : V → ℝ ∪ {+∞}` proper, closed and convex (encoded by
`(g, D)`), `f = h + g`, and `x* ∈ dom g` a minimiser of `f`. Let `(x, y, v)` be a run of the
semi-implicit scheme (115) with `γ₀ > 0` and any step sizes `α_k > 0`, started at `x₀ ∈ dom g`. With
`ℒ_k = f(x_k) − f(x*) + (γ_k/2)‖v_k − x*‖²`, `ℒ̂_k = f(y_k) − f(x*) + (γ_{k+1}/2)‖v_{k+1} − x*‖²` (84)
and `G_f(y_k) = L(y_k − x_{k+1})`, for every `k`
`ℒ̂_k − ℒ_k ≤ −α_kℒ̂_k + (1 + α_k)(f(y_k) − f(x_{k+1})) + (α_k²/(2γ_k))‖G_f(y_k)‖² − ((1 + α_k)/(2L))‖G_f(y_k)‖²`. -/
theorem eq_117 {V : Type*} [NormedAddCommGroup V] [InnerProductSpace ℝ V] [CompleteSpace V]
    (h : V → ℝ) (gradh : V → V) (μ L : ℝ) (hh : NAGFlow.PredCorr.IsS11 h gradh μ L)
    (g : V → ℝ) (D : Set V) (hg : IsProperClosedConvex g D)
    (xstar : V) (hxstar : xstar ∈ D) (hmin : ∀ z ∈ D, (h + g) xstar ≤ (h + g) z)
    (α γ : ℕ → ℝ) (x y v : ℕ → V) (hrun : IsSemiImplicitRun gradh g D μ L α γ x y v)
    (hx0 : x 0 ∈ D) (k : ℕ) :
    NAGFlow.PredCorr.lyapHat (h + g) xstar y v γ k - NAGFlow.PredCorr.lyap (h + g) xstar x v γ k ≤
      -α k * NAGFlow.PredCorr.lyapHat (h + g) xstar y v γ k + (1 + α k) * ((h + g) (y k) - (h + g) (x (k + 1)))
        + α k ^ 2 / (2 * γ k) * ‖gradMap (1 / L) (y k) (x (k + 1))‖ ^ 2
        - (1 + α k) / (2 * L) * ‖gradMap (1 / L) (y k) (x (k + 1))‖ ^ 2 := by sorry

end NAGFlow.APGM
Source
Luo & Chen, arXiv:1909.03145v4, proof of Theorem 7.2, (117), p. 31; (84), p. 20; (115), p. 30
Human review
  • Endorsed by Shuze Chen · Oct 10, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 10, 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