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.

AdaGrad accumulated Gram matrices and both scales are positive semidefinite

Statement

For the AdaGrad inputs, at each round $t \in {0, \dots, T}$ the accumulated matrix $G_{t} = \sum_{s = 1}^{t} g_{s} g_{s}^{⊤}$ , with $G_{0} = 0$ , is a finite real symmetric positive-semidefinite matrix. More precisely, for every $v \in R^{d}$ , $v^{⊤} G_{t} v = \sum_{s = 1}^{t} (g_{s}^{⊤} v)^{2} \geq 0, (G_{t})_{i i} = \sum_{s = 1}^{t} g_{s, i}^{2} \geq 0.$ Here the coordinate and matrix-entry labels $i, j \in {1, \dots, d}$ are one-based: $g_{s, i} = g_{s} (i - 1)$ and $(G_{t})_{i j} = G_{t} (i - 1, j - 1)$ in the underlying zero-based conventions. Empty sums have value zero. Therefore both the full-matrix scale $G_{t}^{1 / 2}$ and the diagonal scale $diag (\sqrt{(G_{t})_{11}}, \dots, \sqrt{(G_{t})_{d d}})$ exist and are finite real symmetric positive-semidefinite matrices. Singular and zero accumulated matrices are allowed.

Statement references

Gram-matrix AdaGrad with full or singular diagonal metrics: defines the accumulated gradient outer products and the two choices of scale.

Facts & Assumptions

Given: Any finite gradient history $g_{1}, \dots, g_{t} \in R^{d}$ admitted by AdaGrad, including $t = 0$ . Coordinate and matrix-entry subscripts use the one-based relabeling specified in the Statement.

[F1]

Gram-matrix AdaGrad with full or singular diagonal metrics: the accumulator is $G_{t} = \sum_{s = 1}^{t} g_{s} g_{s}^{⊤}$ ; its full and diagonal scales are the two matrices in the Statement.

[F2]

Rectangular matrix multiplication and the identity matrix $I_{n}$ , including zero-sized shapes The transpose $A^{T}$ of a matrix: finite matrix multiplication is given by sums of entrywise products, and transposition interchanges the two indices.

[F3]

Sign rules for products and monotonicity of multiplication: a square of a real number is nonnegative, by the positive, negative, and zero cases; a finite sum of such squares is nonnegative.

[F4]

A positive-semidefinite matrix has a unique positive-semidefinite square root: every real symmetric positive-semidefinite matrix has a unique real symmetric positive-semidefinite square root.

[F5]

Square roots exist: a unique $\sqrt{a} \geq 0$ with $(\sqrt{a})^{2} = a$ ; the positives are ${x^{2} : x \neq 0}$ : every nonnegative real number has a unique nonnegative real square root.

Proof

1.1givenF1F2algebra

Write $g_{s, i}$ for the $i$ th coordinate of $g_{s}$ . By [F1, F2], $(G_{t})_{i j} = \sum_{s = 1}^{t} g_{s, i} g_{s, j}$ . These are finite real sums, and commutativity of real multiplication gives $(G_{t})_{i j} = (G_{t})_{j i}$ . Thus $G_{t}$ is finite and symmetric, also when $t = 0$ .

2.1step 1.1F2F3algebra

For arbitrary $v \in R^{d}$ , expand $v^{⊤} G_{t} v$ by [F2] and interchange the finite sum over $s$ with the two coordinate sums. For each $s$ , the coordinate sums factor as $(\sum_{i} g_{s, i} v_{i}) (\sum_{j} g_{s, j} v_{j}) = (g_{s}^{⊤} v)^{2}$ . Hence $v^{⊤} G_{t} v = \sum_{s} (g_{s}^{⊤} v)^{2} \geq 0$ by [F3], including the empty sum when $t = 0$ . Taking $i = j$ in step 1.1 also gives $(G_{t})_{i i} = \sum_{s} g_{s, i}^{2} \geq 0$ .

3.1step 1.1step 2.1F2F3F4F5algebra∎

Steps 1.1 and 2.1 verify every input hypothesis of [F4], which gives the unique full-matrix scale as a finite real symmetric positive-semidefinite matrix. By [F5], each $r_{i} = \sqrt{(G_{t})_{i i}}$ exists and is a nonnegative finite real. The diagonal matrix $D = diag (r_{1}, \dots, r_{d})$ is symmetric, and $v^{⊤} D v = \sum_{i} r_{i} v_{i}^{2} \geq 0$ by [F2, F3]. Thus the diagonal scale has the same required properties, with no positive-definiteness assumption.

Depends on

Used by

Nothing in the library uses this result yet.

Cited to discharge well-definedness by Gram-matrix AdaGrad with full or singular diagonal metrics.

Dependency tree · two levels

28 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

Duchi, Hazan, and Singer, Adaptive Subgradient Methods for Online Learning and Stochastic Optimization, §2 (AdaGrad background; the finite Gram identity is proved locally here) (standard reference, not scraped)