Lemma 7.1, p. 29 — f(y) ≥ f(S_f(x)) + ⟨G_f(x), y − x⟩ + (μ/2)‖y − x‖² + ‖G_f(x)‖²/(2L)
ProvedNAGFlow.APGM.lemma_7_1convex-optimizationgradient-mappingp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1proximal-gradient
Let be a real Hilbert space and , where with and is proper, closed and convex. Write and . Then for every and every ,
The right-hand side is a quadratic lower model of at built from the gradient mapping; it is the composite analogue of -convexity plus the descent lemma, and it is the only property of used in the convergence proof of Algorithm 2.
Formalization Note. The page says "for any "; for its left side is and (114) is void, so the statement is made for . is a named point satisfying the prox predicate with . is the inner product of (Riesz).
Preamble
import Mathlib import Definitions.Def_NAGFlow_APGM_Setting
Formal statement
namespace NAGFlow.APGM
/-- Lemma 7.1 (Luo & Chen, arXiv:1909.03145v4, p. 29). Assume `f = h + g`, where `h ∈ S^{1,1}_{μ,L}`
with `0 ≤ μ ≤ L < ∞` and `g : V → ℝ ∪ {+∞}` is proper, closed and convex (encoded by `(g, D)`,
`D = dom g`). Then for any `x ∈ V` and any `y ∈ dom g` (for `y ∉ dom g` the page's `f(y) = +∞` and the
inequality is void), with `S_f(x) = prox_{g/L}(x − ∇h(x)/L)` and `G_f(x) = L(x − S_f(x))`,
`f(y) ≥ f(S_f(x)) + ⟪G_f(x), y − x⟫ + (μ/2)‖y − x‖² + (1/(2L))‖G_f(x)‖²` (114). -/
theorem lemma_7_1 {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)
(x y s : V) (hy : y ∈ D) (hs : IsSf gradh g D (1 / L) x s) :
(h + g) y ≥ (h + g) s + inner ℝ (gradMap (1 / L) x s) (y - x) + μ / 2 * ‖y - x‖ ^ 2
+ 1 / (2 * L) * ‖gradMap (1 / L) x s‖ ^ 2 := by sorry
end NAGFlow.APGM
Source
Luo & Chen, arXiv:1909.03145v4, Lemma 7.1 and (114), p. 29
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.