LemmaStatement: AI-adaptedProof: AI-adaptedPipeline-generatedjudge pass (gpt-6-luna)

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

A Hessian lower bound gives strong convexity and gradient-gap bounds

Statement

Let $U \subseteq R^{d}$ be open and convex, let $f \in C^{2} (U, R)$ , and fix $μ > 0$ . Suppose $v^{T} H_{f} (z) v \geq μ ∥ v ∥_{2}^{2}$ for every $z \in U$ and $v \in R^{d}$ . Then for every $x, y \in U$ ,

$f (y) \geq f (x) + ⟨ \nabla f (x), y - x ⟩ + \frac{μ}{2} ∥ y - x ∥_{2}^{2},$

and

$⟨ \nabla f (y) - \nabla f (x), y - x ⟩ \geq μ ∥ y - x ∥_{2}^{2} .$

If $x^{*} \in U$ is a global minimizer and $f^{*} : = f (x^{*})$ , it is unique and every $x \in U$ satisfies

$f (x) - f^{*} \geq \frac{μ}{2} ∥ x - x^{*} ∥_{2}^{2}, ∥ \nabla f (x) ∥_{2}^{2} \geq 2 μ (f (x) - f^{*}) .$

Here $H_{f}$ is the matrix of second partial derivatives and $\nabla f$ is the vector of first partial derivatives, as in The Hessian matrix and critical points of a scalar field and The Jacobian matrix of partial derivatives and the gradient in the scalar-valued case.

Facts & Assumptions

Given: An open convex $U \subseteq R^{d}$ , $f \in C^{2} (U, R)$ , $μ > 0$ , and $v^{T} H_{f} (z) v \geq μ ∥ v ∥_{2}^{2}$ for every $z \in U$ and $v \in R^{d}$ .

[F1]

Multivariable Taylor formula with a Lagrange remainder along a line segment: for a $C^{2}$ function on an open convex set and a segment in that set, the first-order Taylor formula has a second-order Hessian remainder at a point on the segment.

[F2]

A $C^{2}$ function is convex exactly when its Hessian is positive semidefinite: a $C^{2}$ function on an open convex set is convex if and only if its Hessian is positive semidefinite everywhere.

[F3]

The Hessian matrix and critical points of a scalar field and The Jacobian matrix of partial derivatives and the gradient in the scalar-valued case: $H_{f}$ is the matrix of second partial derivatives; $\nabla f$ has the first partial derivatives as its standard coordinates.

[F4]

Directional derivatives and partial derivatives of a map $U \subseteq R^{m} \to R^{n}$ : the derivative of $t \mapsto f (a + t v)$ at $0$ is the directional derivative $D_{v} f (a)$ ; for a standard basis vector it is the corresponding partial derivative.

[F5]

Cauchy-Schwarz $∣ ⟨ x, y ⟩ ∣ \leq ∥ x ∥_{2} ∥ y ∥_{2}$ with its equality case, the triangle inequality for $∥ \cdot ∥_{2}$ , the parallelogram law and polarisation: $∣ ⟨ u, v ⟩ ∣ \leq ∥ u ∥_{2} ∥ v ∥_{2}$ .

Proof

1.1F1F2F3given

For any $x, y \in U$ , convexity keeps the segment from $x$ to $y$ in $U$ . Applying [F1] with Taylor order one gives $f (y) = f (x) + ⟨ \nabla f (x), y - x ⟩ + \frac{1}{2} (y - x)^{T} H_{f} (x + θ (y - x)) (y - x)$ for some $θ \in (0, 1)$ . The Hessian hypothesis makes the last term at least $μ ∥ y - x ∥_{2}^{2} / 2$ , proving the first inequality. Since $H_{f} ⪰ μ I ⪰ 0$ , [F2] also makes $f$ convex on $U$ .

1.2F3F4given

Let $x^{*}$ be an interior minimizer. For each standard basis vector $e_{j}$ , openness gives an interval around $0$ on which $x^{*} + t e_{j} \in U$ . The one-variable function $t \mapsto f (x^{*} + t e_{j})$ has a minimum at $0$ , so its derivative there is $0$ ; [F4] identifies this derivative with $\partial_{j} f (x^{*})$ . Thus every coordinate of $\nabla f (x^{*})$ is zero.

2.1step 1.1algebra

Apply the first inequality from step 1.1 once to $(x, y)$ and once to $(y, x)$ , and add. The function-value terms cancel, leaving $⟨ \nabla f (y) - \nabla f (x), y - x ⟩ \geq μ ∥ y - x ∥_{2}^{2}$ .

2.2step 1.1step 1.2

Apply step 1.1 with $x = x^{*}$ and $y = x$ . Using $\nabla f (x^{*}) = 0$ gives $f (x) - f^{*} \geq μ ∥ x - x^{*} ∥_{2}^{2} / 2$ . This also proves uniqueness, because equality of the minimum values forces $x = x^{*}$ .

3.1F5step 1.1algebra∎

Apply step 1.1 with the ordered pair $(x, x^{*})$ and write $d : = x - x^{*}$ . Rearrangement gives $f (x) - f^{*} \leq ⟨ \nabla f (x), d ⟩ - μ ∥ d ∥_{2}^{2} / 2$ . By [F5] and completing the square, the right-hand side is at most $∥ \nabla f (x) ∥_{2}^{2} / (2 μ)$ , since $0 \leq (∥ \nabla f (x) ∥_{2} - μ ∥ d ∥_{2})^{2}$ . This is the gradient-gap inequality.

Depends on

Used by

Dependency tree · two levels

32 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Stephen Boyd and Lieven Vandenberghe, Convex Optimization (standard reference, not scraped)
Philip E. Gill and Margaret H. Wright, Math 171B Numerical Optimization Class Notes (standard reference, not scraped)