Per-round failure bound of Lemma G.26: P(G_tᶜ) ≤ D_θ{(t+1)^{-2} + (H_C/(t+1))^2}
ProvedG26G.Sharp.win_roundSetting. is a compact action set spanning , is a compact generator (), is the direction enumeration, and is a GIA-FTRL run of rounds (IsGIAFTRLRun) with cumulative loss estimate , run filtration , learning rate (gbeta) and magnitude constant (gB). The filtration used below is for and (Fx). The standing hypotheses Sharp hold: lies in the unit ball, , , is the unique minimizer of on , and the instance is sharp with modulus (H.sig): on . The corruption is bounded by : a.s. (IsCorruptedG). The projective body is and the cone body is ; , , and is the index of among the reference atoms (js).
Assume is surjective and . For (with , , , as in win_ok), let
be the good event of Lemma G.26 (Gev), where is the alive event of (G.523) on the window . Then
with (H.Dθ he) depending only on the instance.
The failure probability is split into reference errors on dyadic blocks (Lemma G.29), normalized negative crossings (Lemma G.28), and the contraction step on that compares with . This is the first estimate in (G.525). Summing it with weights gives the weighted failure bound of Lemma G.26.
Formalization Note Rounds are 0-based.
import Mathlib
import Definitions.Def_IAFTRL_LinEnv
import Definitions.Def_IAFTRL_GIAFTRL
import Definitions.Def_IAFTRL_G26_body
import Definitions.Def_IAFTRL_G26_run
import Definitions.Def_IAFTRL_G26_window
open MeasureTheory ProbabilityTheory Set IAFTRL Matrix J11
open G26G
open G26 G26R
variable {d : ℕ} {𝒜 ℬ : Set (Fin d → ℝ)} {e : ℕ → Fin d → ℚ} {θ astar : Fin d → ℝ}
variable {Ω : Type*} [mΩ : MeasurableSpace Ω] {P : Measure Ω} [IsProbabilityMeasure P]
{T : ℕ} {R : GRun d Ω}
open G26G.Sharp
variable (H : Sharp 𝒜 ℬ θ astar) (he : Function.Surjective e)
include H heomit he in
theorem G26G.Sharp.win_round (he : Function.Surjective e) (hR : IsGIAFTRLRun P 𝒜 ℬ e T R) {C : ℝ}
(hC : 0 ≤ C) (hcor : IsCorruptedG P 𝒜 θ C T R) {t : ℕ} (htT : t < T)
(ht0 : H.t0f he C ≤ t) :
P.real (Gev 𝒜 ℬ e (js ℬ e astar) R θ astar H.sig⁻¹ C (zw (mw (H.M0 he) (Hcf C) t) t) T
(mw (H.M0 he) (Hcf C) t) t)ᶜ ≤
H.Dθ he * (1 / ((t : ℝ) + 1) ^ 2 + (Hcf C / ((t : ℝ) + 1)) ^ 2) := by sorry