AFTD Auto-Formalizing Theoretical Domains

exp_neg_le_linear

theoremverifiedimported Lean

Chord bound for the exponential on the unit interval. For every $\eta > 0$ and every $x \in [0,1]$, the value $e^{-\eta x}$ lies below the chord joining the endpoints of the graph of $t \mapsto e^{-\eta t}$ over $[0,1]$; that is, the inequality \[ e^{-\eta x} \;\le\; 1 - \bigl(1 - e^{-\eta}\bigr)\,x \] holds, the right-hand side being the affine function equal to $1$ at $x = 0$ and to $e^{-\eta}$ at $x = 1$.

Statement

set_option relaxedAutoImplicit false in
set_option autoImplicit false in
open Real Finset BigOperators in
lemma exp_neg_le_linear {η x : ℝ} (hη : 0 < η) (hx0 : 0 ≤ x) (hx1 : x ≤ 1) :
    Real.exp (-η * x) ≤ 1 - (1 - Real.exp (-η)) * x
Source
TCSlib, `exp_neg_le_linear`
Lean proof
By Karim Abdel Sadek, Mark Bedaywi, from github.com/Shilun-Allan-Li/tcslib at c8a02591b1e5 (Copyright (c) 2026 Karim Abdel Sadek and Mark Bedaywi. All rights reserved, Apache-2.0). Compiled here against leanprover/lean4:v4.33.1, Mathlib v4.33.1; written for leanprover/lean4:v4.25.0.
Verified
07 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 1
  • potential_ratio_lePotential ratio bound for Hedge. Fix $N \ge 1$ experts, a horizon of $T$ rounds, a learning rate $\eta > 0$, and a valid loss sequence…

Lean source view module on GitHub

set_option relaxedAutoImplicit false inset_option autoImplicit false inopen Real Finset BigOperators in/-- For `x ∈ [0,1]` and `η > 0`, `exp(-ηx) ≤ 1 - (1 - exp(-η)) x`: the exponential lies below the chord joining its values at `-η` and `0`. This is the elementary bound `β^x ≤ 1 - (1 - β) x` of [FS97, §2.1, Eq. (3) (proof of Lemma 1)] with `β = e^{-η}`; it replaces Hoeffding's lemma in the weak regret bound. -/lemma exp_neg_le_linear {η x : ℝ} (hη : 0 < η) (hx0 : 0 ≤ x) (hx1 : x ≤ 1) :    Real.exp (-η * x) ≤ 1 - (1 - Real.exp (-η)) * x := by  -- Convexity: exp(x·a + (1-x)·b) ≤ x·exp(a) + (1-x)·exp(b)  -- Apply with a = -η, b = 0.  have h1x : 0 ≤ 1 - x := sub_nonneg.mpr hx1  have hconv := convexOn_exp.2 (Set.mem_univ (-η)) (Set.mem_univ 0) hx0 h1x    (by linarith : x + (1 - x) = 1)  simp only [smul_eq_mul, mul_zero, add_zero, exp_zero, mul_one] at hconv  -- hconv : exp (x * -η) ≤ x * exp (-η) + (1 - x)  -- Goal : exp (-η * x) ≤ 1 - (1 - exp (-η)) * x  -- These are equal since x * -η = -η * x and x * exp(-η) + 1 - x = 1 - (1 - exp(-η)) * x  have : x * -η = -η * x := by ring  rw [this] at hconv  linarith
See it in the graphDiscuss this resultChallenge it