Theorem 5.3 — for and the perturbed inertial forward-backward iterates converge weakly to a minimizer of
ProvedInertialAVD.Algo.theorem_5_3Let be a real Hilbert space, let be proper, lower semicontinuous and convex, and let be convex and continuously differentiable with -Lipschitz continuous gradient; write . Let with , let be a sequence of perturbations in , and let be generated by the perturbed inertial forward-backward algorithm (55):
with arbitrary.
Assume , , and ; let , so that . Then:
- for , and ;
- ;
- there is such that
The theorem says that Nesterov-type accelerated forward-backward iterates with the vanishing damping coefficient , , converge (weakly) even when each step is computed with an error , provided .
Formalization Note. is EReal-valued with IsProperClosedConvex; is a map with IsProx s Φ P; is the published NesterovFB.Rates.theta Φ Ψ (whose argument names are swapped relative to this paper: its first argument is the nonsmooth part). is a nonnegative real and "" is written , , so is allowed. The run is IsPerturbedRun. Correction. Item iii) on the page reads "to some "; the proof (Step 3, p. 22) applies Opial's lemma with , so the limit is stated to minimize . In item i) the term is and, for , is finite (asserted as part of the conclusion), so the terms are written with real numbers. Convergence is weak, not strong.
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
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.