Lemma 2.6 (Local Descent Lemma) — f(x + d) ≤ f(x) + ∇f(x)ᵀd + (L₂(f)/2)‖d‖² for d with at most two nonzero components
ProvedSparseNLO.CWOpt.lemma_2_6Let be continuously differentiable and bounded below, with -Lipschitz gradient (Assumption 2), and let be a constant satisfying the local Lipschitz condition (2.15): for all , all and all supported in , .
Then for all indices , every and every whose nonzero components lie in ,
This is the local version of the classical descent lemma: along directions with at most two nonzero entries the quadratic upper bound holds with the local constant , which may be much smaller than the global Lipschitz constant (Example 2.1). It is the quantitative tool behind Theorem 2.4.
Formalization Note "Any vector with at most two nonzero components" is formalized as " supported in some with "; for every vector with at most two nonzero components is of this form. is any constant satisfying (2.15), in particular the paper's . Assumption 2 (with some constant ) and Assumption 1 are kept as on the page, although (2.15) is the hypothesis the inequality rests on. The inner product is the Euclidean one.
import Mathlib import Definitions.Def_SparseNLO_CWOpt_Setting open scoped RealInnerProductSpace
namespace SparseNLO.CWOpt
/-- Lemma 2.6 (Local Descent Lemma, p. 12): under Assumption 2, with `L2` a constant satisfying
(2.15), `f(x + d) ≤ f(x) + ∇f(x)ᵀd + (L2/2)‖d‖²` for every `d` with at most two nonzero
components, i.e. supported in some `{i, j}` with `i ≠ j`. -/
theorem lemma_2_6 {n : ℕ} (f : EuclideanSpace ℝ (Fin n) → ℝ) (hf : ContDiff ℝ 1 f)
(hbdd : ∃ γ : ℝ, ∀ x, γ ≤ f x)
(Lf : NNReal) (hLf : LipschitzWith Lf (gradient f))
(L2 : ℝ) (hL2 : LocalLipschitz f L2)
(i j : Fin n) (hij : i ≠ j) (x d : EuclideanSpace ℝ (Fin n))
(hd : ∀ k : Fin n, k ≠ i → k ≠ j → d k = 0) :
f (x + d) ≤ f x + ⟪gradient f x, d⟫ + L2 / 2 * ‖d‖ ^ 2 := by sorry
end SparseNLO.CWOpt
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.