TheoremStatement: AI-adaptedProof: 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.

A corrected regret bound for agile mirror descent

Statement

Let $d \geq 1$ and let $(K, U, R)$ be a mirror regularizer on $K \subseteq R^{d}$ , with $K$ nonempty, bounded, closed, and convex, $U$ open and convex, positive-definite Hessian on $U$ , and $R$ $m$ -strongly convex on $K$ for some $m > 0$ . Let $T \geq 1$ be an integer and $η > 0$ . Let $x_{1} \in K \cap U$ minimize $R$ on $K$ . For every $t = 1, \dots, T$ , suppose $x_{t}, x_{t + 1} \in K \cap U$ , $y_{t + 1} \in U$ , and

$\nabla R (y_{t + 1}) = \nabla R (x_{t}) - η g_{t}, x_{t + 1} \in \arg \min_{x \in K} B_{R} (x ∥ y_{t + 1}) .$

For each $t$ , let either $f_{t}$ be differentiable and convex on an open convex set containing $K$ with $g_{t} = \nabla f_{t} (x_{t})$ , or let $f_{t}$ be convex on a convex set containing $K$ with $f_{t} (u) \geq f_{t} (x_{t}) + ⟨ g_{t}, u - x_{t} ⟩$ for every $u \in K$ . Define the pointwise regret by $R_{T} (u) : = \sum_{t = 1}^{T} (f_{t} (x_{t}) - f_{t} (u))$ . For each $t$ , there exists $z_{t}$ on the segment $[x_{t}, y_{t + 1}]$ such that

$2 B_{R} (y_{t + 1} ∥ x_{t}) = ∥ x_{t} - y_{t + 1} ∥_{z_{t}}^{2} .$

For every comparator $u \in K$ ,

$R_{T} (u) \leq \frac{R (u) - R (x_{1})}{η} + \frac{η}{2} \sum_{t = 1}^{T} ∥ g_{t} ∥_{*, z_{t}}^{2} .$

The range diameter $D_{R}^{2} : = \max_{x, y \in K} (R (x) - R (y))$ is finite, and $D_{R} : = \sqrt{D_{R}^{2}}$ . If $D_{R} > 0$ , $G_{R} > 0$ , and $∥ g_{t} ∥_{*, z_{t}} \leq G_{R}$ for all $t$ , then $η = D_{R} / (G_{R} \sqrt{T})$ gives $R_{T} (u) \leq \frac{3}{2} D_{R} G_{R} \sqrt{T}$ . Minimizing the corrected right-hand expression over $η > 0$ instead gives $η = \sqrt{2} D_{R} / (G_{R} \sqrt{T})$ and $R_{T} (u) \leq \sqrt{2} D_{R} G_{R} \sqrt{T}$ .

Statement references

Agile online mirror descent: defines the agile dual update, the Bregman projection, the full-information timing, and the optional supplied-subgradient branch.

Mirror maps, Bregman divergence, and local Hessian norms: defines $B_{R}$ , the local primal/dual Hessian norms, and strong convexity on $K$ .

Static, dynamic, interval, and strongly adaptive regret: defines pointwise regret against a fixed comparator $u \in K$ .

A convex subset of $R^{m}$ contains every line segment between two of its points: convexity of $K$ supplies the segments used in the minimizer and projection arguments.

Convex and strictly convex functions on Euclidean convex sets: defines convexity of the loss functions.

The Euclidean inner product $⟨ x, y ⟩ = \sum_{k < n} x_{k} y_{k}$ on $R^{n}$ : defines the pairings and Euclidean norms in the local Hessian calculations.

The Jacobian matrix of partial derivatives and the gradient in the scalar-valued case: defines each loss gradient as its standard-coordinate partial-derivative vector.

Differentiable convex functions are characterized by the gradient inequality: the smooth loss case gives the supporting inequality used in the proof.

Subgradients and the subdifferential of a convex function: defines the supplied supporting vector in the nonsmooth case.

The Bregman three-point identity: provides the algebraic identity that converts the dual step into a potential difference.

Positive Hessians make Bregman divergence nonnegative: provides the nonnegative potential terms used when telescoping.

Compactness makes the Bregman projection well-defined: establishes existence/uniqueness and the projection variational and Pythagorean inequalities.

Multivariable Taylor formula with a Lagrange remainder along a line segment: supplies the intermediate Hessian point $z_{t}$ on each update segment.

Facts & Assumptions

Given: The mirror regularizer, horizon, step size, iterates, update equations, loss conditions, and comparator in the Statement.

[A1]

At every round $x_{t}, x_{t + 1} \in K \cap U$ , $y_{t + 1} \in U$ , the agile gradient identity holds, and $x_{t + 1}$ minimizes $B_{R} (\cdot ∥ y_{t + 1})$ on $K$ .

[A2]

The initial point $x_{1} \in K \cap U$ minimizes $R$ on $K$ .

[A3]

At each round, either the differentiable convex gradient condition or the explicitly stated supporting-subgradient condition holds for every comparator in $K$ .

[A4]

$D_{R} > 0$ , $G_{R} > 0$ , and $∥ g_{t} ∥_{*, z_{t}} \leq G_{R}$ for every $t$ when the tuned corollaries are invoked.

[F1]

Mirror maps, Bregman divergence, and local Hessian norms: $B_{R} (a ∥ b) = R (a) - R (b) - ⟨ \nabla R (b), a - b ⟩$ ; for $z \in U$ , $H_{R} (z)$ is positive definite and $∥ v ∥_{z}^{2} = v^{⊤} H_{R} (z) v$ , $∥ h ∥_{*, z}^{2} = h^{⊤} H_{R} (z)^{- 1} h$ .

[F2]

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

[F3]

Positive Hessians make Bregman divergence nonnegative: $B_{R} (a ∥ b) \geq 0$ for $a, b \in U$ , and $B_{R} (a ∥ b) \geq \frac{m}{2} ∥ a - b ∥_{2}^{2}$ for $a \in K$ , $b \in K \cap U$ .

[F4]

Agile online mirror descent: $\nabla R (y_{t + 1}) = \nabla R (x_{t}) - η g_{t}$ and $x_{t + 1}$ is the Bregman minimizer.

[F5]

Compactness makes the Bregman projection well-defined: for every $u \in K$ , $B_{R} (u ∥ y_{t + 1}) \geq B_{R} (u ∥ x_{t + 1}) + B_{R} (x_{t + 1} ∥ y_{t + 1})$ .

[F6]

Differentiable convex functions are characterized by the gradient inequality: if $f_{t}$ is differentiable and convex on an open convex domain containing $K$ , then $f_{t} (x_{t}) - f_{t} (u) \leq ⟨ \nabla f_{t} (x_{t}), x_{t} - u ⟩$ .

[F7]

Subgradients and the subdifferential of a convex function: in the supplied-subgradient branch, $f_{t} (x_{t}) - f_{t} (u) \leq ⟨ g_{t}, x_{t} - u ⟩$ for every $u \in K$ by the stated supporting inequality.

[F8]

Multivariable Taylor formula with a Lagrange remainder along a line segment: for $R \in C^{2} (U)$ and $x_{t}, y_{t + 1} \in U$ , some $θ_{t} \in (0, 1)$ gives the second-order Taylor formula at $x_{t}$ along $y_{t + 1} - x_{t}$ .

[F9]

Static, dynamic, interval, and strongly adaptive regret: pointwise regret against $u$ is $\sum_{t} (f_{t} (x_{t}) - f_{t} (u))$ .

[F10]

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 $R^{d}$ are compact.

[F11]

Semicontinuous extreme value theorem on compact Euclidean sets: a continuous real-valued function on a nonempty compact Euclidean set attains both its minimum and maximum.

[F12]

A convex subset of $R^{m}$ contains every line segment between two of its points: for $x, y \in K$ and $s \in [0, 1]$ , $(1 - s) x + s y \in K$ .

[F13]

Convex and strictly convex functions on Euclidean convex sets: a loss is convex when its value on a segment is at most the corresponding affine combination of endpoint values.

[F14]

The Euclidean inner product $⟨ x, y ⟩ = \sum_{k < n} x_{k} y_{k}$ on $R^{n}$ : the Euclidean pairing is $⟨ v, w ⟩ = \sum_{i} v_{i} w_{i}$ and its norm is induced by that inner product.

[F15]

The Jacobian matrix of partial derivatives and the gradient in the scalar-valued case: $\nabla f_{t} (x_{t})$ is the standard-coordinate vector of partial derivatives.

Proof

1.1givenA3F6F7F13F15cases

In either loss case [F6] or [F7] gives $f_{t} (x_{t}) - f_{t} (u) \leq ⟨ g_{t}, x_{t} - u ⟩$ for every $u \in K$ ; the loss convexity convention is [F13], and gradients are the vectors in [F15].

1.2givenF1F8caseschoosealgebra

Apply [F8] to $R$ along the segment from $x_{t}$ to $y_{t + 1}$ . If $x_{t} \neq y_{t + 1}$ it gives $z_{t} = x_{t} + θ_{t} (y_{t + 1} - x_{t}) \in U$ and $B_{R} (y_{t + 1} ∥ x_{t}) = \frac{1}{2} (x_{t} - y_{t + 1})^{⊤} H_{R} (z_{t}) (x_{t} - y_{t + 1})$ ; if the two points coincide, choose $z_{t} = x_{t}$ and both sides are zero. Thus the stated intermediate-point identity holds.

1.3givenA1F1algebra

Put $d_{t} = x_{t} - y_{t + 1}$ . Expanding the two Bregman terms by [F1] gives $B_{R} (x_{t} ∥ y_{t + 1}) + B_{R} (y_{t + 1} ∥ x_{t}) = ⟨ \nabla R (x_{t}) - \nabla R (y_{t + 1}), d_{t} ⟩ = η ⟨ g_{t}, d_{t} ⟩$ by [A1].

1.4givenF1F10F11choosealgebra

By [F10], $K$ is compact; by [F1], $R$ is continuous there; hence [F11] gives $M = \max_{K} R$ and $m_{0} = \min_{K} R$ . Every difference $R (x) - R (y)$ is at most $M - m_{0}$ , and points attaining $M$ and $m_{0}$ attain this difference, so $D_{R}^{2} = M - m_{0}$ is finite and nonnegative.

2.1step 1.2step 1.3F1F14algebracases

Let $A = H_{R} (z_{t})$ , $a = ∥ g_{t} ∥_{*, z_{t}}$ , and $b = ∥ d_{t} ∥_{z_{t}}$ . For every real $λ$ , positive definiteness gives $0 \leq (d_{t} - λ A^{- 1} g_{t})^{⊤} A (d_{t} - λ A^{- 1} g_{t}) = b^{2} - 2 λ ⟨ g_{t}, d_{t} ⟩ + λ^{2} a^{2}$ , with the pairing from [F14]. If $a > 0$ , substitute $λ = ⟨ g_{t}, d_{t} ⟩ / a^{2}$ to get $⟨ g_{t}, d_{t} ⟩^{2} \leq a^{2} b^{2}$ ; if $a = 0$ , positive definiteness of $A^{- 1}$ forces $g_{t} = 0$ . In either case $⟨ g_{t}, d_{t} ⟩ \leq a b$ . By steps 1.2 and 1.3, $B_{R} (x_{t} ∥ y_{t + 1}) = η ⟨ g_{t}, d_{t} ⟩ - b^{2} / 2 \leq η a b - b^{2} / 2 \leq η^{2} a^{2} / 2$ , the last inequality following from $(b - η a)^{2} \geq 0$ .

3.1step 1.1step 2.1A1F2F3F4F5algebra

Use [F2] with $a = u$ , $b = x_{t}$ , and $c = y_{t + 1}$ , together with [A1], to write $η ⟨ g_{t}, x_{t} - u ⟩ = B_{R} (u ∥ x_{t}) - B_{R} (u ∥ y_{t + 1}) + B_{R} (x_{t} ∥ y_{t + 1})$ . Apply [F5] to the middle potential and [F3] to $B_{R} (x_{t + 1} ∥ y_{t + 1})$ ; then apply step 2.1. With step 1.1 this gives $η (f_{t} (x_{t}) - f_{t} (u)) \leq B_{R} (u ∥ x_{t}) - B_{R} (u ∥ x_{t + 1}) + \frac{η^{2}}{2} ∥ g_{t} ∥_{*, z_{t}}^{2}$ .

4.1step 3.1F3F9algebra

Sum step 3.1 over $t$ . The Bregman terms telescope, and [F3] gives $B_{R} (u ∥ x_{T + 1}) \geq 0$ because $u \in K$ and $x_{T + 1} \in K \cap U$ . Divide by $η > 0$ to obtain $R_{T} (u) \leq B_{R} (u ∥ x_{1}) / η + (η / 2) \sum_{t = 1}^{T} ∥ g_{t} ∥_{*, z_{t}}^{2}$ .

5.1givenA2F1F9F12step 4.1algebra

For fixed $u \in K$ , [F12] puts the segment $x_{1} + s (u - x_{1})$ in $K$ , and $R$ has a minimum at $s = 0$ . Since $x_{1} \in U$ , the right derivative is $⟨ \nabla R (x_{1}), u - x_{1} ⟩ \geq 0$ . The Bregman identity gives $R (u) - R (x_{1}) = B_{R} (u ∥ x_{1}) + ⟨ \nabla R (x_{1}), u - x_{1} ⟩ \geq B_{R} (u ∥ x_{1})$ . Substitute in step 4.1 to prove the pointwise bound.

6.1step 1.4step 5.1A4algebra∎

For every $u \in K$ , $R (u) - R (x_{1}) \leq D_{R}^{2}$ . Under [A4], step 5.1 gives $R_{T} (u) \leq D_{R}^{2} / η + η T G_{R}^{2} / 2$ . Substituting $η = D_{R} / (G_{R} \sqrt{T})$ gives $\frac{3}{2} D_{R} G_{R} \sqrt{T}$ . For arbitrary $η > 0$ , the difference between $D_{R}^{2} / η + η T G_{R}^{2} / 2$ and $\sqrt{2} D_{R} G_{R} \sqrt{T}$ is ${(D_{R} / \sqrt{η} - G_{R} \sqrt{T η / 2})}^{2} \geq 0$ . Equality holds when $D_{R}^{2} / η = η T G_{R}^{2} / 2$ , that is, $η = \sqrt{2} D_{R} / (G_{R} \sqrt{T})$ . This proves the optimized corrected bound.

Remarks

The unhalved initial potential and the $η / 2$ local-norm term are essential. The original planned $η / 4$ term and $[R (u) - R (x_{1})] / (2 η)$ initial term, together with its $D_{R} G_{R} \sqrt{T}$ corollary at $η = D_{R} / (G_{R} \sqrt{T})$ , are false. Their exact original clause and a complete admissible one-round refutation are preserved in fs-mirror-descent-halved-regret-constants. The corrected $\sqrt{2} D_{R} G_{R} \sqrt{T}$ optimized constant here is attained by that quadratic witness at $η = 1$ .

Remarks references

Halving both terms in the agile mirror-descent regret bound.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

66 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)
Francesco Orabona, Online Mirror Descent II: Regret and Mirror Version (standard reference, not scraped)