Lemma 4.2 — Hessian characterization of pointwise exp-concavity (with )
ProvedOnlineConvexOpt.SecondOrder.exp_concave_iff_hessian_v2exp-concavityhessianonline-convex-optimization
Statement (Lemma 4.2). Let , let be a real inner-product space, and let be twice differentiable at . Then is -exp-concave at — i.e. is concave to second order at (IsExpConcaveAt) — if and only if
Formalization Note. The retired statement omitted the chapter's standing convention (Definition 4.1's exp-concavity parameter is positive): for the left side is always true while the right side says , and for the equivalence also fails. The hypothesis hα : 0 < α is added; nothing else changes. is the iterated Fréchet derivative (fderiv ℝ (fderiv ℝ f) x) v v, the differential (fderiv ℝ f x) v, and ContDiffAt ℝ 2 f x renders "twice differentiable".
Preamble
import Mathlib import Definitions.Def_OnlineConvexOpt_SecondOrder_ExpConcave open OnlineConvexOpt.SecondOrder
Formal statement
namespace OnlineConvexOpt.SecondOrder
variable {E : Type*} [NormedAddCommGroup E] [InnerProductSpace ℝ E]
/-- Lemma 4.2 (Hazan, *Introduction to Online Convex Optimization*, 2nd ed.,
arXiv:1909.05207v3, p. 59, PDF p. 81). For an exp-concavity parameter `α > 0`, a
twice-differentiable function `f : E → ℝ` is `α`-exp-concave at `x` (`IsExpConcaveAt`, the
pointwise Hessian formulation of `g(y) = exp(-α f(y))` being concave to second order at `x`) if
and only if `∇²f(x) ⪰ α∇f(x)∇f(x)^⊤`. The matrix inequality is stated as a comparison of the
two quadratic forms it induces: for every direction `v`, `v^⊤∇²f(x)v ≥ α(∇f(x)^⊤v)^2`, where
`v^⊤∇²f(x)v` is the iterated Fréchet derivative `(fderiv ℝ (fderiv ℝ f) x) v v` and
`∇f(x)^⊤v` is the differential `(fderiv ℝ f x) v`.
Corrected version: the retired statement omitted the chapter's standing convention `α > 0`
(Definition 4.1's exp-concavity parameter is positive; the Hessian of `exp(-αf)` is
`exp(-αf)(α²∇f∇f^⊤ - α∇²f)`, and dividing by `α` reverses or kills the inequality for
`α ≤ 0`). -/
theorem exp_concave_iff_hessian_v2 (α : ℝ) (hα : 0 < α) (f : E → ℝ) (x : E)
(hf : ContDiffAt ℝ 2 f x) :
IsExpConcaveAt α f x ↔
∀ v : E, α * ((fderiv ℝ f x) v) ^ 2 ≤ (fderiv ℝ (fderiv ℝ f) x) v v := by sorry
end OnlineConvexOpt.SecondOrder
Source
Hazan, Introduction to Online Convex Optimization, 2nd ed., arXiv:1909.05207v3, p. 59, Lemma 4.2 (PDF p. 81)