Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

EDA, p. 174 — the EDA update is the SANP step (3.11) with ψ = ψ_e on X = Δ and stays in int Δ

Proved
BeckTeboulleMD.EMDA.eda_is_sanp_step

by mikedeng1 · Oct 5, 2026 · Mathlib 0df444a (Lean v4.33.1)

entropic-mirror-descentexponentiated-gradientmirror-descentp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1unit-simplex

Let y∈int⁡Δy \in \operatorname{int}\Deltay∈intΔ (all yj>0y_j > 0yj​>0, ∑jyj=1\sum_j y_j = 1∑j​yj​=1), z∈Rnz \in \mathbb R^nz∈Rn and t>0t > 0t>0, and define

wj=yj e−tzj∑i=1nyi e−tzi,j=1,…,n.w_j = \frac{y_j\, e^{-t z_j}}{\sum_{i=1}^n y_i\, e^{-t z_i}}, \qquad j = 1, \dots, n.wj​=∑i=1n​yi​e−tzi​yj​e−tzj​​,j=1,…,n.

Then w∈int⁡Δw \in \operatorname{int}\Deltaw∈intΔ, and www minimises the SANP objective over the simplex:

⟨w,z⟩+1tBψe(w,y)≤⟨u,z⟩+1tBψe(u,y)for all u∈Δ.\langle w, z\rangle + \frac1t B_{\psi_e}(w, y) \le \langle u, z\rangle + \frac1t B_{\psi_e}(u, y) \qquad \text{for all } u \in \Delta.⟨w,z⟩+t1​Bψe​​(w,y)≤⟨u,z⟩+t1​Bψe​​(u,y)for all u∈Δ.

With z=f′(xk)z = f'(x^k)z=f′(xk) and y=xky = x^ky=xk, this says that the entropic descent algorithm (EDA) is exactly SANP (3.11) with X=ΔX = \DeltaX=Δ and ψ=ψe\psi = \psi_eψ=ψe​, and that its iterates remain in the relative interior of Δ\DeltaΔ, so that Theorems 4.1 and 4.2 apply to it.

Formalization Note The page derives the EDA by "using the entropy function ψe\psi_eψe​ in (3.12)", that is, in SANP with a ψ\psiψ satisfying (3.12); this item states the resulting identification for one step. ⟨u,z⟩=∑jujzj\langle u, z\rangle = \sum_j u_j z_j⟨u,z⟩=∑j​uj​zj​, and Bψe(u,y)B_{\psi_e}(u, y)Bψe​​(u,y) uses the derivative of ψe\psi_eψe​ at yyy, which exists because yyy has positive entries.

Preamble
import Mathlib
import Definitions.Def_BeckTeboulleMD_EMDA_Setting
Formal statement
namespace BeckTeboulleMD.EMDA

/-- The EDA is SANP with `ψ_e` on `Δ`, p. 174: for `y` in the relative interior of `Δ`, a vector `z`
(the subgradient `f′(y)`) and `t > 0`, the point `w_j = y_j e^{−t z_j} / ∑_i y_i e^{−t z_i}` lies in
the relative interior of `Δ` and minimises `u ↦ ⟨u, z⟩ + (1/t) B_{ψ_e}(u, y)` over `Δ`. -/
theorem eda_is_sanp_step {n : ℕ} (y : Fin n → ℝ) (hy : y ∈ relIntSimplex n)
    (z : Fin n → ℝ) (t : ℝ) (ht : 0 < t) :
    (fun j => y j * Real.exp (-(t * z j)) / ∑ i, y i * Real.exp (-(t * z i))) ∈ relIntSimplex n ∧
    ∀ u ∈ stdSimplex ℝ (Fin n),
      ∑ j, (y j * Real.exp (-(t * z j)) / ∑ i, y i * Real.exp (-(t * z i))) * z j
          + (1 / t) * bregman (entropy (n := n))
              (fun j => y j * Real.exp (-(t * z j)) / ∑ i, y i * Real.exp (-(t * z i))) y
        ≤ ∑ j, u j * z j + (1 / t) * bregman (entropy (n := n)) u y := by sorry

end BeckTeboulleMD.EMDA
Source
Beck & Teboulle, Mirror descent and nonlinear projected subgradient methods for convex optimization, Oper. Res. Lett. 31 (2003), p. 174, the entropic descent algorithm (EDA) and the sentence preceding it
Human review
  • Endorsed by Shuze Chen · Oct 5, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 5, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me