Corollary 9 — on
ProvedEmpiricalBernstein.SVP.corollary_9concentrationinequalitiesp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be points of . Then
all sums running over .
This is Lemma 8 for uniformly distributed on the points ; it gives the self-boundedness of used in the proof of Theorem 10.
Formalization Note The paper writes ; the points form a list , so repetitions are allowed. The paper's index is Lean's k : Fin n. At both sides are .
Preamble
import Mathlib
Formal statement
namespace EmpiricalBernstein.SVP
/-- Corollary 9 (arXiv:0907.3740v1, p. 4), for a list `x_1, …, x_n` of points of `[0, 1]`. -/
theorem corollary_9 {n : ℕ} (x : Fin n → ℝ) (hx : ∀ i, x i ∈ Set.Icc (0 : ℝ) 1) :
(1 / (n : ℝ)) * ∑ k, ((1 / (n : ℝ)) * ∑ j, (x k - x j) ^ 2) ^ 2
≤ 1 / (2 * (n : ℝ) ^ 2) * ∑ k, ∑ j, (x k - x j) ^ 2 := by sorry
end EmpiricalBernstein.SVP
Source
Maurer, Pontil, Empirical Bernstein Bounds and Sample Variance Penalization, arXiv:0907.3740v1, Corollary 9, p. 4
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.