Theorem 6.11 — representer theorem (goal; corrected: a minimizer of the representer form exists whenever a minimizer exists)
ProvedFoundationsML.Kernels.representer_theorem_v2Statement (Theorem 6.11, p. 117, PDF p. 134; corrected form). Let be a PDS kernel and its corresponding RKHS. Then, for any non-decreasing function and any loss function , the optimization problem
admits, whenever it admits a solution at all, a solution of the form . If is further assumed to be increasing and is finite at some point, then any solution has this form.
Formalization Note. The retired version asserted unconditionally that a minimizer of the representer form exists, which is false: with and a linear loss has no minimizer at all (the accepted disproof). This is an error in the printed statement, not in the proof: the proof shows only that for every its projection onto satisfies (and when is increasing and ), so the printed "admits a solution of the form" tacitly assumes the argmin is nonempty. The standard corrected reading is formalized: existence of some minimizer implies existence of one of the representer form. The second clause keeps the finiteness hypothesis , now placed where it is needed (for every minimizes , so the clause would be false without it). 's codomain is WithTop ℝ; is (Theorem 6.8's construction, with ev h x = ⟨h, Φ x⟩); non-decreasing/increasing are Monotone/StrictMono.
import Mathlib import Definitions.Def_FoundationsML_Kernels_IsPDS import Definitions.Def_FoundationsML_Kernels_IsRKHSOf import Definitions.Def_FoundationsML_Kernels_IsMinimizer
namespace FoundationsML.Kernels
/-- Theorem 6.11 (Representer theorem; goal; Mohri, Rostamizadeh & Talwalkar, *Foundations of
Machine Learning*, 2nd ed., MIT Press 2018, p. 117, PDF p. 134), in its corrected form. Let
`K : X × X → ℝ` be a PDS kernel and `H` its corresponding RKHS. Then, for any non-decreasing
function `G : ℝ → ℝ` and any loss function `L : ℝ^m → ℝ ∪ {+∞}`, the optimization problem
`argmin_{h∈H} F(h) = argmin_{h∈H} G(‖h‖_H) + L(h(x_1),…,h(x_m))`, whenever it admits a
solution, admits a solution of the form `h* = ∑_{i=1}^m α_i K(x_i,·)`. If `G` is further
assumed to be increasing and `F` is finite somewhere, then any solution has this form.
**Formalization Note.** Replaces `representer_theorem`, whose first clause asserted
unconditionally that a minimizer of the stated form exists, which is false (disproved with
`G ≡ 0` and a linear loss, where `F` has no minimizer at all). The book's proof shows only
that for every `h` the projection `h_1` of `h` onto `span{K(x_i,·)}` satisfies `F(h_1) ≤ F(h)`
(and `F(h_1) < F(h)` when `G` is increasing and `h ∉ span`), so the printed "admits a
solution of the form" tacitly assumes the argmin is nonempty; this is the standard corrected
reading and is what is formalized: existence of some minimizer implies existence of one of
the representer form. The second clause keeps the finiteness hypothesis `∃ h₀, F h₀ ≠ ⊤`
(now placed where it is needed): for `L ≡ +∞` every `h` minimizes `F ≡ ⊤`, so the clause
would be false without it. `L`'s codomain `ℝ ∪ {+∞}` is `WithTop ℝ`; `K(x_i,·)` is `Φ (x i)`
(Theorem 6.8's construction); non-decreasing/increasing are `Monotone`/`StrictMono`. -/
theorem representer_theorem_v2
{X H : Type*} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H]
(K : X → X → ℝ) (hK : IsPDS K) (Φ : X → H) (ev : H → X → ℝ)
(hRKHS : IsRKHSOf K Φ ev)
(m : ℕ) (x : Fin m → X)
(G : ℝ → ℝ) (hG : Monotone G)
(L : (Fin m → ℝ) → WithTop ℝ)
(F : H → WithTop ℝ) (hF : ∀ h : H, F h = (G ‖h‖ : WithTop ℝ) + L (fun i => ev h (x i))) :
((∃ h : H, IsMinimizer F h) → ∃ α : Fin m → ℝ, IsMinimizer F (∑ i, α i • Φ (x i))) ∧
(StrictMono G → (∃ h₀ : H, F h₀ ≠ ⊤) →
∀ h : H, IsMinimizer F h → ∃ α : Fin m → ℝ, h = ∑ i, α i • Φ (x i)) := by sorry
end FoundationsML.Kernels
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.