Theorem 4, p. 30 — (NV-reg) is uniformly stable with parameter (b∨h)²X²_max/(2nλ)
ProvedBigDataNV.Reg.theorem4_uniform_stabilityLet be the newsvendor costs, the regularization parameter and . Let be a sample whose feature vectors satisfy , and fix an index . Let minimize the (NV-reg) objective
over , and let minimize the leave-one-out objective . Then for every feature vector with and every demand ,
This is the uniform stability of (NV-reg) with parameter , display (28). Together with the generalization bound for stable algorithms (Theorem 6), it yields the feature-count-free bound of Theorem 2.
Formalization Note The page writes the constant as , i.e. a factor . The leave-one-out problem keeps the weight , as in Theorem 5 (Bousquet and Elisseeff's (20)); running (NV-reg) literally on points would use . The statement holds for any pair of minimizers. Symmetry of the algorithm is not stated, as the objective does not depend on the order of the sample. No bound on the demands is needed.
import Mathlib import Definitions.Def_BigDataNV_Reg_Setting
namespace BigDataNV.Reg
/-- Theorem 4, p. 30: (NV-reg) is uniformly stable with respect to the newsvendor cost, with
stability parameter `(b ∨ h)² X²_max / (2 n λ)`, in the form used by Theorem 5 (p. 31): the
comparison solution minimizes the leave-one-out objective with weight `1/n`. -/
theorem theorem4_uniform_stability {p n : ℕ} (b h lam Xmax : ℝ)
(hb : 0 < b) (hh : 0 < h) (hlam : 0 < lam) (hX : 0 ≤ Xmax)
(S : Fin n → EuclideanSpace ℝ (Fin p) × ℝ) (hS : ∀ j, ‖(S j).1‖ ^ 2 ≤ Xmax ^ 2)
(i : Fin n) (q q' : EuclideanSpace ℝ (Fin p))
(hq : IsNVRegSolution b h lam S q) (hq' : IsNVRegLooSolution b h lam S i q') :
∀ x : EuclideanSpace ℝ (Fin p), ‖x‖ ^ 2 ≤ Xmax ^ 2 → ∀ d : ℝ,
|nvCost b h (inner ℝ q x) d - nvCost b h (inner ℝ q' x) d| ≤
(max b h) ^ 2 * Xmax ^ 2 / (2 * (n : ℝ) * lam) := by sorry
end BigDataNV.Reg
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.