Lemma 22 — Ĝ_n(F) ≤ (2B/n)√(Σ k(X_i, X_i)) and R̂_n(F) ≤ (2B/n)√(Σ k(X_i, X_i)) for the kernel class
ProvedRadGauss.Kernel.lemma_22gaussian-complexitykernel-methodslearning-theoryp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1rademacher-complexity
Let be a kernel on a compact space , let , and let be the class of kernel expansions with . Then for every and every sample , the empirical Gaussian and Rademacher complexities of satisfy
The bound depends on the sample only through the trace of its Gram matrix, so it holds for every realization of random elements and requires no bound on the kernel beyond its values at the sample points.
Formalization Note The statement is sample-wise: it holds for every . Complexities are those of Definition 2 with values in , the right-hand side is embedded by ENNReal.ofReal. The paper takes ; here . At both sides are ( in Lean), so no hypothesis is needed.
Preamble
import Mathlib import Definitions.Def_RadGauss_Kernel_Complexity import Definitions.Def_RadGauss_Kernel_KernelClass
Formal statement
namespace RadGauss.Kernel
/-- Lemma 22 (Bartlett–Mendelson 2002, p. 477). Let `k` be a kernel on `𝒳`, `B ≥ 0`, and let
`F = kernelClass k B`. For every sample `x_1, …, x_n ∈ 𝒳`,
`Ĝ_n(F) ≤ (2B/n) √(Σ_i k(x_i, x_i))` and `R̂_n(F) ≤ (2B/n) √(Σ_i k(x_i, x_i))`.
The paper takes `B > 0`; `0 ≤ B` is assumed here. At `n = 0` both sides are `0`. -/
theorem lemma_22 {X : Type*} [TopologicalSpace X] (k : X → X → ℝ) (hk : IsKernel k)
(B : ℝ) (hB : 0 ≤ B) (n : ℕ) (x : Fin n → X) :
empiricalGaussian (kernelClass k B) n x
≤ ENNReal.ofReal (2 * B / n * Real.sqrt (∑ i, k (x i) (x i))) ∧
RadGauss.Classification.empiricalRademacher (kernelClass k B) n x
≤ ENNReal.ofReal (2 * B / n * Real.sqrt (∑ i, k (x i) (x i))) := by sorry
end RadGauss.Kernel
Source
Bartlett, Mendelson, Rademacher and Gaussian Complexities: Risk Bounds and Structural Results, J. Mach. Learn. Res. 3 (2002), p. 477 (PDF p. 15), Lemma 22
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.