Lemma 1 — descent lemma along
ProvedStochCoordProx.lemma_1_descent_along_Uhigh-probability-boundsnonconvex-optimizationp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1proximal-gradientstochastic-coordinate-descent
Let be differentiable, let , and suppose is smooth along , i.e. for all , . Then
This quadratic bound along the subspace is the basic estimate behind the descent property of SCPG (Lemma 4).
Differences from the source:
- generalization: Assumption 1 [A.1] for every U in the family 𝒰 → one matrix U with a constant L_U satisfying (2); reason: the conclusion concerns one U; A.1 supplies this for every U ∈ 𝒰
- generalization: f is L_U smooth along U (A.1) → f differentiable on ℝⁿ and (2) for U with constant L_U; reason: the paper defines the term by (2) and uses nothing else; any smooth f satisfying (2) is an instance
- encoding: vectors of ℝⁿ, ℝᵖ and matrices U ∈ ℝ^{n×p} → EuclideanSpace ℝ (Fin n), EuclideanSpace ℝ (Fin p), U acting through Matrix.toEuclideanLin; reason: Lean convention; the Euclidean norm and inner product of the paper, same instances
- generalization: the set 𝒰 bounded (standing assumption, p.4); 𝓛_F(x₀) bounded (standing assumption, p.7: "Throughout the paper, we also assume boundedness of the level set") → not assumed; reason: the proof does not use them; they serve only to make H_{F,max} finite, which this statement does not involve; every instance satisfying them is covered
Preamble
import Mathlib import Definitions.Def_StochCoordProx_IsSmoothAlong open Matrix open scoped InnerProductSpace
Formal statement
namespace StochCoordProx
/-- **Lemma 1 (descent lemma along `U`).** If `f : ℝⁿ → ℝ` is differentiable and `L_U` smooth
along `U ∈ ℝ^{n×p}` (display (2)), then for all `x ∈ ℝⁿ` and `h ∈ ℝᵖ`
`|f(x + U h) − f(x) − ⟨Uᵀ∇f(x), h⟩| ≤ (L_U/2) ‖h‖²` (3).
Necoara & Chorobura, arXiv:2104.13370v3, Lemma 1, display (3), p.5.
**Formalization Note.** Stated for one matrix `U` with its constant `L_U` ("Assumption 1 [A1]"
restricted to that `U`). Euclidean spaces; `U` acts as `Matrix.toEuclideanLin U`. -/
theorem lemma_1_descent_along_U {n p : ℕ} (f : EuclideanSpace ℝ (Fin n) → ℝ)
(U : Matrix (Fin n) (Fin p) ℝ) (LU : ℝ) (hf : Differentiable ℝ f)
(hL : IsSmoothAlong f U LU) (x : EuclideanSpace ℝ (Fin n)) (h : EuclideanSpace ℝ (Fin p)) :
|f (x + Matrix.toEuclideanLin U h) - f x - ⟪Matrix.toEuclideanLin Uᵀ (gradient f x), h⟫_ℝ| ≤
LU / 2 * ‖h‖ ^ 2 := by sorry
end StochCoordProx
Source
Necoara & Chorobura, Efficiency of stochastic coordinate proximal gradient methods on nonseparable composite optimization, arXiv:2104.13370v3, Lemma 1, display (3), p.5
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.