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

Follow-the-Leader regret for bounded strongly convex losses

Statement

Let $d, N \geq 1$ be integers, let $K \subseteq R^{d}$ be nonempty and convex, and define $∥ x - y ∥_{2} = (\sum_{r = 1}^{d} (x_{r} - y_{r})^{2})^{1 / 2}$ . Let $G \geq 0$ and $μ > 0$ . For each $i = 1, \dots, N$ , let $L_{i} : K \to [0, 1]$ be $G$ -Lipschitz, meaning $∣ L_{i} (x) - L_{i} (y) ∣ \leq G ∥ x - y ∥_{2}$ , and $μ$ -strongly convex, meaning

$L_{i} ((1 - λ) x + λ y) \leq (1 - λ) L_{i} (x) + λ L_{i} (y) - \frac{μ}{2} λ (1 - λ) ∥ x - y ∥_{2}^{2}$

for all $x, y \in K$ and $λ \in [0, 1]$ . For $n = 1, \dots, N$ , assume $F_{n} : = \sum_{i = 1}^{n} L_{i}$ attains a minimum on $K$ . Let $θ_{1} \in K$ and, for $n = 1, \dots, N$ , let $θ_{n + 1}$ be the unique minimizer of $F_{n}$ . Define $H_{0} = 0$ and $H_{n} = \sum_{j = 1}^{n} 1 / j$ for $n \geq 1$ . Then

$\sum_{i = 1}^{N} L_{i} (θ_{i}) - \min_{θ \in K} \sum_{i = 1}^{N} L_{i} (θ) \leq 1 + \frac{4 G^{2}}{μ} H_{N - 1} .$

The minimizers are unique because $F_{n}$ is $n μ$ -strongly convex. The first policy $θ_{1}$ may be any supplied point of $K$ .

Statement references

Ross, Gordon, and Bagnell, A Reduction of Imitation Learning and Structured Prediction to No-Regret Online Learning: §4.1–4.2, PDF pp. 3–4, for the FTL/strongly-convex no-regret context.

Facts & Assumptions

Given: $K$ , $L_{1}, \dots, L_{N}$ , $G$ , $μ$ , the attained cumulative minimizers, and $θ_{1}$ as in the Statement.

[A1]

Each $L_{i}$ takes values in $[0, 1]$ , is $G$ -Lipschitz and $μ$ -strongly convex on the convex set $K$ , and each $F_{n}$ has an attained minimum.

Proof

technique · be-the-leader telescoping and a stability bound for consecutive minimizers

1.1givenA1algebra

Each $F_{n}$ is $n μ$ -strongly convex by summing the defining inequalities, so it has at most one minimizer; the assumed attainment therefore makes every $θ_{n + 1}$ well-defined and unique. For any comparator $v \in K$ , expand $L_{i} (θ_{i + 1}) = F_{i} (θ_{i + 1}) - F_{i - 1} (θ_{i + 1})$ and telescope to obtain $\sum_{i = 1}^{N} L_{i} (θ_{i + 1}) = F_{N} (θ_{N + 1}) + \sum_{i = 1}^{N - 1} (F_{i} (θ_{i + 1}) - F_{i} (θ_{i + 2})) \leq F_{N} (v)$ , because $θ_{i + 1}$ minimizes $F_{i}$ and $θ_{N + 1}$ minimizes $F_{N}$ .

2.1A1step 1.1algebra

For $i \geq 2$ , apply the midpoint strong-convexity inequality for $F_{i - 1}$ to $θ_{i}$ and $θ_{i + 1}$ . Since $θ_{i}$ minimizes $F_{i - 1}$ , this gives $\frac{(i - 1) μ}{4} ∥ θ_{i + 1} - θ_{i} ∥_{2}^{2} \leq F_{i - 1} (θ_{i + 1}) - F_{i - 1} (θ_{i})$ . Optimality of $θ_{i + 1}$ for $F_{i} = F_{i - 1} + L_{i}$ bounds the right side by $L_{i} (θ_{i}) - L_{i} (θ_{i + 1})$ , which is at most $G ∥ θ_{i + 1} - θ_{i} ∥_{2}$ by Lipschitz continuity. If the distance is zero the loss difference is zero; otherwise divide by it to obtain $L_{i} (θ_{i}) - L_{i} (θ_{i + 1}) \leq 4 G^{2} / ((i - 1) μ)$ .

3.1A1step 1.1step 2.1algebra∎

The first difference satisfies $L_{1} (θ_{1}) - L_{1} (θ_{2}) \leq 1$ because both values lie in $[0, 1]$ . Summing this with the bounds from step 2.1 yields $\sum_{i = 1}^{N} (L_{i} (θ_{i}) - L_{i} (θ_{i + 1})) \leq 1 + \frac{4 G^{2}}{μ} H_{N - 1}$ . For a minimizer $v$ of $F_{N}$ , step 1.1 gives $\sum_{i} L_{i} (θ_{i + 1}) \leq F_{N} (v)$ ; adding that inequality proves the Statement.

Used by

Dependency tree · 0 levels

Nothing. This result depends on no other item in the library.

Sources

Stéphane Ross, Geoffrey J. Gordon, and J. Andrew Bagnell, A Reduction of Imitation Learning and Structured Prediction to No-Regret Online Learning (standard reference, not scraped)