Theorem 2 — Natarajan-dimension generalization bound for the SPO loss over a polyhedron
ProvedSPOBounds.Natarajan.natarajan_generalization_boundLet be a nonempty, compact, convex polyhedron and the set of its extreme points, and let be an optimization oracle for whose values are extreme points of . Let be a nonempty bounded set of cost vectors, let be a probability distribution on whose cost component lies in almost surely, and let be a family of functions . Let be a natural number such that every finite set N-shattered by has at most points. Then for every and every , with probability at least over an i.i.d. sample drawn from , every satisfies
With this is the paper's Theorem 2: the SPO risk of every predictor in the class is controlled by its empirical SPO risk plus a term of order , uniformly over the class and hence for any training procedure.
Formalization Note "With probability at least " is stated as: the product measure of the set of samples on which some violates the inequality is at most (outer measure for a non-measurable set, so the strong form). Added hypotheses, all disclosed: (i) the oracle returns extreme points of , the proof's own "w.l.o.g." (p. 31), since p. 10 allows non-extreme optimal points under ties; (ii) the three measurability hypotheses of Theorem 1 (each loss function measurable; the uniform deviation and, for each sign vector, the signed supremum a.e.-measurable in the sample), on which the paper is silent. is replaced by an upper bound on the sizes of N-shattered sets (equivalent when ; the printed bound is vacuous otherwise). is Set.ncard of the extreme points; the logarithm is natural.
import Mathlib import Definitions.Def_SPOBounds_Natarajan_Model import Definitions.Def_SPOBounds_Natarajan_Rademacher import Definitions.Def_SPOBounds_Natarajan_NatarajanDim open MeasureTheory
namespace SPOBounds.Natarajan
/-- **Theorem 2, second display** (arXiv:1905.11488v3, p. 11). Let `S` be a nonempty compact
convex polyhedron with extreme-point set `𝔖`, let the oracle `w` return extreme points of `S`,
let every set N-shattered by `w*(H)` have at most `k` elements, and let the cost vectors lie
almost surely in the nonempty bounded set `C`. For any `δ > 0`, with probability at least
`1 − δ` over an i.i.d. sample of size `n ≥ 1`, every `f ∈ H` satisfies
`R_SPO(f) ≤ R̂_SPO(f) + 2 ω_S(C) √(2 k log(n |𝔖|²) / n) + ω_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 `δ`. The measurability hypotheses `hℓ`, `hΦ`, `hA` are added (the paper is silent). -/
theorem natarajan_generalization_bound {d : ℕ} {X : Type*} [MeasurableSpace X]
(S : Set (EuclideanSpace ℝ (Fin d))) (hS : S.Nonempty) (hSc : IsCompact S)
(hSv : Convex ℝ S) (hSp : IsPolyhedron S)
(w : EuclideanSpace ℝ (Fin d) → EuclideanSpace ℝ (Fin d)) (hw : IsOracle S w)
(hwv : ∀ c, w c ∈ Set.extremePoints ℝ S)
(C : Set (EuclideanSpace ℝ (Fin d))) (hC : C.Nonempty) (hCb : Bornology.IsBounded C)
(D : Measure (X × EuclideanSpace ℝ (Fin d))) [IsProbabilityMeasure D]
(hDC : ∀ᵐ z ∂D, z.2 ∈ C)
(H : Set (X → EuclideanSpace ℝ (Fin d)))
(hℓ : ∀ f ∈ H, Measurable (fun z : X × EuclideanSpace ℝ (Fin d) => spoLoss w (f z.1) z.2))
(k : ℕ) (hk : ∀ T : Finset X, NShatters (oracleClass w H) T → T.card ≤ k)
(n : ℕ) (hn : 0 < n)
(hΦ : AEMeasurable (fun s : Fin n → X × EuclideanSpace ℝ (Fin d) => supDeviation D w H s)
(Measure.pi fun _ : Fin n => D))
(hA : ∀ σ : Fin n → Bool,
AEMeasurable (fun s : Fin n → X × EuclideanSpace ℝ (Fin d) => signedSup w H σ s)
(Measure.pi fun _ : Fin n => D))
(δ : ℝ) (hδ : 0 < δ) :
Measure.pi (fun _ : Fin n => D)
{s | ∃ f ∈ H, ¬ (spoRisk D w f ≤ empRisk w f s +
2 * linGapSet S C * Real.sqrt (2 * k *
Real.log ((n : ℝ) * ((Set.extremePoints ℝ S).ncard : ℝ) ^ 2) / n) +
linGapSet S C * Real.sqrt (Real.log (1 / δ) / (2 * n)))} ≤ ENNReal.ofReal δ := by sorry
end SPOBounds.Natarajan
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Throughout, with its Euclidean structure. Several names come from imported definition files whose code was not provided: IsPolyhedron, IsOracle, spoLoss, spoRisk, empRisk, linGapSet, oracleClass, NShatters, supDeviation, signedSup. This read-back therefore cannot unfold them. It describes only how the statement uses them, and each one means exactly what its imported definition says. The doc-comment above the theorem is a comment, not part of the assertion, and is not used here.
Data and hypotheses. Fix a natural number and a type with a σ-algebra. The theorem assumes the following.
- The feasible set. is nonempty, compact and convex, and satisfies the imported predicate
IsPolyhedron. - The oracle. is any function that:
- satisfies the imported predicate
IsOraclerelative to ; - for every (including ), returns an extreme point of . Write for the set of extreme points of .
- satisfies the imported predicate
- The cost set. is nonempty and bounded.
- The distribution. is a probability measure on . For -almost every pair , the second component lies in .
- The hypothesis class. is an arbitrary set of functions . No measurability of itself is required.
- Measurability of the loss. For every , the map is measurable.
- Natarajan-dimension bound. is a natural number. For every finite set that is shattered by , in the sense of the imported
NShatters, we have . - Sample size. is a natural number with . is the -fold product measure on samples .
- Measurability of the deviation. The map is -almost-everywhere measurable.
- Measurability of the signed suprema. For every sign pattern , the map is -almost-everywhere measurable.
- Confidence level. is a real number with . There is no upper bound on .
Notation for the bound.
- is the imported population risk.
- is the imported empirical risk on the sample .
- is an imported real number.
- is the number of extreme points of , as a natural number. By this convention it would be if the set were infinite.
Define
Conclusion. The -measure of the set of samples for which some has (that is, fails ) is at most :
- The set is not asserted to be measurable, so here is the outer measure.
- The right-hand side is viewed as an extended nonnegative real.
Degenerate cases.
- Large . If , the conclusion holds trivially, because is a probability measure. Also, when , and the real square root returns , so the last term vanishes. When it is as well.
- . The middle term is .
- Logarithm term. Since , is taken of a nonnegative real.
- If (an infinite or empty extreme-point set), this is , which evaluates to by convention.
- If and , it is .
- In both cases the middle term vanishes.
- . is a single point, so and is constant.
- . cannot be empty, since is a probability measure on .
- Empty . If is empty, the exceptional set is empty and the statement is trivial.
- Imported quantities. , and take whatever values their imported definitions give. That includes any default values those definitions produce, for example an integral of a non-integrable function or a supremum of an empty or unbounded set, and the bound is stated against those values as they are.
- Sign convention. The statement reads "true"/"false" in as whatever sign convention
signedSupuses.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.