Proof of Theorem 34, p. 44 — with α = 1/(2(c+R)): e^{2α(c+R)}(α(c+R))² ≤ 1 and α²e^{αc}c² ≤ e^{−α(R+c)}
ProvedLSWCuttingPlane.ChasingZero.alpha_choicep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1parameter-choicepotential-function
Let and , and put . Then
This is the choice of the scale of the exponential potential in the proof of Theorem 34: it makes the adversary's drift term no larger than the decrease claimed for the player's reset, and it fixes the factor in the final bound.
Preamble
import Mathlib import Definitions.Def_LSWCuttingPlane_ChasingZero_Setting
Formal statement
namespace LSWCuttingPlane.ChasingZero
/-- Proof of Theorem 34, p. 44: with `α = 1/(2(c + R))`,
`e^{2α(c+R)} (α(c + R))² ≤ 1` and `α² e^{αc} c² ≤ e^{−α(R+c)}`. -/
theorem alpha_choice (c R α : ℝ) (hc : 0 < c) (hR : 0 < R) (hα : α = 1 / (2 * (c + R))) :
Real.exp (2 * α * (c + R)) * (α * (c + R)) ^ 2 ≤ 1 ∧
α ^ 2 * Real.exp (α * c) * c ^ 2 ≤ Real.exp (-(α * (R + c))) := 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, first sentence
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.