Proposition 5.1(a), p. 173 — ψ_e is 1-strongly convex on int Δ w.r.t. ‖·‖₁: Σ(x_j − y_j) ln(x_j/y_j) ≥ ‖x − y‖₁²
ProvedBeckTeboulleMD.EMDA.proposition_5_1_aentropyp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1pinsker-inequalitystrong-convexityunit-simplex
Let be the entropy and . Then for all :
- ;
- is -strongly convex over with respect to : for with ,
The strong convexity constant with respect to the norm is what makes the entropic mirror descent bound depend on the dimension only through .
Formalization Note is written , and the strong convexity is written out explicitly instead of through a normed space carrying the norm; it is Mathlib's notion of strong convexity with parameter for that norm. is the Fréchet derivative of on (which does not depend on the norm). "" is the relative interior of , since has empty interior in .
Preamble
import Mathlib import Definitions.Def_BeckTeboulleMD_EMDA_Setting
Formal statement
namespace BeckTeboulleMD.EMDA
/-- Proposition 5.1(a), p. 173: on the relative interior of the unit simplex,
`⟨∇ψ_e(x) − ∇ψ_e(y), x − y⟩ = ∑_j (x_j − y_j) ln(x_j / y_j) ≥ ‖x − y‖₁²`,
and `ψ_e` is `1`-strongly convex there with respect to `‖·‖₁`. -/
theorem proposition_5_1_a {n : ℕ} :
(∀ x ∈ relIntSimplex n, ∀ y ∈ relIntSimplex n,
(fderiv ℝ (entropy (n := n)) x - fderiv ℝ (entropy (n := n)) y) (x - y)
= ∑ j, (x j - y j) * Real.log (x j / y j)) ∧
(∀ x ∈ relIntSimplex n, ∀ y ∈ relIntSimplex n,
(∑ j, |x j - y j|) ^ 2 ≤ ∑ j, (x j - y j) * Real.log (x j / y j)) ∧
(∀ x ∈ relIntSimplex n, ∀ y ∈ relIntSimplex n, ∀ a b : ℝ, 0 ≤ a → 0 ≤ b → a + b = 1 →
entropy (a • x + b • y)
≤ a * entropy x + b * entropy y - a * b * (1 / 2 * (∑ j, |x j - y j|) ^ 2)) := by sorry
end BeckTeboulleMD.EMDA
Source
Beck & Teboulle, Mirror descent and nonlinear projected subgradient methods for convex optimization, Oper. Res. Lett. 31 (2003), p. 173, Proposition 5.1(a)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.