Preparation before a reference block: probability that the remaining-budget field crosses its buffer
ProvedG26G.Sharp.prep_probSetting. 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).
Let , let be nondecreasing, , , and . Write with (kk d), (cK d) for the absolute-envelope constant, and for the event that the remaining-budget field of Lemma G.30 satisfies for all . Then
The first term is Markov's inequality for the absolute envelope of ; the second applies the crossing envelope from the start , where the negative moment of is bounded by its absolute moment plus the shift . This is the event that the block argument of Lemma G.29 must exclude before using the per-action variables.
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)
include H
variable (he : Function.Surjective e)
include hetheorem G26G.Sharp.prep_prob (hR : IsGIAFTRLRun P 𝒜 ℬ e T R) {C : ℝ} (hC : 0 ≤ C)
(hcor : IsCorruptedG P 𝒜 θ C T R) {τ : ℕ → ℝ} (hτmono : ∀ n, τ n ≤ τ (n + 1))
{m0 N nC : ℕ} (hN : N ≤ T) (hnN : nC ≤ N) (hτ1 : 1 ≤ τ m0) {ρ : ℝ} (hρτ : τ m0 ≤ ρ)
(hρC : 4 * C ≤ ρ) :
P.real (IW 𝒜 ℬ R θ astar C τ m0 N)ᶜ ≤
2 ^ (4 * kk d) * cK d * ((N : ℝ) + 1) ^ (4 * kk d) / ρ ^ (4 * kk d) +
2 ^ (4 * kk d) * 4 ^ d * (ρ / τ m0) ^ d / τ m0 ^ (4 * kk d) *
(Hneg (kk d) (16 * d + 1) (gB d) * ((N : ℝ) + 1) ^ (3 * kk d) +
(((N : ℝ) + 1) / ((nC : ℝ) + 1)) ^ (d + 2) *
(2 ^ (4 * kk d) * (cK d * ((nC : ℝ) + 1) ^ (4 * kk d) + (2 * C) ^ (4 * kk d)))) := by sorry