Footnote 2 — under (2.2), strong convexity in forces
ProvedNesterovRCD.Constrained.footnote2convex-optimizationcoordinate-descentp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1strong-convexity
Let with and every , each block carrying a Euclidean norm (3.4). Let have a coordinate-wise Lipschitz gradient (2.2) with constants , and let be strongly convex in the norm of (3.5) with convexity parameter (3.1). Then
In the proof of Theorem 5 this guarantees that lies in and that the contraction factor of (4.6) is nonnegative.
Formalization Note The paper's blocks are with ; Lean states this as nontriviality of every block space. It cannot be dropped: if every block were the zero space, every would satisfy the hypotheses. Indices are Fin n, 0-based.
Preamble
import Mathlib import Definitions.Def_NesterovRCD_HighProb_Basic import Definitions.Def_NesterovRCD_Constrained_UCDM
Formal statement
namespace NesterovRCD.Constrained
variable {n : ℕ} {E : Fin n → Type*} [∀ i, NormedAddCommGroup (E i)] [∀ i, InnerProductSpace ℝ (E i)]
[∀ i, FiniteDimensional ℝ (E i)]
theorem footnote2 (hn : 0 < n) [∀ i, Nontrivial (E i)] (f : NesterovRCD.Sublinear.Blocks E → ℝ) (L : Fin n → ℝ)
(hL : NesterovRCD.Sublinear.CoordLipschitz f L) (σ : ℝ) (hσ : 0 < σ) (hsc : NesterovRCD.HighProb.StronglyConvexW f L 1 σ) :
σ ≤ 1 := by sorry
end NesterovRCD.Constrained
Source
Nesterov, Efficiency of coordinate descent methods on huge-scale optimization problems, CORE Discussion Paper 2010/2, p. 14, footnote 2) (to the proof of Theorem 5)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.