(51), p. 49 — basic inequality for the BIC-type estimator β̂^B_2
ProvedSubsetShrink.BIC.eq_51best-subset-selectionmodel-selectionoracle-inequalityp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1sparse-regression
Let , , and . Let be any global minimizer over of , where and . Then for every ,
This deterministic inequality is the starting point of every bound for : the remaining work is to control the noise term on high-probability events.
Formalization Note The statement is deterministic: is an arbitrary vector and no distributional assumption is used. Products are muB b β * l0 β (value at ).
Preamble
import Mathlib import Definitions.Def_SubsetShrink_BIC_Model
Formal statement
namespace SubsetShrink.BIC
open MeasureTheory ProbabilityTheory
/-- (51), p. 49: the basic inequality for a minimizer of the objective of `β̂^B_2`. -/
theorem eq_51 {n p : ℕ} (X : Matrix (Fin n) (Fin p) ℝ) (fstar ε : Fin n → ℝ) (a b : ℝ)
(βhat : Fin p → ℝ) (hβhat : IsBIC2 X (fstar + ε) a b βhat) (β : Fin p → ℝ) :
∑ i, (fstar i - X.mulVec βhat i) ^ 2 + lamB a βhat * SubsetShrink.Events.l2 βhat + muB b βhat * (SubsetShrink.Events.l0 βhat : ℝ) ≤
∑ i, (fstar i - X.mulVec β i) ^ 2 + 2 * SubsetShrink.Events.dot ε (X.mulVec (βhat - β)) +
lamB a β * SubsetShrink.Events.l2 β + muB b β * (SubsetShrink.Events.l0 β : ℝ) := by sorry
end SubsetShrink.BIC
Source
Mazumder, Radchenko & Dedieu, Subset Selection with Shrinkage, arXiv:1708.03288v4, p. 49, proof of Theorem 5 (B.13), (51)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.