Let XβRnΓp have columns of unit Euclidean norm, let Ο>0, 1β€sβ€p and Ξ΄0ββ(0,1], and let Ο΅ have independent N(0,Ο2) coordinates. Then the event
This is the fast-rate event of the paper's oracle inequalities, with the coefficient of log(1/Ξ΄0β) corrected from 1 to 3.
Formalization Note The paper prints the event with log(1/Ξ΄0β) instead of 3log(1/Ξ΄0β). As printed the bound is false: for n=p=s=1 and X=[1] the printed event is {β£Ο΅β£β€Ο5+Lβ} with L=log(1/Ξ΄0β), whose complement has probability 2Ξ¦Λ(5+Lβ), and this exceeds eβL=Ξ΄0β for Lβ₯9 (at L=9: 1.83β 10β4>1.23β 10β4). The corrected constant 3 follows from the argument the paper cites (Lemma 8 of its reference [51]): for a support S of size s, supsuppuβSβΟ΅β€Xu/β₯Xuβ₯ is the norm of the projection of Ο΅ on the span of the columns in S, a ΟΟ variable with at most s degrees of freedom; the LaurentβMassart bound P(Οs2ββ₯s+2sxβ+2x)β€eβx with x=slog(ep/s)+log(1/Ξ΄0β), 2sxββ€s+x and log(ep/s)β₯1 give the threshold 5slog(ep/s)+3log(1/Ξ΄0β), and a union bound over (spβ)β€(ep/s)s supports gives failure probability at most Ξ΄0β. The printed event is contained in the corrected one.
Preamble
import Mathlib
import Definitions.Def_SubsetShrink_Events_Model
open MeasureTheory ProbabilityTheory
Formal statement
namespace SubsetShrink.Events
theorem prob_G_corrected {n p s : β} (X : Matrix (Fin n) (Fin p) β) (hX : UnitCols X)
(Ο : β) (hΟ : 0 < Ο) (hs : 1 β€ s) (hsp : s β€ p) (Ξ΄0 : β) (hΞ΄0 : 0 < Ξ΄0) (hΞ΄1 : Ξ΄0 β€ 1) :
MeasurableSet (Gc X Ο Ξ΄0 s) β§ 1 - Ξ΄0 β€ (noiseLaw n Ο (Gc X Ο Ξ΄0 s)).toReal := by sorry
end SubsetShrink.Events
Source
Mazumder, Radchenko & Dedieu, Subset Selection with Shrinkage, arXiv:1708.03288v4, p. 13, Theorem 1 (P(G_s) β₯ 1 β Ξ΄0, event G_s on p. 13; constant corrected); proof B.1, pp. 38β39
Confirmed by the moderator at approval.