Theorem 3.3 — CBA average regret (corrected: constant ; projected onto )
ProvedConicBlackwell.theorem_3_3blackwell-approachabilityconic-optimizationonline-convex-optimizationp2o-correctedp2o-gran-per-chapterp2o-plan-paperp2o-v1regret-minimization
Let be a nonempty convex compact set, , and . Let be generated by CBA (Algorithm 1) with aggregate payoff weights on the losses , and measure regret with decision weights ; write . Assume the weights are positive and
and let bound the losses, for . Then for every
With uniform payoff weights and linearly increasing decision weights (, ) the right-hand side is , so CBA is a no-regret algorithm compatible with weighted averaging of the decisions, the regime in which it performs best in practice.
The page prints the constant , which is false: for , , , , the left side is while . The constant is attained on that instance.
Differences from the source:
- correction: constant √2 κL → constant 2 κL; reason: X = [−1, 1], θ = ω = 1, T = 1, x₁ = 1, f₁ = 1: the left side is 2 and √2κL = √2; the proof's ‖v_t‖₂ ≤ L (p.10) holds only as ‖v_t‖₂ ≤ √2‖f_t‖₂, which gives √2κ · √2L = 2κL
- correction: Algorithm 1 line 4: u₁ = ω₁(⟨f₁, x₁⟩/κ, −f₁) (no projection) → u₀ = 0 and u₁ = π_C(ω₁v₁), the UPDATEPAYOFF rule applied to u₀ = 0; reason: the printed u₁ can leave C, contradicting 'we always have u ∈ C' (p.5): X = [−1, 1], x₁ = 1/10, f₁ = 1, f₂ = −1, ω = 1 gives u₁ = (1/10, −1) ∉ C and x₂ = −10 ∉ X; the two agree whenever ω₁v₁ ∈ C
- reading: weights (ω_t), (θ_t) → 0 < ω t and 0 < θ t for t ≥ 1; reason: weights are positive; the ratios θ_{t+1}/θ_t, ω_{t+1}/ω_t and θ_T/ω_T in the statement presuppose it
- encoding: (4): ‖f‖ ≤ L for every (sub)gradient → ‖f t‖ ≤ L for 1 ≤ t ≤ T; reason: for a single regret minimizer, (4) bounds exactly the observed losses f_1, …, f_T
- encoding: ℝⁿ and ℝ × ℝⁿ = ℝⁿ⁺¹ → E n = EuclideanSpace ℝ (Fin n), and lift a x : E (n+1) with the scalar a in coordinate 0; reason: Lean convention of the reused ApproachRegret.ToOLO definitions; same instances (the dimension n = 0 is not excluded; there X ⊆ {0} and the statements stay true)
- encoding: κ = max_{x∈X} ‖x‖₂ and v_t = (⟨f_t, x_t⟩/κ, −f_t) → kappa X = sSup of ‖x‖ over X, and payoff X x f = lift (⟪f, x⟫ / kappa X) (−f) with Lean's x/0 = 0; reason: sSup is the max on a nonempty compact X; κ = 0 only when X = {0}, where the page's ⟨f,x⟩/κ is undefined and both coordinates conventions give the same statement
- encoding: min_{x∈X} Σ_{t=1}^T θ_t⟨f_t, x⟩ → sInf of the image of X (weightedRegret); reason: a continuous function on a nonempty compact X attains its infimum
- encoding: rounds t ≥ 1 of Algorithm 1 → sequences ℕ → ·, with rounds t ∈ Finset.Icc 1 T; values at index 0 unused (u 0 = 0 is the start of the run); reason: Lean convention; same instances
- encoding: π_C(u), the nearest point of C = cone({κ} × X) to u (UPDATEPAYOFF_{CBA+}, p.5) → PerspEpi.projC C u, the unique nearest point if there is one and u otherwise; reason: C is nonempty, closed and convex for nonempty compact convex X (κ > 0: the base {κ} × X is compact and misses 0; κ = 0: X = {0}, C = {0}), so the nearest point exists and is unique and the fallback is never taken
- encoding: x₀ ∈ X 'arbitrary' in CHOOSEDECISION (p.5) → x₀ a universally quantified parameter with x₀ ∈ X; reason: the bound holds for every choice
- encoding: an adversary choosing f_{t+1} after seeing x_{t+1} → an arbitrary fixed loss sequence f : ℕ → ℝⁿ; reason: CBA+ is deterministic, so the bound for every sequence covers adaptive adversaries
Preamble
import Mathlib import Definitions.Def_ApproachRegret_ToOLO_AlgorithmOne import Definitions.Def_ConicBlackwell_cbaPlusU import Definitions.Def_ConicBlackwell_cbaPlusX import Definitions.Def_ConicBlackwell_weightedRegret open scoped RealInnerProductSpace open ApproachRegret.ToOLO
Formal statement
namespace ConicBlackwell
/-- **Theorem 3.3**, Grand-Clément & Kroer, arXiv:2202.12277v1, p.8, **corrected constant**.
Consider `(x_t)_{t≥1}` generated by CBA+ with aggregate payoff weights `(ω_t)_{t≥1}`, when regret is
measured using decision weights `(θ_t)_{t≥1}`, and `S_T = Σ_{t=1}^T θ_t`. Assume that
`θ_{t+1}/θ_t ≥ ω_{t+1}/ω_t` for all `t ≥ 1`. Then
`(Σ_{t=1}^T θ_t⟨f_t, x_t⟩ − min_{x∈X} Σ_{t=1}^T θ_t⟨f_t, x⟩)/S_T
≤ 2 κ L (θ_T/ω_T) √(Σ_{t=1}^T ω_t²) / Σ_{t=1}^T θ_t`.
The page prints the constant `√2 κ L`, which is false: on `X = [−1, 1]`, `θ = ω = 1`, `T = 1`,
`x₁ = 1`, `f₁ = 1`, the left side is `2` and `√2 κ L = √2`. The proof's `‖v_t‖₂ ≤ L` holds only
up to a factor `√2` (`‖v_t‖₂ ≤ √2 ‖f_t‖₂`), which gives `√2 κ · √2 L = 2 κ L`.
Formalization Note: `X ⊂ ℝⁿ` nonempty, convex, compact; `κ = kappa X`; `L` bounds `‖f_t‖₂` for
`1 ≤ t ≤ T` (the paper's (4)); weights are positive; rounds are numbered from `1`; the min over
`X` is `sInf` (`weightedRegret`); the run starts from `u₀ = 0`, so `u₁ = π_C(ω₁ v₁)` (Algorithm 1
line 4 prints `u₁ = ω₁ v₁`, which can leave `C`). -/
theorem theorem_3_3 {n : ℕ} (X : Set (E n)) (hXne : X.Nonempty) (hXc : IsCompact X) (hXcv : Convex ℝ X)
(x₀ x₁ : E n) (hx₀ : x₀ ∈ X) (hx₁ : x₁ ∈ X)
(ω θ : ℕ → ℝ) (hω : ∀ t, 1 ≤ t → 0 < ω t) (hθ : ∀ t, 1 ≤ t → 0 < θ t)
(hratio : ∀ t, 1 ≤ t → ω (t + 1) / ω t ≤ θ (t + 1) / θ t)
(f : ℕ → E n) (L : ℝ) (T : ℕ) (hT : 1 ≤ T) (hf : ∀ t ∈ Finset.Icc 1 T, ‖f t‖ ≤ L) :
weightedRegret X θ f (cbaPlusX X x₀ x₁ ω f) T / (∑ t ∈ Finset.Icc 1 T, θ t) ≤
2 * kappa X * L * (θ T / ω T) * Real.sqrt (∑ t ∈ Finset.Icc 1 T, ω t ^ 2) /
(∑ t ∈ Finset.Icc 1 T, θ t) := by sorry
end ConicBlackwell
Source
Grand-Clément & Kroer, Solving Optimization Problems with Blackwell Approachability, arXiv:2202.12277v1 (https://arxiv.org/abs/2202.12277v1), Theorem 3.3, p.8 (proof pp.9–10)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.