Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 5.3 — for α>3\alpha>3α>3 and ∑k∥gk∥<∞\sum k\|g_k\|<\infty∑k∥gk​∥<∞ the perturbed inertial forward-backward iterates converge weakly to a minimizer of Φ+Ψ\Phi+\PsiΦ+Ψ

Proved
InertialAVD.Algo.theorem_5_3

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

forward-backwardinertial-methodsp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1perturbationsweak-convergence

Let H\mathcal HH be a real Hilbert space, let Φ:H→R∪{+∞}\Phi:\mathcal H\to\mathbb R\cup\{+\infty\}Φ:H→R∪{+∞} be proper, lower semicontinuous and convex, and let Ψ:H→R\Psi:\mathcal H\to\mathbb RΨ:H→R be convex and continuously differentiable with LLL-Lipschitz continuous gradient; write Θ=Φ+Ψ\Theta=\Phi+\PsiΘ=Φ+Ψ. Let s>0s>0s>0 with sL<1sL<1sL<1, let (gk)k≥0(g_k)_{k\ge 0}(gk​)k≥0​ be a sequence of perturbations in H\mathcal HH, and let (xk)k≥0,(yk)k≥0(x_k)_{k\ge0},(y_k)_{k\ge0}(xk​)k≥0​,(yk​)k≥0​ be generated by the perturbed inertial forward-backward algorithm (55):

yk=xk+k−1k+α−1(xk−xk−1) (k≥1),xk+1=prox⁡sΦ(yk−s(∇Ψ(yk)−gk)) (k≥0),y_k = x_k + \frac{k-1}{k+\alpha-1}(x_k-x_{k-1})\ (k\ge 1),\qquad x_{k+1}=\operatorname{prox}_{s\Phi}\big(y_k-s(\nabla\Psi(y_k)-g_k)\big)\ (k\ge 0),yk​=xk​+k+α−1k−1​(xk​−xk−1​) (k≥1),xk+1​=proxsΦ​(yk​−s(∇Ψ(yk​)−gk​)) (k≥0),

with y0∈Hy_0\in\mathcal Hy0​∈H arbitrary.

Assume α>3\alpha>3α>3, ∑k∈Nk∥gk∥<+∞\sum_{k\in\mathbb N}k\|g_k\|<+\infty∑k∈N​k∥gk​∥<+∞, and S=argmin⁡Θ≠∅S=\operatorname{argmin}\Theta\neq\emptysetS=argminΘ=∅; let x∗∈Sx^*\in Sx∗∈S, so that Θ(x∗)=inf⁡Θ\Theta(x^*)=\inf\ThetaΘ(x∗)=infΘ. Then:

  1. Θ(xk)<+∞\Theta(x_k)<+\inftyΘ(xk​)<+∞ for k≥1k\ge1k≥1, and ∑kk(Θ(xk)−inf⁡Θ)<+∞\displaystyle\sum_{k}k\big(\Theta(x_k)-\inf\Theta\big)<+\inftyk∑​k(Θ(xk​)−infΘ)<+∞;
  2. ∑kk ∥xk+1−xk∥2<+∞\displaystyle\sum_k k\,\|x_{k+1}-x_k\|^2<+\inftyk∑​k∥xk+1​−xk​∥2<+∞;
  3. there is xˉ∈argmin⁡Θ\bar x\in\operatorname{argmin}\Thetaxˉ∈argminΘ such that
xk⇀xˉweakly in H.x_k\rightharpoonup\bar x\quad\text{weakly in }\mathcal H .xk​⇀xˉweakly in H.

The theorem says that Nesterov-type accelerated forward-backward iterates with the vanishing damping coefficient k−1k+α−1\frac{k-1}{k+\alpha-1}k+α−1k−1​, α>3\alpha>3α>3, converge (weakly) even when each step is computed with an error gkg_kgk​, provided ∑kk∥gk∥<∞\sum_k k\|g_k\|<\infty∑k​k∥gk​∥<∞.

Formalization Note. Φ\PhiΦ is EReal-valued with IsProperClosedConvex; prox⁡sΦ\operatorname{prox}_{s\Phi}proxsΦ​ is a map PPP with IsProx s Φ P; Θ\ThetaΘ is the published NesterovFB.Rates.theta Φ Ψ (whose argument names are swapped relative to this paper: its first argument is the nonsmooth part). LLL is a nonnegative real and "0<s<1/L0<s<1/L0<s<1/L" is written 0<s0<s0<s, sL<1sL<1sL<1, so L=0L=0L=0 is allowed. The run is IsPerturbedRun. Correction. Item iii) on the page reads "to some x∗∈argmin⁡Φx^*\in\operatorname{argmin}\Phix∗∈argminΦ"; the proof (Step 3, p. 22) applies Opial's lemma with S=argmin⁡(Φ+Ψ)S=\operatorname{argmin}(\Phi+\Psi)S=argmin(Φ+Ψ), so the limit is stated to minimize Φ+Ψ\Phi+\PsiΦ+Ψ. In item i) the k=0k=0k=0 term is 000 and, for k≥1k\ge1k≥1, Θ(xk)\Theta(x_k)Θ(xk​) is finite (asserted as part of the conclusion), so the terms are written with real numbers. Convergence is weak, not strong.

Preamble
import Mathlib
import Definitions.Def_ThreeOpSplitting_ConvexRates_Problem
import Definitions.Def_NesterovFB_Rates_Algorithm
import Definitions.Def_InertialAVD_Algo_PerturbedRun
import Definitions.Def_InertialFB_IFB_ConvexAnalysis

open Filter Topology NesterovFB.Rates
Formal statement
namespace InertialAVD.Algo

/-- Theorem 5.3, p. 21 (iii with `argmin(Φ + Ψ)`, as the proof uses). Under the standing
hypotheses, with `α > 3`, `0 < s`, `sL < 1`, `∑ k‖g_k‖ < ∞` and `x*` a minimizer of `Θ = Φ + Ψ`:
i) `Θ(x_k) < +∞` for `k ≥ 1` and `∑_k k(Θ(x_k) − Θ(x*)) < +∞`;
ii) `∑_k k‖x_{k+1} − x_k‖² < +∞`;
iii) `x_k` converges weakly to some minimizer of `Θ`. -/
theorem theorem_5_3 {H : Type*} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H]
    (Φ : H → EReal) (Ψ : H → ℝ) (L : NNReal) (s α : ℝ) (P : H → H) (g : ℕ → H) (x y : ℕ → H)
    (hΦ : ThreeOpSplitting.ConvexRates.IsProperClosedConvex Φ)
    (hΨc : ConvexOn ℝ Set.univ Ψ) (hΨd : ContDiff ℝ 1 Ψ)
    (hL : LipschitzWith L (gradient Ψ))
    (hs : 0 < s) (hsL : s * (L : ℝ) < 1)
    (hP : ThreeOpSplitting.ConvexRates.IsProx s Φ P)
    (hrun : IsPerturbedRun Ψ P α s g x y)
    (hα : 3 < α)
    (hg : Summable (fun k : ℕ => (k : ℝ) * ‖g k‖))
    (xstar : H) (hxstar : ∀ v : H, theta Φ Ψ xstar ≤ theta Φ Ψ v) :
    ((∀ k : ℕ, 1 ≤ k → theta Φ Ψ (x k) ≠ ⊤) ∧
      Summable (fun k : ℕ =>
        (k : ℝ) * ((theta Φ Ψ (x k)).toReal - (theta Φ Ψ xstar).toReal))) ∧
    Summable (fun k : ℕ => (k : ℝ) * ‖x (k + 1) - x k‖ ^ 2) ∧
    ∃ xbar : H, (∀ v : H, theta Φ Ψ xbar ≤ theta Φ Ψ v) ∧ InertialFB.IFB.WeakTendsto x xbar := by sorry

end InertialAVD.Algo
Source
Attouch, Chbani, Peypouquet, Redont, Fast convergence of inertial dynamics and algorithms with asymptotic vanishing damping, Optimization Online preprint 5179 (Oct. 2015), p. 21, Theorem 5.3 (iii with argmin(Φ + Ψ), as used in the proof on p. 22)
Human review
  • Endorsed by Shuze Chen · Oct 8, 2026

    Confirmed by the moderator at approval.

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