False statementConstruction: AI-adaptedVerification: AI-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.

Halving both terms in the agile mirror-descent regret bound

Statement

Let $d \geq 1$ , let $K \subseteq R^{d}$ be nonempty, bounded, closed and convex with nonempty interior, and let $U$ be an open convex set containing $int K$ , with $K \subseteq \overline{U}$ . Let $R$ be continuous on $K$ , twice continuously differentiable with positive-definite Hessian on $U$ , and strongly convex on $K$ . Initialize $x_{1} \in K \cap U$ at a minimizer of $R$ on $K$ . For an integer $T \geq 1$ and a constant $η > 0$ , run the well-defined agile update $\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}),$ with $x_{t}, x_{t + 1} \in K \cap U$ , $y_{t + 1} \in U$ , and $g_{t} = \nabla f_{t} (x_{t})$ for differentiable convex losses on an open convex neighborhood of $K$ . Define $B_{R} (x ∥ y) = R (x) - R (y) - ⟨ \nabla R (y), x - y ⟩$ . For each $t$ , choose an intermediate point $z_{t} \in [x_{t}, y_{t + 1}]$ satisfying $2 B_{R} (y_{t + 1} ∥ x_{t}) = (x_{t} - y_{t + 1})^{⊤} \nabla^{2} R (z_{t}) (x_{t} - y_{t + 1})$ and put $∥ g_{t} ∥_{*, t}^{2} = g_{t}^{⊤} [\nabla^{2} R (z_{t})]^{- 1} g_{t}$ .

The following two assertions hold for every comparator $u \in K$ :

The pointwise regret $R_{T} (u) = \sum_{t = 1}^{T} (f_{t} (x_{t}) - f_{t} (u))$ satisfies $R_{T} (u) \leq \frac{η}{4} \sum_{t = 1}^{T} ∥ g_{t} ∥_{*, t}^{2} + \frac{R (u) - R (x_{1})}{2 η} .$
If $D_{R}^{2} = \max_{x, y \in K} (R (x) - R (y))$ , $D_{R} = \sqrt{D_{R}^{2}} > 0$ , and $G_{R} > 0$ bounds $∥ g_{t} ∥_{*, t}$ , then the choice $η = D_{R} / (G_{R} \sqrt{T})$ gives $R_{T} (u) \leq D_{R} G_{R} \sqrt{T} .$

Statement references

Agile mirror descent and its well-defined update conditions

Bregman divergence and local Hessian norms

Hazan, Theorem 5.6 and displayed proof, PDF pages 101–103

Facts & Assumptions

Given: The two universal assertions and all their hypotheses in the Statement.

[F1]

Agile online mirror descent: the initial decision minimizes $R$ on $K$ ; the agile step solves $\nabla R (y) = \nabla R (x) - η g$ and then minimizes $B_{R} (\cdot ∥ y)$ over $K$ .

[F2]

Mirror maps, Bregman divergence, and local Hessian norms: the oriented divergence is $R (x) - R (y) - ⟨ \nabla R (y), x - y ⟩$ , and the local dual squared norm is $g^{⊤} [\nabla^{2} R (z)]^{- 1} g$ .

Refutation

1.1givenconstructalgebra

Set $d = T = 1$ , $K = [0, 1]$ , $U = R$ , $R (x) = x^{2} / 2$ , $x_{1} = 0$ , $f_{1} (x) = - x$ , $g_{1} = - 1$ , and comparator $u = 1$ . The interval is nonempty, bounded, closed and convex with nonempty interior; $U$ is open and convex. The regularizer is continuous and $C^{2}$ on $R$ , with Hessian $1$ . The identity $R ((1 - λ) x + λ y) = (1 - λ) R (x) + λ R (y) - λ (1 - λ) (x - y)^{2} / 2$ proves $1$ -strong convexity, and $0$ uniquely minimizes $R$ on $K$ . The loss is differentiable and affine, hence convex, with gradient $- 1$ everywhere. All regularizer, initialization and loss hypotheses hold.

2.1step 1.1F1F2algebra

For any $0 < η \leq 1$ , [F1] gives $y_{2} = η$ , since $\nabla R (x) = x$ . By [F2], $B_{R} (x ∥ y) = (x - y)^{2} / 2$ , which has its unique minimum on $K$ at $x_{2} = y_{2} = η$ . Thus every update is well-defined and the required iterates lie in $K \cap U$ . Also $2 B_{R} (y_{2} ∥ x_{1}) = η^{2} = (x_{1} - y_{2})^{2} \nabla^{2} R (z)$ for every $z$ on the segment, and $∥ g_{1} ∥_{*, 1} = 1$ . Taking $G_{R} = 1$ is admissible.

3.1step 1.1step 2.1algebra

The one-round regret against $u = 1$ is $f_{1} (0) - f_{1} (1) = 1$ , independently of the internal post-round iterate. At $η = 1$ , the first assertion's right side is $1 / 4 + (R (1) - R (0)) / 2 = 1 / 4 + 1 / 4 = 1 / 2$ . Thus its claimed inequality would be $1 \leq 1 / 2$ , which is false.

3.2step 1.1step 2.1algebra

The maximum difference of regularizer values on $[0, 1]$ is $R (1) - R (0) = 1 / 2$ , so $D_{R} = 1 / \sqrt{2}$ . The second assertion's prescribed step is $η = D_{R} / (G_{R} \sqrt{T}) = 1 / \sqrt{2}$ , which belongs to $(0, 1]$ and therefore gives a valid trajectory by step 2.1. Its claimed regret bound is $D_{R} G_{R} \sqrt{T} = 1 / \sqrt{2} < 1$ , whereas the regret is still $1$ . This separately refutes the tuned assertion.

4.1step 3.1step 3.2algebra∎

Both original conclusions fail under their stated hypotheses. The same witness also shows sharpness of the corrected constants: at $η = 1$ the unhalved potential bound is $(R (1) - R (0)) / η + (η / 2) ∥ g_{1} ∥_{*, 1}^{2} = 1$ , and the optimized corrected expression $\sqrt{2} D_{R} G_{R} \sqrt{T}$ is also $1$ . Thus retaining the full correct bound resolves the false constants without losing the comparator, local-norm or optimized-rate conclusions.

Remarks

The original canonical ML-67 clause is retained verbatim in the repair packet's original-false-clause.md, with its exact substring hash and controlling-plan source recorded in original-clause-record.json. The local positive theorem supplies a complete proof with the initial term divided by $η$ and the accumulated local-norm term multiplied by $η / 2$ . At the original prescribed step its valid rate is $3 D_{R} G_{R} \sqrt{T} / 2$ ; optimizing gives $\sqrt{2} D_{R} G_{R} \sqrt{T}$ . This refutation does not alter any update rule or assert an AdaGrad convergence rate.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

14 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, Theorem 5.6 and full displayed proof (standard reference, not scraped)
Peter Bartlett, Stat 260/CS 294-102: Learning in Sequential Decision Problems, mirror-descent lecture notes, slides 28–30 (standard reference, not scraped)