Lemma G.29 (corruption-uniform block bound for the reference)
ProvedG26G.Sharp.ref_blockSetting. 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. Let , an integer with , and let be an integer with , (H.Sref he) and
Then the probability that the penalized reference problem (3.4) fails to select strictly at some round of the block satisfies
where (goodS) says the atom of is the strict minimizer in (3.4), and (H.Dref he) depends only on the instance.
This is (G.622) of Lemma G.29 with and in the role of the corruption scale. Summed over dyadic blocks it gives the reference part of the alive-window failure probability in Lemma G.28.
Formalization Note Rounds are 0-based (block in run indices).
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 hetheorem G26G.Sharp.ref_block (hR : IsGIAFTRLRun P 𝒜 ℬ e T R) {C : ℝ} (hC : 0 ≤ C)
(hcor : IsCorruptedG P 𝒜 θ C T R) {u nC : ℕ} (hnC1 : 1 ≤ nC) (hCn : C ≤ nC)
(h2uT : 2 * u ≤ T) (hu : H.Sref he ≤ u)
(huC : 2 ^ 20 * (((nC : ℝ) + 1) * Real.log (Real.exp 1 * ((nC : ℝ) + 1))) ≤ (u : ℝ) + 1) :
P.real {ω | ∃ s, u ≤ s ∧ s ≤ 2 * u ∧ ¬ goodS ℬ e (js ℬ e astar) (s + 1) (R.cumEst s ω)} ≤
H.Dref he * ((((nC : ℝ) + 1) / ((u : ℝ) + 1)) ^ 4 + 1 / ((u : ℝ) + 1) ^ 4) := by sorry