p. 38, display after (27) — ∑_{j≤s} log(2p/j) = s log(2p) − log(s!) ≤ s log(2ep/s)
ProvedSubsetShrink.Events.sum_log_boundgaussian-noisehigh-probability-eventsp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1sparse-regression
Let be integers. Then
The inequality is the bound rewritten; it controls the sum of the squared weights of the sorted- term over the first indices, which enters the proof of Theorem 1 through (28).
Formalization Note The sum runs over (Finset.Icc 1 s) with natural logarithms; keeps every logarithm's argument positive.
Preamble
import Mathlib import Definitions.Def_SubsetShrink_Events_Model open MeasureTheory ProbabilityTheory
Formal statement
namespace SubsetShrink.Events
theorem sum_log_bound {p s : ℕ} (hs : 1 ≤ s) (hsp : s ≤ p) :
∑ j ∈ Finset.Icc 1 s, Real.log (2 * (p : ℝ) / j) =
(s : ℝ) * Real.log (2 * p) - Real.log (s.factorial) ∧
∑ j ∈ Finset.Icc 1 s, Real.log (2 * (p : ℝ) / j) ≤
(s : ℝ) * Real.log (2 * Real.exp 1 * p / s) := by sorry
end SubsetShrink.Events
Source
Mazumder, Radchenko & Dedieu, Subset Selection with Shrinkage, arXiv:1708.03288v4, p. 38, proof of Theorem 1 (B.1), display after (27)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.