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

One-step diagonal AdaGrad regret inequality

Statement

Let $A = diag (a_{1}, \dots, a_{d})$ with $a_{j} > 0$ , let $C \subseteq R^{d}$ be nonempty, closed, and convex, and let $x, x^{+}, u \in C$ where $x^{+}$ minimizes $η ⟨ g, z ⟩ + \frac{1}{2} ∥ z - x ∥_{A}^{2}$ over $z \in C$ , for $η > 0$ and $g \in R^{d}$ . With $∥ w ∥_{A}^{2} = w^{T} A w$ , $A^{- 1} = diag (1 / a_{1}, \dots, 1 / a_{d})$ , and $∥ g ∥_{A^{- 1}}^{2} = g^{T} A^{- 1} g$ ,

$⟨ g, x - u ⟩ \leq \frac{∥ x - u ∥_{A}^{2} - ∥ x^{+} - u ∥_{A}^{2}}{2 η} + \frac{η}{2} ∥ g ∥_{A^{- 1}}^{2} .$

Facts & Assumptions

Given: The set, positive diagonal matrix, step size, gradient, comparator, and minimizer in the Statement. In coordinate expansions use the one-based labels $z_{j} : = z (j - 1)$ for $1 \leq j \leq d$ , as in [F1].

[F1]

Diagonal AdaGrad for online convex losses: an update minimizes $η ⟨ g, z ⟩ + \frac{1}{2} ∥ z - x ∥_{A}^{2}$ on $C$ , with positive diagonal $A$ .

[F2]

Diagonal AdaGrad subproblem has a unique minimizer: for these data the minimizer exists and is unique.

[F3]

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

[F4]

The metric topology: a set is open when every one of its points has a ball around it inside the set; closed means open complement: closed means that the complement is open in the stated metric topology.

[F5]

The Euclidean inner product $⟨ x, y ⟩ = \sum_{k < n} x_{k} y_{k}$ on $R^{n}$ : the inner product is bilinear and the squared Euclidean norm is the sum of coordinate squares.

[F6]

Square roots exist: a unique $\sqrt{a} \geq 0$ with $(\sqrt{a})^{2} = a$ ; the positives are ${x^{2} : x \neq 0}$ : each positive diagonal entry has a positive square root.

[F7]

Laws of finite sums and finite products: a finite sum of nonnegative terms is nonnegative.

[F8]

Squares of nonzero elements are positive gives positivity for each nonzero coordinate square; Multiplication by zero: $0 \cdot a = 0$ gives square zero for a zero coordinate. Thus every coordinate square is nonnegative.

[F9]

Ordered field and Sign rules for products and monotonicity of multiplication, with Multiplication by zero: $0 \cdot a = 0$ and Inverses of positives are positive, and reciprocation reverses order for zero factors and reciprocals: sums and products of nonnegative reals are nonnegative, and a positive denominator preserves order.

[F10]

The multiplicative identity is positive: $1 > 0$ .

Proof

Given: The objects and assumptions in the Statement.

1.1F1F2F3F4F5F7F8F9F10givenalgebra

Write $q (z) = η ⟨ g, z ⟩ + \frac{1}{2} ∥ z - x ∥_{A}^{2}$ , $d = u - x^{+}$ , $c = ⟨ η g + A (x^{+} - x), d ⟩$ , and $Q = ∥ d ∥_{A}^{2} \geq 0$ , the last inequality following from [F5], [F7], [F8], and [F9]. Since $C$ is nonempty, closed in the metric topology [F4], and convex, [F2] ensures the unique update minimizer exists. For $0 < s \leq 1$ , [F3] gives $x^{+} + s d \in C$ , so [F1] minimality gives $0 \leq q (x^{+} + s d) - q (x^{+}) = s c + (s^{2} / 2) Q$ . If $c < 0$ , put $a = - c > 0$ and $s = a / (Q + a + 1)$ . By [F9] and [F10], $Q + a + 1 > a > 0$ , so $0 < s < 1$ and $Q < Q + a + 1$ . Dividing the minimality inequality by $s > 0$ gives $0 \leq c + s Q / 2$ , whereas $s Q / 2 = a Q / (2 (Q + a + 1)) < a / 2$ , so $c + s Q / 2 < - a / 2 < 0$ , a contradiction. Thus $c \geq 0$ , which rearranges to $η ⟨ g, x^{+} - u ⟩ \leq ⟨ A (x - x^{+}), x^{+} - u ⟩$ .

2.1F5F6F7F8step 1.1givenalgebra∎

Expanding gives $2 ⟨ A (x - x^{+}), x^{+} - u ⟩ = ∥ x - u ∥_{A}^{2} - ∥ x^{+} - u ∥_{A}^{2} - ∥ x - x^{+} ∥_{A}^{2}$ . Also [F5]–[F8] and nonnegativity of squares give $0 \leq \sum_{j} (\sqrt{a_{j}} (x_{j} - x_{j}^{+}) - η g_{j} / \sqrt{a_{j}})^{2}$ , hence $η ⟨ g, x - x^{+} ⟩ - \frac{1}{2} ∥ x - x^{+} ∥_{A}^{2} \leq (η^{2} / 2) ∥ g ∥_{A^{- 1}}^{2}$ . Add the inequality from step 1.1 and divide by $η > 0$ to obtain the Statement.

Depends on

Used by

Diagonal AdaGrad regret bound Theorem

Dependency tree · two levels

46 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

John Duchi, Elad Hazan, and Yoram Singer, Adaptive Subgradient Methods for Online Learning and Stochastic Optimization, JMLR 12 (2011) (standard reference, not scraped)
Sébastien Bubeck, Convex Optimization: Algorithms and Complexity, complete monograph (standard reference, not scraped)