(2.12), p. 7 — for convex f ∈ C^{1,1}_L with ∇f(x*) = 0, (1/L)‖∇f(y)‖² ≤ ⟨∇f(y), y − x*⟩
ProvedGhadimiLan.RSG.eq_2_12convex-optimizationp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1smooth-optimization
Let with be convex, and let satisfy . Then for every ,
In the proof of Theorem 2.1 b) this is applied at the iterates ; it is the co-coercivity inequality (1.8) specialized to a stationary point, and it controls the gradient term in the distance recursion for .
Formalization Note The paper writes the inequality at ; it holds for every point, and is stated so.
Preamble
import Mathlib import Definitions.Def_ConvexOptAlg_SmoothGD_Defs import Definitions.Def_GhadimiLan_RSG_Model open MeasureTheory ProbabilityTheory open scoped InnerProductSpace
Formal statement
namespace GhadimiLan.RSG
/-- Eq. (2.12) (Ghadimi & Lan, arXiv:1309.5549v1, proof of Theorem 2.1 b), p. 7): for a convex
`f ∈ C^{1,1}_L(ℝⁿ)` (`L > 0`) with gradient map `g = ∇f` and a point `x*` with
`∇f(x*) = 0`, every `y` satisfies `(1/L)‖∇f(y)‖² ≤ ⟨∇f(y), y − x*⟩`. The paper states it at
the iterate `y = x_k`; the claim does not depend on how `y` was produced. -/
theorem eq_2_12 {n : ℕ} (f : E n → ℝ) (g : E n → E n) (L : ℝ)
(hf : ConvexOptAlg.SmoothGD.IsBetaSmooth f g L) (hL : 0 < L)
(hconv : ConvexOn ℝ Set.univ f) (xstar : E n) (hxstar : g xstar = 0) (y : E n) :
1 / L * ‖g y‖ ^ 2 ≤ ⟪g y, y - xstar⟫_ℝ := by sorry
end GhadimiLan.RSG
Source
Ghadimi & Lan, arXiv:1309.5549v1, proof of Theorem 2.1 b), Eq. (2.12), p. 7
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.