(28), p. 38 — ∑_j u♯_j √log(2p/j) ≤ ‖u‖ √(∑_{j≤s} log(2p/j)) ≤ √(s log(2ep/s)) ‖u‖ for u ∈ B₀(s)
ProvedSubsetShrink.Events.eq_28gaussian-noisehigh-probability-eventsp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1sparse-regression
Let and let satisfy . Write for the non-increasing rearrangement of . Then
This bounds the sorted- entry of the event by the threshold of for -sparse vectors, the second ingredient of the inclusion .
Formalization Note The left side is the definition sortedSum: the maximum over permutations of , equal to the sorted sum by the rearrangement inequality (the weights are non-increasing and non-negative). Indices of Fin p are 0-based.
Preamble
import Mathlib import Definitions.Def_SubsetShrink_Events_Model open MeasureTheory ProbabilityTheory
Formal statement
namespace SubsetShrink.Events
theorem eq_28 {p s : ℕ} (hs : 1 ≤ s) (hsp : s ≤ p) (u : Fin p → ℝ) (hu : l0 u ≤ s) :
sortedSum u ≤ l2 u * Real.sqrt (∑ j ∈ Finset.Icc 1 s, Real.log (2 * (p : ℝ) / j)) ∧
l2 u * Real.sqrt (∑ j ∈ Finset.Icc 1 s, Real.log (2 * (p : ℝ) / j)) ≤
Real.sqrt ((s : ℝ) * Real.log (2 * Real.exp 1 * p / s)) * l2 u := by sorry
end SubsetShrink.Events
Source
Mazumder, Radchenko & Dedieu, Subset Selection with Shrinkage, arXiv:1708.03288v4, p. 38, proof of Theorem 1 (B.1), (28)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.