Theorem 1 (𝓗 part), p. 13; B.1, p. 38 — P(‖X⊤ϵ‖_∞ ≤ σ√(2 log 2p) + σ√(2 log(1/δ₀))) ≥ 1 − δ₀
ProvedSubsetShrink.Events.prob_Hgaussian-noisehigh-probability-eventsp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1sparse-regression
Let , let have columns of unit Euclidean norm, let and , and let have independent coordinates. Then the event
is measurable and
This is the maximal inequality for the Gaussian variables ; it is used for the -regularized estimator (Theorem 3).
Formalization Note is the explicit maximum of over . The probability space is with the law . The hypothesis is the "" of Theorem 1.
Preamble
import Mathlib import Definitions.Def_SubsetShrink_Events_Model open MeasureTheory ProbabilityTheory
Formal statement
namespace SubsetShrink.Events
theorem prob_H {n p : ℕ} (hp : 1 ≤ p) (X : Matrix (Fin n) (Fin p) ℝ) (hX : UnitCols X)
(σ : ℝ) (hσ : 0 < σ) (δ0 : ℝ) (hδ0 : 0 < δ0) (hδ1 : δ0 ≤ 1) :
MeasurableSet (H X σ δ0) ∧ 1 - δ0 ≤ (noiseLaw n σ (H X σ δ0)).toReal := by sorry
end SubsetShrink.Events
Source
Mazumder, Radchenko & Dedieu, Subset Selection with Shrinkage, arXiv:1708.03288v4, p. 13, Theorem 1 (P(H) ≥ 1 − δ0); proof B.1, p. 38
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.