Lemma 3 — optimality condition for a composite problem
ProvedStochCoordProx.lemma_3_optimality_conditionhigh-probability-boundsnonconvex-optimizationp2o-gran-per-chapterp2o-plan-paperp2o-v1proximal-gradientstochastic-coordinate-descent
Consider the composite problem on , where is differentiable and is convex on its convex domain . Let . Then is a stationary point of on if and only if
Here "stationary" means directional stationarity: for every , .
The lemma is applied to the subproblem (9) when is convex along the subspaces, with the quadratic part and .
Differences from the source:
- reading: y* is a stationary point (undefined in the paper, cited from [32]) → IsDirStationary: liminf_{t↓0} ((θ+φ)(y*+t(y−y*)) − (θ+φ)(y*))/t ≥ 0 for every y ∈ D; reason: first-order stationarity on a convex set; reading it as (15) or as −∇θ(y*) ∈ ∂φ(y*) would make the lemma a restatement
- encoding: φ convex on its convex domain dom φ; y* in the problem's domain → φ : ℝᵐ → ℝ with ConvexOn ℝ D φ (which includes convexity of D), and y* ∈ D; reason: only the values of φ on D enter the statement
- encoding: an unspecified finite-dimensional space (ℝᵖ in the application) → EuclideanSpace ℝ (Fin m), for every m; reason: Lean convention; same instances
Preamble
import Mathlib import Definitions.Def_StochCoordProx_IsDirStationary open scoped InnerProductSpace
Formal statement
namespace StochCoordProx
/-- **Lemma 3 (optimality condition for a composite problem).** Consider
`min_{x ∈ dom φ} θ(x) + φ(x)` on `ℝᵐ`, where `θ` is differentiable and `φ` is convex on the convex
domain `dom φ = D`. Then `y* ∈ D` is a stationary point if and only if
`⟨∇θ(y*), y − y*⟩ + φ(y) − φ(y*) ≥ 0` for all `y ∈ D` (15).
Necoara & Chorobura, arXiv:2104.13370v3, Lemma 3, display (15), p.9.
**Formalization Note.** "Stationary point", which the paper does not define, is read as
first-order directional stationarity of `θ + φ` on `D` (`IsDirStationary`). `φ` is a real
function on `ℝᵐ` and `D` plays the role of `dom φ`; `ConvexOn ℝ D φ` includes convexity of `D`.
`ℝᵐ` is `EuclideanSpace ℝ (Fin m)` and `∇θ` is `gradient θ`. -/
theorem lemma_3_optimality_condition {m : ℕ} (θ φ : EuclideanSpace ℝ (Fin m) → ℝ)
(D : Set (EuclideanSpace ℝ (Fin m))) (hθ : Differentiable ℝ θ) (hφ : ConvexOn ℝ D φ)
(ystar : EuclideanSpace ℝ (Fin m)) (hystar : ystar ∈ D) :
IsDirStationary (fun y => θ y + φ y) D ystar ↔
∀ y ∈ D, ⟪gradient θ ystar, y - ystar⟫_ℝ + φ y - φ ystar ≥ 0 := by sorry
end StochCoordProx
Source
Necoara & Chorobura, Efficiency of stochastic coordinate proximal gradient methods on nonseparable composite optimization, arXiv:2104.13370v3, Lemma 3, display (15), p.9
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.