§4.3, p. 477 — ‖Σ α_iΦ(x_i)‖² = Σ α_iα_j k(x_i, x_j), hence F ⊆ {x ↦ ⟨w, Φ(x)⟩ : ‖w‖ ≤ B}
ProvedRadGauss.Kernel.feature_map_inclusionkernel-methodslearning-theoryp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a kernel on a compact space , and let be a feature map of : is a real Hilbert space with inner product and norm , and for all . Let and let be the class of kernel expansions with . Then
- for every , all and all ,
- consequently
The inclusion places the kernel class inside a ball of linear functionals of the feature map, which is how its complexity is bounded in Lemma 22.
Formalization Note The feature map is a hypothesis (any real Hilbert space and any with ); its existence for every kernel is the cited RKHS theorem, available on the platform as FoundationsML.Kernels.RKHS_exists. The paper takes ; here (for the right-hand set is empty while contains the zero function, so a sign condition is needed).
Preamble
import Mathlib import Definitions.Def_RadGauss_Kernel_KernelClass
Formal statement
namespace RadGauss.Kernel
/-- §4.3, p. 477 (Bartlett–Mendelson 2002), the feature-map displays. Let `k` be a kernel on `𝒳`
with feature map `Φ : 𝒳 → ℋ` into a real Hilbert space, `k(x₁, x₂) = ⟨Φ(x₁), Φ(x₂)⟩`. Then
`‖Σ_i α_i Φ(x_i)‖² = Σ_{i,j} α_i α_j k(x_i, x_j)` for every finite family, and hence, for `B ≥ 0`,
`F ⊆ {x ↦ ⟨w, Φ(x)⟩ : ‖w‖ ≤ B}`. The paper takes `B > 0`; `0 ≤ B` is assumed here. -/
theorem feature_map_inclusion {X H : Type*} [TopologicalSpace X]
[NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H]
(k : X → X → ℝ) (hk : IsKernel k) (Φ : X → H)
(hΦ : ∀ x₁ x₂, k x₁ x₂ = inner ℝ (Φ x₁) (Φ x₂)) (B : ℝ) (hB : 0 ≤ B) :
(∀ (m : ℕ) (x : Fin m → X) (α : Fin m → ℝ),
‖∑ i, α i • Φ (x i)‖ ^ 2 = ∑ i, ∑ j, α i * α j * k (x i) (x j)) ∧
kernelClass k B ⊆ {f | ∃ w : H, ‖w‖ ≤ B ∧ f = fun x => inner ℝ w (Φ x)} := 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), §4.3, first and second displays
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.