Proof of Theorem 34, p. 44 — with λ_k = 4mk²/p: 1 − Σ_{k≥1} 2m/λ_k = 1 − Σ_{k≥1} p/(2k²) ≥ 1 − p
ProvedLSWCuttingPlane.ChasingZero.union_bound_sump2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1probability-boundseriesunion-bound
Let be an integer and , and for put . Then the series and converge, and
This is the arithmetic of the union bound that closes the proof of Theorem 34: if the -th bad event has probability at most , the probability that none occurs is at least .
Formalization Note The Lean sums run over with in place of the paper's , so they are exactly the paper's sums from . The page writes the first sum with index (""), a typo for .
Preamble
import Mathlib import Definitions.Def_LSWCuttingPlane_ChasingZero_Setting
Formal statement
namespace LSWCuttingPlane.ChasingZero
/-- Proof of Theorem 34, p. 44, last display: with `λ_k = 4 m k² / p` (`k ≥ 1`),
`1 − ∑_{k≥1} 2m/λ_k = 1 − ∑_{k≥1} p/(2k²) ≥ 1 − p`, both series summable.
The summation index `k : ℕ` below stands for the paper's `k + 1`. -/
theorem union_bound_sum (m : ℕ) (hm : 0 < m) (p : ℝ) (hp : 0 < p) :
let lam : ℕ → ℝ := fun k => 4 * (m : ℝ) * ((k : ℝ) + 1) ^ 2 / p
Summable (fun k : ℕ => 2 * (m : ℝ) / lam k) ∧
Summable (fun k : ℕ => p / (2 * ((k : ℝ) + 1) ^ 2)) ∧
1 - ∑' k : ℕ, 2 * (m : ℝ) / lam k = 1 - ∑' k : ℕ, p / (2 * ((k : ℝ) + 1) ^ 2) ∧
1 - p ≤ 1 - ∑' k : ℕ, p / (2 * ((k : ℝ) + 1) ^ 2) := by sorry
end LSWCuttingPlane.ChasingZero
Source
Lee, Sidford, Wong, A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimization, arXiv:1508.04874v2, p. 44, proof of Theorem 34, last display
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.