(31), p. 16 β Sanov's lower bound: βinf_{int π} B(D, D_tr) β€ liminf (1/n) log D^β_tr[D_bs[n] β π]
ProvedBootRobust.Optimality.eq_31_sanov_lowerLet have all coordinates positive, let be any set, and let lie in the interior of relative to . Then for every , for all sufficiently large ,
where is the law of independent draws from and is their empirical distribution.
Holding for every and every , this is Sanov's lower bound (31) on a finite alphabet:
It shows that the bootstrap inequality of Theorem 6 is exact in the exponential rate.
Formalization Note The pointwise form with an explicit is equivalent to (31) and avoids . Since , is finite and is used as a real number. Only the first coordinates of the infinite bootstrap process enter the event, so its law is the -fold product. Full support of is the paper's convention that is the support of the training data.
import Mathlib import Definitions.Def_BootRobust_Optimality_Setting
namespace BootRobust.Optimality
open MeasureTheory
/-- Sanov's lower bound, Eq. (31), p. 16, in pointwise form: for every set `C`, every `D` in the
interior of `C` relative to `πβ` and every `Ξ΅ > 0`, eventually in `n`,
`DβΏ_tr(D_bs[n] β C) β₯ exp(-n (B(D, D_tr) + Ξ΅))`. Over all such `D` this is
`-inf_{D β int C} B(D, D_tr) β€ liminf (1/n) log D^β_tr[D_bs[n] β C]`. The training distribution has
full support, so `B(D, D_tr)` is finite and `EReal.toReal` returns its value. -/
theorem eq_31_sanov_lower {ΞΉ : Type*} [Fintype ΞΉ] [DecidableEq ΞΉ]
[MeasurableSpace ΞΉ] [MeasurableSingletonClass ΞΉ]
(Dtr : ΞΉ β β) (hDtr : Dtr β stdSimplex β ΞΉ) (hDtrpos : β i, 0 < Dtr i)
(C : Set (ΞΉ β β)) (D : ΞΉ β β) (hDC : D β relInt C) :
β Ξ΅ : β, 0 < Ξ΅ β βαΆ n : β in Filter.atTop,
ENNReal.ofReal (Real.exp (-((n : β) * ((BootRobust.Perf.bootDist D Dtr).toReal + Ξ΅)))) β€
bootLaw Dtr n {Ο | empDist Ο β C} := by sorry
end BootRobust.Optimality
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.