Lemma 12 — and are Lipschitz in with constants and
ProvedEmpiricalBernstein.SVP.lemma_12concentrationlipschitzp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let , and . Then
where and are the confidence-bound functionals of Section 3 and is the sup norm on .
These Lipschitz bounds let a finite sup-norm cover of the function class on the double sample stand in for the whole class in the proof of Theorem 6.
Formalization Note is Mathlib's norm on Fin n → ℝ, the sup norm. is added, as for every statement involving , (which contain in a denominator); the page leaves it implicit.
Preamble
import Mathlib import Definitions.Def_EmpiricalBernstein_SVP_PhiPsi
Formal statement
namespace EmpiricalBernstein.SVP
/-- Lemma 12 (arXiv:0907.3740v1, p. 5): Lipschitz properties of `Φ` and `Ψ` in the sup norm
`‖·‖` of `Fin n → ℝ`, for `n ≥ 2`. -/
theorem lemma_12 {n : ℕ} (hn : 2 ≤ n) (t : ℝ) (ht : 0 < t) (x x' : Fin n → ℝ)
(hx : ∀ i, x i ∈ Set.Icc (0 : ℝ) 1) (hx' : ∀ i, x' i ∈ Set.Icc (0 : ℝ) 1) :
Phi x t - Phi x' t ≤ (1 + 2 * Real.sqrt (t / n)) * ‖x - x'‖ ∧
Psi x t - Psi x' t ≤ (1 + 6 * Real.sqrt (t / n)) * ‖x - x'‖ := by sorry
end EmpiricalBernstein.SVP
Source
Maurer, Pontil, Empirical Bernstein Bounds and Sample Variance Penalization, arXiv:0907.3740v1, Lemma 12, p. 5
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.