§7.2.2, p. 30 — every run of Algorithm 2 (Semi-APGM) is a run of the semi-implicit scheme (115)
ProvedNAGFlow.APGM.algorithm_2_eq_115accelerated-gradientode-discretizationp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1proximal-gradient
Let be a real Hilbert space, , , a map and with domain . Let be generated by Algorithm 2 (Semi-APGM): and, for every , with ,
Then satisfies the semi-implicit scheme (115): for every ,
where .
This is the statement that Algorithm 2 "summarizes" (115): it lets every estimate proved for (115) be applied to the algorithm. The -update matches because of the step-size relation .
Formalization Note. Only enters the scheme, so no class assumption on or is needed. The prox is the predicate of the definitions file (a minimiser over ).
Preamble
import Mathlib import Definitions.Def_NAGFlow_APGM_Setting
Formal statement
namespace NAGFlow.APGM
/-- Algorithm 2 is the semi-implicit scheme (115) (Luo & Chen, arXiv:1909.03145v4, §7.2.2, p. 30).
Let `0 ≤ μ` and `0 < L`. Every run `(α, γ, x, y, w, v)` of Algorithm 2 (Semi-APGM, with `γ₀ > 0`,
`α_k > 0`, `Lα_k² = γ_k(1 + α_k)`, `η = 1/L`) satisfies (115): for every `k`,
`(y_k − x_k)/α_k = v_k − y_k`, `x_{k+1} = S_f(y_k)`,
`(v_{k+1} − v_k)/α_k = (μ/γ_k)(y_k − v_{k+1}) − (1/γ_k)G_f(y_k)` with `G_f(y_k) = L(y_k − x_{k+1})`, and
`(γ_{k+1} − γ_k)/α_k = μ − γ_{k+1}`. -/
theorem algorithm_2_eq_115 {V : Type*} [NormedAddCommGroup V] [InnerProductSpace ℝ V]
(gradh : V → V) (g : V → ℝ) (D : Set V) (μ L : ℝ) (hμ : 0 ≤ μ) (hL : 0 < L)
(α γ : ℕ → ℝ) (x y w v : ℕ → V) (hrun : IsAPGMRun gradh g D μ L α γ x y w v) :
IsSemiImplicitRun gradh g D μ L α γ x y v := by sorry
end NAGFlow.APGM
Source
Luo & Chen, arXiv:1909.03145v4, §7.2.2, (115) and Algorithm 2, p. 30
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.