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.Partial.lemma_2_6Let be continuously differentiable and bounded below (Assumption 1), 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 . It is the tool behind every decrease estimate of Lemma 4.1.
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.
import Mathlib import Definitions.Def_SparseNLO_Partial_Setting open scoped RealInnerProductSpace
namespace SparseNLO.Partial
/-- 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.Partial
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.