Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 1 — descent estimate and quadratic-direction bound

Proved
TsengCGD.Global.lemma1

by mikedeng1 · Oct 6, 2026 · Mathlib 0df444a (Lean v4.33.1)

composite-optimizationcoordinate-descentnonsmooth-optimizationp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1

Let x∈dom⁡Px\in\operatorname{dom}Px∈domP, let J\mathcal JJ be a nonempty coordinate set, and let HHH be positive definite. If d=dH(x;J)d=d_H(x;\mathcal J)d=dH​(x;J) is the exact minimizer of the coordinate quadratic subproblem and g=∇f(x)g=\nabla f(x)g=∇f(x), then, for 0<α≤10<\alpha\le10<α≤1,

Fc(x+αd)≤Fc(x)+α(g⊤d+cP(x+d)−cP(x))+o(α),F_c(x+\alpha d)\le F_c(x)+\alpha\bigl(g^\top d+cP(x+d)-cP(x)\bigr)+o(\alpha),Fc​(x+αd)≤Fc​(x)+α(g⊤d+cP(x+d)−cP(x))+o(α),

and

g⊤d+cP(x+d)−cP(x)≤−d⊤Hd.g^\top d+cP(x+d)-cP(x)\le-d^\top Hd.g⊤d+cP(x+d)−cP(x)≤−d⊤Hd.

The first inequality relates the actual objective to the model direction; the second provides its quantitative descent bound.

Formalization Note The standing assumptions of (1) are explicit. The line segment x+αdx+\alpha dx+αd belongs to DDD, so the displayed objective is finite. The remainder is a function r(α)r(\alpha)r(α) with r(α)/α→0r(\alpha)/\alpha\to0r(α)/α→0 from the right; the statement holds for every exact minimizer.

Preamble
import Mathlib
import Definitions.Def_TsengCGD_Global_Basic
Formal statement
namespace TsengCGD.Global

open Filter Topology Finset Matrix
open scoped RealInnerProductSpace

theorem lemma1 {n : ℕ} (f : Vec n → ℝ) (D : Set (Vec n)) (P : Vec n → ℝ)
    (c : ℝ) (hs : Standing f D P c)
    (x : Vec n) (hx : x ∈ D) (J : Finset (Fin n)) (hJ : J.Nonempty)
    (H : Matrix (Fin n) (Fin n) ℝ) (hH : H.PosDef)
    (d : Vec n) (hd : IsDir f D P c H x J d) :
    (∃ r : ℝ → ℝ, Tendsto (fun a => r a / a) (𝓝[>] (0 : ℝ)) (𝓝 0) ∧
      ∀ a ∈ Set.Ioc (0 : ℝ) 1,
        x + a • d ∈ D ∧
        Fc f P c (x + a • d) ≤
          Fc f P c x + a * (⟪gradient f x, d⟫ + c * P (x + d) - c * P x) + r a) ∧
    ⟪gradient f x, d⟫ + c * P (x + d) - c * P x ≤ -qf H d := by sorry

end TsengCGD.Global
Source
Tseng and Yun, A coordinate gradient descent method for nonsmooth separable minimization, Math. Program. Ser. B 117 (2009), p. 391, Lemma 1, equations (7)–(8), https://doi.org/10.1007/s10107-007-0170-0
Human review
  • Endorsed by Shuze Chen · Oct 6, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 6, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me