Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Bounds for general decomposable M-estimators (Theorem 9.19)

Disproved
HighDimStat.Decomposability.thm9_19_general_bound

by mikedeng1 · Sep 19, 2026 · Mathlib 0df444a (Lean v4.33.1)

functional-analysishigh-dimensional-statisticsoptimizationstatistics

Theorem 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) LnL_nLn​ is convex and satisfies the restricted strong convexity condition (Def. 9.15) with curvature κ>0\kappa>0κ>0, radius RRR and tolerance τn2\tau_n^2τn2​, with respect to a norm ∥⋅∥\|\cdot\|∥⋅∥ induced by the inner product on Ω\OmegaΩ; and (A2) the regularizer Φ\PhiΦ is decomposable with respect to a subspace pair (M,Mˉ)(\mathcal M,\bar{\mathcal M})(M,Mˉ). Let θ^\hat\thetaθ^ be any optimal solution of the M-estimator, conditioned on the good event G(λn)\mathcal G(\lambda_n)G(λn​). Then:

(a)Φ(θ^−θ∗)≤4(Ψ(Mˉ) ∥θ^−θ∗∥+Φ(θM⊥∗)).\text{(a)}\quad \Phi(\hat\theta-\theta^*) \le 4\Big(\Psi(\bar{\mathcal M})\, \|\hat\theta-\theta^*\| + \Phi(\theta^*_{\mathcal M^\perp})\Big).(a)Φ(θ^−θ∗)≤4(Ψ(Mˉ)∥θ^−θ∗∥+Φ(θM⊥∗​)). (b)if τn2Ψ2(Mˉ)≤κ/64 and εn(M,Mˉ)≤R, then ∥θ^−θ∗∥2≤εn2(M,Mˉ).\text{(b)}\quad \text{if } \tau_n^2\Psi^2(\bar{\mathcal M}) \le \kappa/64 \text{ and } \varepsilon_n(\mathcal M,\bar{\mathcal M}) \le R, \text{ then } \|\hat\theta-\theta^*\|^2 \le \varepsilon_n^2(\mathcal M,\bar{\mathcal M}).(b)if τn2​Ψ2(Mˉ)≤κ/64 and εn​(M,Mˉ)≤R, then ∥θ^−θ∗∥2≤εn2​(M,Mˉ).

where εn2(M,Mˉ):=9λn2κ2Ψ2(Mˉ)+8κ(λnΦ(θM⊥∗)+16τn2Φ2(θM⊥∗))\varepsilon_n^2(\mathcal M,\bar{\mathcal M}) := \frac{9\lambda_n^2}{\kappa^2} \Psi^2(\bar{\mathcal M}) + \frac{8}{\kappa}\big(\lambda_n\Phi(\theta^*_{\mathcal M^\perp}) + 16\tau_n^2\Phi^2(\theta^*_{\mathcal M^\perp})\big)εn2​(M,Mˉ):=κ29λn2​​Ψ2(Mˉ)+κ8​(λn​Φ(θM⊥∗​)+16τn2​Φ2(θM⊥∗​)) (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 ΔMˉ∈Mˉ\Delta_{\bar{\mathcal M}}\in\bar{\mathcal M}ΔMˉ​∈Mˉ — see Core's Formalization Note. hκ : 0 < κ and hR : 0 < R make explicit the positivity Definition 9.15 states jointly for κ\kappaκ and RRR ("with radius R>0R>0R>0, curvature κ>0\kappa>0κ>0"), and hlam : 0 < lamN the chapter's standing convention that λn\lambda_nλn​ is a (positive) regularization weight; none of the three narrows the theorem's actual scope (see MODERATION_NOTES.md).

Preamble
import Mathlib
import Definitions.Def_HighDimStat_Decomposability_Core
Formal statement
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
Source
Wainwright, High-Dimensional Statistics, CUP 2019, p. 280 (PDF p. 300), Theorem 9.19, Eqs. (9.46)-(9.48)
Human review
  • Endorsed by Shuze Chen · Sep 28, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Sep 28, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me