Theorem 5, p. 21 — oracle inequalities for the expected prediction error of the BIC-type estimators β̂^B_2 and β̂^B_1
ProvedSubsetShrink.BIC.theorem_5Work in the model , where is deterministic, has independent entries with , and the design () has columns of unit Euclidean norm. For let and , and define the BIC-type estimators
There exist universal constants (and a universal constant implicit in ) such that:
- if or , then
- if or (with ), then
The penalties choose the model size from the data, so these oracle inequalities hold over all of rather than over a fixed sparsity class , and require no condition on the design beyond the normalization of its columns.
Formalization Note An estimator is a measurable map with a global minimizer of the objective for every ; the bound is claimed for every such selection (one exists; neither uniqueness nor a particular selection is assumed). The expectation is the lower Lebesgue integral of against the law of , so it cannot vanish by non-integrability. "" is one universal constant , chosen together with before and ; the infimum is written as "for every ". The page claims no sign for , and none is stated; positivity is forced in any proof, since at the first bound fails for least squares. The paper's convention makes ; the Lean products give the same value.
import Mathlib import Definitions.Def_SubsetShrink_BIC_Model
namespace SubsetShrink.BIC
open MeasureTheory ProbabilityTheory
/-- Theorem 5, p. 21: oracle inequalities for the expected prediction error of the BIC-type
estimators `β̂^B_2` and `β̂^B_1`, for every measurable selection of the minimizers. -/
theorem theorem_5 :
∃ a0 b0 c0 C : ℝ, 0 < C ∧
(∀ {n p : ℕ} (X : Matrix (Fin n) (Fin p) ℝ) (fstar : Fin n → ℝ) (σ a b : ℝ)
(βhat : (Fin n → ℝ) → (Fin p → ℝ)),
SubsetShrink.Events.UnitCols X → 1 ≤ p → 0 < σ → 0 ≤ a → 0 ≤ b → (a0 * σ ≤ a ∨ b0 * σ ^ 2 ≤ b) →
Measurable βhat → (∀ y, IsBIC2 X y a b (βhat y)) →
∀ β : Fin p → ℝ,
∫⁻ ε, ENNReal.ofReal (∑ i, (fstar i - X.mulVec (βhat (fstar + ε)) i) ^ 2)
∂(SubsetShrink.Events.noiseLaw n σ) ≤
ENNReal.ofReal (C * (∑ i, (fstar i - X.mulVec β i) ^ 2 + lamB a β * SubsetShrink.Events.l2 β +
muB b β * (SubsetShrink.Events.l0 β : ℝ) + σ ^ 2))) ∧
(∀ {n p : ℕ} (X : Matrix (Fin n) (Fin p) ℝ) (fstar : Fin n → ℝ) (σ lam b : ℝ)
(βhat : (Fin n → ℝ) → (Fin p → ℝ)),
SubsetShrink.Events.UnitCols X → 1 ≤ p → 0 < σ → 0 ≤ lam → 0 ≤ b →
(c0 * σ * Real.sqrt (Real.log (Real.exp 1 * p)) ≤ lam ∨ b0 * σ ^ 2 ≤ b) →
Measurable βhat → (∀ y, IsBIC1 X y lam b (βhat y)) →
∀ β : Fin p → ℝ,
∫⁻ ε, ENNReal.ofReal (∑ i, (fstar i - X.mulVec (βhat (fstar + ε)) i) ^ 2)
∂(SubsetShrink.Events.noiseLaw n σ) ≤
ENNReal.ofReal (C * (∑ i, (fstar i - X.mulVec β i) ^ 2 + lam * SubsetShrink.Events.l1 β +
muB b β * (SubsetShrink.Events.l0 β : ℝ) + σ ^ 2))) := by sorry
end SubsetShrink.BIC
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.