LemmaStatement: Literature-sourcedProof: AI-generatedPipeline-generated

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.

Positive Hessians make Bregman divergence nonnegative

Statement

Let $(K, U, R)$ be a mirror regularizer, and suppose $R$ is $m$ -strongly convex on $K$ for some $m > 0$ . For $x, y \in U$ ,

$B_{R} (x ∥ y) \geq 0,$

with strict inequality when $x \neq y$ . For $x \in K$ and $y \in K \cap U$ ,

$B_{R} (x ∥ y) \geq \frac{m}{2} ∥ x - y ∥_{2}^{2} .$

Statement references

Mirror maps, Bregman divergence, and local Hessian norms: defines the Bregman formula, the positive-definite Hessian on $U$ , and strong convexity on $K$ .

Multivariable Taylor formula with a Lagrange remainder along a line segment: gives a second-order Taylor formula with a Hessian evaluated at an intermediate point of the segment.

Facts & Assumptions

Given: A mirror regularizer $(K, U, R)$ , a strong-convexity constant $m > 0$ on $K$ , and the points in the Statement.

[F1]

Mirror maps, Bregman divergence, and local Hessian norms: $B_{R} (x ∥ y) = R (x) - R (y) - ⟨ \nabla R (y), x - y ⟩$ ; $R$ is $C^{2}$ with positive-definite Hessian on open convex $U$ , and its strong-convexity inequality holds on $K$ .

[F2]

Multivariable Taylor formula with a Lagrange remainder along a line segment: for a $C^{2}$ scalar function on open convex $U$ and $a, a + h \in U$ , some $θ \in (0, 1)$ gives $R (a + h) = R (a) + ⟨ \nabla R (a), h ⟩ + \frac{1}{2} h^{⊤} H_{R} (a + θ h) h$ .

Proof

1.1givenF1F2casesalgebra

For distinct $x, y \in U$ , apply [F2] at $a = y$ and $h = x - y$ . By [F1], the remainder identity gives $B_{R} (x ∥ y) = \frac{1}{2} (x - y)^{⊤} H_{R} (y + θ (x - y)) (x - y) > 0$ , because the Hessian is positive definite and $x - y \neq 0$ . If $x = y$ , the defining formula gives $B_{R} (x ∥ y) = 0$ . Thus the first claim holds.

1.2givenF1algebra

Fix $x \in K$ and $y \in K \cap U$ , and put $d = x - y$ . For $0 < λ < 1$ , strong convexity in [F1] gives $R (y + λ d) \leq (1 - λ) R (y) + λ R (x) - \frac{m}{2} λ (1 - λ) ∥ d ∥_{2}^{2}$ . Rearranging yields $R (x) - R (y) - [R (y + λ d) - R (y)] / λ \geq \frac{m}{2} (1 - λ) ∥ d ∥_{2}^{2}$ .

2.1step 1.2F1algebra∎

As $λ ↓ 0$ , $y + λ d$ lies in the open set $U$ for all sufficiently small $λ$ , and differentiability gives $[R (y + λ d) - R (y)] / λ \to ⟨ \nabla R (y), d ⟩$ . Taking the derivative limit in step 1.2 gives $B_{R} (x ∥ y) \geq \frac{m}{2} ∥ d ∥_{2}^{2}$ .

Depends on

Used by

Dependency tree · two levels

13 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

Elad Hazan, Introduction to Online Convex Optimization, second edition (standard reference, not scraped)
Peter Bartlett, Stat 260/CS 294-102: Learning in Sequential Decision Problems, mirror-descent lecture notes (standard reference, not scraped)