Theorem 4 — margin-based generalization bound for the SPO loss under the strength property ( case)
ProvedSPOBounds.Margin.margin_generalization_boundWork in the set-up: decisions in with the Euclidean norm, cost vectors with its dual (again Euclidean) norm. Let be nonempty, compact, convex and not a singleton, any optimization oracle for , and suppose satisfies the strength property with parameter . Fix . Let be a probability distribution on feature–cost pairs whose cost lies almost surely in a nonempty bounded set , and let be a class of functions from to . Then for every and every , with probability at least over an i.i.d. sample from , every satisfies
Here is the SPO risk, the empirical -margin SPO risk, the expected multivariate Rademacher complexity, and .
This is the paper's margin-based generalization bound: the complexity term is the multivariate Rademacher complexity of , which for common classes grows mildly in the dimensions, at the price of the empirical margin loss in place of the empirical SPO loss.
Formalization Note "With probability at least " is stated as: the (outer) measure under of the samples on which some violates the bound is at most . The cost space carries the Borel -algebra. The paper is silent on measurability; added hypotheses are that every and its SPO loss are measurable, that the uniform deviation and the margin Rademacher suprema are a.e.-measurable in the sample, and that the multivariate Rademacher sums are almost surely bounded above and is integrable over samples, so that is the paper's expectation (when it is infinite the bound is vacuous).
import Mathlib import Definitions.Def_SPOBounds_Margin_Model import Definitions.Def_SPOBounds_Margin_Degeneracy import Definitions.Def_SPOBounds_Margin_Rademacher open MeasureTheory
namespace SPOBounds.Margin
/-- **Theorem 4, second display** (arXiv:1905.11488v3, pp. 19–20). ℓ₂ set-up: `E = ℝ^d` with the
Euclidean norm, costs and predictions in its dual (operator norm = Euclidean norm), with the Borel
σ-algebra. Let `S` be nonempty, compact, convex and not a singleton, `w` any oracle, and suppose
`S` satisfies the strength property with parameter `μ > 0`. Fix `γ > 0`, a nonempty bounded set
`C` containing the cost vector almost surely, and any `δ > 0`. Then with probability at least
`1 − δ` over an i.i.d. sample of size `n` from `D`, every `f ∈ H` satisfies
`R_SPO(f) ≤ R̂^γ_SPO(f) + ((2√2 ρ₂(C) + 2√2 μ ω_S(C)) / (γ μ)) ℜⁿ(H) + ω_S(C) √(log(1/δ) / (2n))`.
Stated as: the (outer) `Dⁿ`-measure of the samples on which some `f ∈ H` violates the bound is at
most `δ`. Added hypotheses (the paper is silent): measurability of each `f ∈ H` and of its SPO
loss (`hf`, `hℓ`), of the uniform deviation and of the margin Rademacher sups (`hΦ`, `hA`); and
almost-sure boundedness plus integrability of the multivariate empirical Rademacher complexity
(`hBdd`, `hInt`), without which `ℜⁿ(H)` is not the paper's quantity. -/
theorem margin_generalization_bound {d : ℕ} {X : Type*} [MeasurableSpace X]
[MeasurableSpace (StrongDual ℝ (EuclideanSpace ℝ (Fin d)))]
[BorelSpace (StrongDual ℝ (EuclideanSpace ℝ (Fin d)))]
(S : Set (EuclideanSpace ℝ (Fin d))) (hS : S.Nonempty) (hSc : IsCompact S)
(hSv : Convex ℝ S) (hSnt : S.Nontrivial)
(w : StrongDual ℝ (EuclideanSpace ℝ (Fin d)) → EuclideanSpace ℝ (Fin d)) (hw : IsOracle S w)
(μ : ℝ) (hμ : 0 < μ) (hstr : StrengthProperty S μ w)
(γ : ℝ) (hγ : 0 < γ)
(C : Set (StrongDual ℝ (EuclideanSpace ℝ (Fin d)))) (hC : C.Nonempty)
(hCb : Bornology.IsBounded C)
(D : Measure (X × StrongDual ℝ (EuclideanSpace ℝ (Fin d)))) [IsProbabilityMeasure D]
(hDC : ∀ᵐ z ∂D, z.2 ∈ C)
(H : Set (X → StrongDual ℝ (EuclideanSpace ℝ (Fin d))))
(hf : ∀ f ∈ H, Measurable f)
(hℓ : ∀ f ∈ H,
Measurable (fun z : X × StrongDual ℝ (EuclideanSpace ℝ (Fin d)) => spoLoss w (f z.1) z.2))
(n : ℕ) (hn : 0 < n)
(hΦ : AEMeasurable
(fun s : Fin n → X × StrongDual ℝ (EuclideanSpace ℝ (Fin d)) =>
marginSupDeviation S w γ D H s)
(Measure.pi fun _ : Fin n => D))
(hA : ∀ σ : Fin n → Bool,
AEMeasurable
(fun s : Fin n → X × StrongDual ℝ (EuclideanSpace ℝ (Fin d)) =>
marginSignedSup S w γ H σ s)
(Measure.pi fun _ : Fin n => D))
(hBdd : ∀ᵐ s ∂(Measure.pi fun _ : Fin n => D), ∀ σ : Fin n → Fin d → Bool,
BddAbove (Set.range fun f : H => (1 / n : ℝ) *
∑ i, (f : X → StrongDual ℝ (EuclideanSpace ℝ (Fin d))) (s i).1 (signVec (σ i))))
(hInt : Integrable
(fun s : Fin n → X × StrongDual ℝ (EuclideanSpace ℝ (Fin d)) =>
empRademacherMulti H (fun i => (s i).1))
(Measure.pi fun _ : Fin n => D))
(δ : ℝ) (hδ : 0 < δ) :
Measure.pi (fun _ : Fin n => D)
{s | ∃ f ∈ H, ¬ (spoRisk D w f ≤ empMarginRisk S w γ f s +
(2 * Real.sqrt 2 * rhoSet C + 2 * Real.sqrt 2 * μ * omegaSet S C) / (γ * μ) *
expRademacherMulti D H n +
omegaSet S C * Real.sqrt (Real.log (1 / δ) / (2 * n)))} ≤ ENNReal.ofReal δ := by sorry
end SPOBounds.Margin
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
The statement is about a dimension and a type of features. Let with the Euclidean norm, and let be its dual: the continuous linear functionals . carries some measurable structure, which can be anything. carries some measurable structure that is assumed to be its Borel σ-algebra. The statement also uses several named notions that are imported and not unfolded in the code I was given: , , (spoLoss), (spoRisk), (empMarginRisk), (rhoSet), (omegaSet), (expRademacherMulti), (empRademacherMulti), (marginSupDeviation), (marginSignedSup) and (signVec). What each one means depends on its definition in those imported files. Below they are described only by how they are used.
The hypotheses are:
- The feasible set : is nonempty, compact and convex. It is also nontrivial: it contains two distinct points.
- The oracle: is a map with .
- Strength: with and .
- The margin: with .
- The cost set : is nonempty and bounded.
- The distribution: is a probability measure on . Under , the second coordinate (the cost) lies in almost surely.
- The hypothesis class: is a set of functions .
- Every is measurable.
- For every , the map is measurable on .
- The sample size: with . Write for the product measure on samples , where .
- Measurability of : the map (
marginSupDeviation) is almost-everywhere measurable with respect to . - Measurability of : for every sign pattern , the map (
marginSignedSup) is almost-everywhere measurable with respect to . - Boundedness: for -almost every sample , and for every , the following set of reals is bounded above:
Here , and is the vector in that signVec assigns to it. The functional is evaluated at that vector.
- Integrability: the map is integrable with respect to . This quantity (
empRademacherMulti) depends only on the feature coordinates of the sample. - Confidence: with . No upper bound on is assumed.
Conclusion. Define the bad set
The statement says that
where both sides are compared as extended non-negative reals.
-
The symbols in are applied to these arguments:
- is
spoRiskapplied to . - is
empMarginRiskapplied to . - is
rhoSetof . - is
omegaSetof and . - is
expRademacherMultiof .
- is
-
Nothing in the code states that is measurable. The product measure applied to a set that may not be measurable is its outer measure.
-
"Violates" means the stated inequality between real numbers fails.
-
Real-valued definitions are total. So if
spoRiskorexpRademacherMultiis defined through Bochner integrals or suprema, the following apply:- A non-integrable integrand contributes .
- A set with no upper bound, or an empty set, has supremum .
The code states integrability only for . It does not state integrability of the SPO loss under .
Degenerate cases.
- : has exactly one point, so no can be nontrivial. The hypotheses cannot all hold, and the statement is vacuous.
- Empty : is empty and carries no probability measure. The statement is again vacuous.
- nonempty: this hypothesis adds nothing, because nontriviality already implies it.
- : is empty and the bound holds trivially.
- :
- . The square root of a non-positive real is taken to be , so the last term vanishes.
- The right-hand side is at least the total mass of the probability measure , so the conclusion holds trivially.
- : this is the only range where the inequality says something beyond the total mass of .
- No division by zero: , and , so the divisions , and are never by zero.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.