Bounds for general decomposable M-estimators (Theorem 9.19)
DisprovedHighDimStat.Decomposability.thm9_19_general_boundTheorem 9.19 ("Bounds for general models"). The chapter's central result: a deterministic error bound for the regularized M-estimator that holds under any restricted-strong-convexity certificate and any decomposable regularizer, for any choice of the model subspace pair subject to two explicit side conditions.
Assume (A1) is convex and satisfies the restricted strong convexity condition (Def. 9.15) with curvature , radius and tolerance , with respect to a norm induced by the inner product on ; and (A2) the regularizer is decomposable with respect to a subspace pair . Let be any optimal solution of the M-estimator, conditioned on the good event . Then:
where (Eq. (9.47)).
As the book itself remarks, this claim is deterministic: probability enters only in certifying the RSC condition and the good event, separately, for a specific statistical model.
Formalization Note Both parts (a) and (b) are packaged as one conjunction (main_item
of this mission). Ψ(bar M) (subspaceLip Φ Mbar) is used throughout — source.pdf pages
300/301, rendered and inspected directly, print the bar over M̄ clearly in equations
(9.47)-(9.48) (the derived source.txt extraction drops the diacritic, not the PDF
itself), independently confirmed by checking the book's own proof, which applies the
subspace Lipschitz constant to — see Core's
Formalization Note. hκ : 0 < κ and hR : 0 < R make explicit the positivity Definition
9.15 states jointly for and ("with radius , curvature "), and
hlam : 0 < lamN the chapter's standing convention that is a (positive)
regularization weight; none of the three narrows the theorem's actual scope (see
MODERATION_NOTES.md).
import Mathlib import Definitions.Def_HighDimStat_Decomposability_Core
namespace HighDimStat.Decomposability
open scoped RealInnerProductSpace
variable {Ω : Type*} [NormedAddCommGroup Ω] [InnerProductSpace ℝ Ω] [FiniteDimensional ℝ Ω]
/-- Theorem 9.19 ("Bounds for general models", p. 280): under (A1) — `Ln` convex and satisfying
restricted strong convexity with curvature `κ`, tolerance `τn²` and radius `R` — and (A2) — `Φ`
decomposable with respect to `(M, M̄)` — conditioned on the good event `G(λn)`:
(a) any optimal solution `θ̂` of the M-estimator satisfies
`Φ(θ̂ - θ*) ≤ 4(Ψ(M̄) ‖θ̂ - θ*‖ + Φ(θ*_{Mᗮ}))`;
(b) whenever `τn² Ψ(M̄)² ≤ κ/64` and `εn(M, M̄) ≤ R`, `‖θ̂ - θ*‖² ≤ εn²(M, M̄)`. -/
theorem thm9_19_general_bound
(Ln Φ : Ω → ℝ) (M Mbar : Submodule ℝ Ω) (θstar θhat g : Ω) (lamN κ τnSq R : ℝ)
(hΦ : IsRegularizerNorm Φ) (hdecomp : IsDecomposable Φ M Mbar)
(hconv : ConvexOn ℝ Set.univ Ln) (hgrad : HasGradientAt Ln g θstar)
(hRSC : RSC Ln g θstar Φ κ τnSq R)
(hκ : 0 < κ) (hR : 0 < R) (hlam : 0 < lamN)
(hopt : ∀ θ : Ω, Ln θhat + lamN * Φ θhat ≤ Ln θ + lamN * Φ θ)
(hG : goodEvent Φ g lamN)
(htol : τnSq * subspaceLip Φ Mbar ^ 2 ≤ κ / 64)
(hRbound : Real.sqrt (epsilonSq Φ M Mbar θstar lamN κ τnSq) ≤ R) :
Φ (θhat - θstar) ≤
4 * (subspaceLip Φ Mbar * ‖θhat - θstar‖ + Φ (Mᗮ.starProjection θstar)) ∧
‖θhat - θstar‖ ^ 2 ≤ epsilonSq Φ M Mbar θstar lamN κ τnSq := by sorry
end HighDimStat.Decomposability
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.