LemmaStatement: Literature-sourcedProof: AI-generatedPipeline-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.

Compactness makes the Bregman projection well-defined

Statement

Let $d \geq 1$ , let $K \subseteq R^{d}$ be nonempty, bounded, closed, and convex, and let $(K, U, R)$ be a mirror regularizer with $R$ $m$ -strongly convex on $K$ for some $m > 0$ . Then $R$ has a unique minimizer on $K$ , and for every $y \in U$ the function $x \mapsto B_{R} (x ∥ y)$ has a unique minimizer $x_{+} (y)$ on $K$ . If $x_{+} (y) \in U$ , then for every $u \in K$ ,

$⟨ \nabla R (x_{+} (y)) - \nabla R (y), u - x_{+} (y) ⟩ \geq 0$

and

$B_{R} (u ∥ y) \geq B_{R} (u ∥ x_{+} (y)) + B_{R} (x_{+} (y) ∥ y) .$

Statement references

Agile online mirror descent: uses a minimizer of $R$ to initialize and a minimizer of $B_{R} (\cdot ∥ y)$ for each dual point $y$ .

Mirror maps, Bregman divergence, and local Hessian norms: gives continuity of $R$ on $K$ , the strong-convexity inequality, and the Bregman formula.

The Euclidean inner product $⟨ x, y ⟩ = \sum_{k < n} x_{k} y_{k}$ on $R^{n}$ : the strong-convexity inequality uses the standard Euclidean norm.

The Bregman three-point identity: states the algebraic identity used for the Pythagorean inequality.

Upper and lower semicontinuity on subsets of $R^{n}$ : continuity implies lower semicontinuity on a Euclidean subset.

Facts & Assumptions

Given: The set $K$ , the mirror regularizer $(K, U, R)$ , its strong-convexity constant $m > 0$ , and any fixed $y \in U$ .

[F1]

Agile online mirror descent: $K$ is bounded, closed, and convex, $R$ is strongly convex on $K$ , and the Bregman projection minimizes $B_{R} (x ∥ y)$ over $x \in K$ .

[F2]

Mirror maps, Bregman divergence, and local Hessian norms: $R$ is continuous on $K$ , and $B_{R} (x ∥ y) = R (x) - R (y) - ⟨ \nabla R (y), x - y ⟩$ for $x \in K$ , $y \in U$ .

[F3]

Heine-Borel in $R^{n}$ : with the Euclidean metric a subset of $R^{n}$ is compact if and only if it is closed and bounded, and the proof by bisection uses no choice principle; the same holds on the real line: closed bounded subsets of finite-dimensional Euclidean space are compact.

[F4]

Semicontinuous extreme value theorem on compact Euclidean sets: every real-valued lower semicontinuous function on a nonempty compact Euclidean set attains its minimum.

[F5]

A convex subset of $R^{m}$ contains every line segment between two of its points: every segment between two points of $K$ lies in $K$ .

[F6]

The Bregman three-point identity: for $u \in K$ and $x, y \in U$ , $⟨ u - x, \nabla R (y) - \nabla R (x) ⟩ = B_{R} (u ∥ x) - B_{R} (u ∥ y) + B_{R} (x ∥ y)$ .

[F7]

Upper and lower semicontinuity on subsets of $R^{n}$ : a continuous real-valued function on a Euclidean subset is lower semicontinuous there.

Proof

1.1givenF2F3F4F7

By [F3], $K$ is compact. Continuity of $R$ on the nonempty set $K$ and [F7] make it lower semicontinuous; [F4] then implies that $R$ attains a minimum on $K$ .

1.2givenF2F5algebra

Suppose $x_{+} (y) \in U$ and fix $u \in K$ . The segment from $x_{+} (y)$ to $u$ lies in $K$ by [F5], and because $U$ is open it remains in $U$ for all sufficiently small nonnegative segment parameters. Since $x_{+} (y)$ minimizes $B_{R} (\cdot ∥ y)$ , the right derivative at zero of $s \mapsto B_{R} (x_{+} (y) + s (u - x_{+} (y)) ∥ y)$ is nonnegative. Differentiating its defining formula at $s = 0$ gives $⟨ \nabla R (x_{+} (y)) - \nabla R (y), u - x_{+} (y) ⟩ \geq 0$ .

2.1step 1.1F1F5algebra

If two distinct points minimized $R$ , their midpoint would lie in $K$ by [F5]. The strong-convexity inequality at $λ = 1 / 2$ would make its value at least $m ∥ x - y ∥_{2}^{2} / 8$ below the common minimum, a contradiction. Thus the minimizer is unique.

3.1givenstep 2.1F1F2F3F4F7algebra

For fixed $y \in U$ , the formula in [F2] writes $B_{R} (x ∥ y)$ as the continuous function $R (x)$ plus an affine function of $x$ . It is therefore lower semicontinuous by [F7] and attains a minimum on compact $K$ by [F3, F4]. If two distinct points minimized it, the affine term would cancel from the strong-convexity inequality for $R$ , giving the same strict midpoint contradiction as in step 2.1. Hence its minimizer $x_{+} (y)$ is unique.

4.1step 1.2F6algebra∎

Apply [F6] with $x = x_{+} (y)$ . Step 1.2 makes its left side nonpositive, so $B_{R} (u ∥ x_{+} (y)) - B_{R} (u ∥ y) + B_{R} (x_{+} (y) ∥ y) \leq 0$ . Rearranging proves the stated Pythagorean inequality.

Depends on

Used by

Cited to discharge well-definedness by Agile online mirror descent.

Dependency tree · two levels

57 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)