Smooth Minimization of Non-Smooth Functions (Nesterov, 2004) -- Section 04 -- Part 5

Lean contributors (project-level attribution): Wanli Ma, Zichen Wang.

Source header · Attribution source

The softmax vector belongs to the standard simplex (and its normalizer is positive).

lemma entropySimplex_softmax_den_pos_and_mem (m : ℕ) (μ : ℝ) (s : Fin m → ℝ) (hm : 0 < m) : let Z : ℝ := ∑ j : Fin m, Real.exp (s j / μ) 0 < Z ∧ (fun j : Fin m => Real.exp (s j / μ) / Z) ∈ standardSimplex m := by classical dsimp set Z : ℝ := ∑ j : Fin m, Real.exp (s j / μ) with hZ have hZpos : 0 < Z := by simpa [hZ] using entropySimplex_softmax_den_pos (m := m) (μ := μ) (s := s) hm have hZne : Z ≠ 0 := ne_of_gt hZpos refine ⟨hZpos, ?_⟩ refine ⟨?_, ?_⟩ · intro j have : 0 < Real.exp (s j / μ) / Z := div_pos (Real.exp_pos (s j / μ)) hZpos exact le_of_lt (by simpa [hZ] using this) · have hsum_div : (∑ j : Fin m, Real.exp (s j / μ) / Z) = (∑ j : Fin m, Real.exp (s j / μ)) / Z := by simpa using (Finset.sum_div (s := (Finset.univ : Finset (Fin m))) (f := fun j => Real.exp (s j / μ)) (a := Z)).symm calc (∑ j : Fin m, Real.exp (s j / μ) / Z) = (∑ j : Fin m, Real.exp (s j / μ)) / Z := hsum_div _ = Z / Z := by simp [hZ] _ = (1 : ℝ) := by simp [hZne]

Scalar inequality underlying KL nonnegativity: for Unknown identifier `u`sorry > 0 : Propu > 0, Unknown identifier `v`sorry ≥ 0 : Propv ≥ 0.

lemma entropySimplex_mul_log_div_ge_sub {u v : ℝ} (hu : 0 < u) (hv : 0 ≤ v) : v * Real.log (v / u) ≥ v - u := by by_cases hv0 : v = 0 · subst hv0 simp [hu.le] · have hvpos : 0 < v := lt_of_le_of_ne hv (Ne.symm hv0) have hx : 0 < u / v := div_pos hu hvpos have hlog : Real.log (u / v) ≤ u / v - 1 := Real.log_le_sub_one_of_pos hx have hv' : 0 < v := hvpos have hmul : v * Real.log (u / v) ≤ v * (u / v - 1) := by exact mul_le_mul_of_nonneg_left hlog (le_of_lt hv') have hmul' : v * (u / v - 1) = u - v := by calc v * (u / v - 1) = v * (u / v) - v := by ring _ = u - v := by simp [mul_div_cancel₀ u hv0] have hbase : -(v * Real.log (u / v)) ≥ v - u := by have : v * Real.log (u / v) ≤ u - v := by simpa [hmul'] using hmul linarith -- rewrite `-log(u/v)` as `log(v/u)` have hloginv : Real.log (v / u) = -Real.log (u / v) := by simpa [inv_div] using (Real.log_inv (u / v)) -- finalize have : v * Real.log (v / u) = -(v * Real.log (u / v)) := by calc v * Real.log (v / u) = v * (-Real.log (u / v)) := by simp [hloginv] _ = -(v * Real.log (u / v)) := by ring simpa [this] using hbase

Rewrite as Unknown identifier `v`sorry * sorry - sorry * sorry : ?m.15v * Unknown identifier `log`log v - Unknown identifier `v`v * Unknown identifier `log`log u (handles Unknown identifier `v`sorry = 0 : Propv = 0 by cases).

lemma entropySimplex_mul_log_div_eq (u v : ℝ) (hu : u ≠ 0) : v * Real.log (v / u) = v * Real.log v - v * Real.log u := by by_cases hv0 : v = 0 · subst hv0 simp · have hv : v ≠ 0 := hv0 simp [Real.log_div hv hu, mul_sub]

Nonnegativity of the KL divergence on the simplex against a positive Unknown identifier `u`u.

lemma entropySimplex_KL_nonneg {m : ℕ} {v u : Fin m → ℝ} (hv : v ∈ standardSimplex m) (hu_pos : ∀ j, 0 < u j) (hu_sum : ∑ j, u j = (1 : ℝ)) : 0 ≤ ∑ j : Fin m, v j * Real.log (v j / u j) := by classical have hv_nonneg : ∀ j, 0 ≤ v j := hv.1 have hv_sum : ∑ j, v j = (1 : ℝ) := hv.2 have hterm : ∀ j : Fin m, v j - u j ≤ v j * Real.log (v j / u j) := by intro j have := entropySimplex_mul_log_div_ge_sub (u := u j) (v := v j) (hu := hu_pos j) (hv := hv_nonneg j) linarith have hsum : (∑ j : Fin m, (v j - u j)) ≤ ∑ j : Fin m, v j * Real.log (v j / u j) := by have : (Finset.univ.sum fun j : Fin m => v j - u j) ≤ (Finset.univ.sum fun j : Fin m => v j * Real.log (v j / u j)) := by refine Finset.sum_le_sum ?_ intro j hj exact hterm j simpa using this have hleft0 : (∑ j : Fin m, (v j - u j)) = 0 := by have hsub : (∑ j : Fin m, (v j - u j)) = (∑ j : Fin m, v j) - (∑ j : Fin m, u j) := by simp [Finset.sum_sub_distrib] calc (∑ j : Fin m, (v j - u j)) = (∑ j : Fin m, v j) - (∑ j : Fin m, u j) := hsub _ = (1 : ℝ) - (1 : ℝ) := by simp [hv_sum, hu_sum] _ = 0 := by ring simpa [hleft0] using hsum

The entropy-regularized objective at the softmax point equals .

lemma entropySimplex_obj_at_softmax (m : ℕ) (μ : ℝ) (s : Fin m → ℝ) (hm : 0 < m) (hμ : 0 < μ) : let Z : ℝ := ∑ j : Fin m, Real.exp (s j / μ) let uμ : Fin m → ℝ := fun j => Real.exp (s j / μ) / Z (∑ j, uμ j * s j) - μ * (∑ j, uμ j * Real.log (uμ j)) = μ * Real.log Z := by classical dsimp set Z : ℝ := ∑ j : Fin m, Real.exp (s j / μ) with hZ set uμ : Fin m → ℝ := fun j => Real.exp (s j / μ) / Z with huμ have hZpos : 0 < Z := by simpa [hZ] using entropySimplex_softmax_den_pos (m := m) (μ := μ) (s := s) hm have hZne : Z ≠ 0 := ne_of_gt hZpos have hu_mem : uμ ∈ standardSimplex m := by have h := entropySimplex_softmax_den_pos_and_mem (m := m) (μ := μ) (s := s) hm simpa [hZ, huμ] using h.2 have hu_sum : ∑ j : Fin m, uμ j = (1 : ℝ) := hu_mem.2 have hμne : μ ≠ 0 := ne_of_gt hμ have hlog_u : ∀ j : Fin m, Real.log (uμ j) = s j / μ - Real.log Z := by intro j have hexp : Real.exp (s j / μ) ≠ 0 := Real.exp_ne_zero (s j / μ) simp [huμ, Real.log_div hexp hZne, Real.log_exp, sub_eq_add_neg] have hsum_log : (∑ j : Fin m, uμ j * Real.log (uμ j)) = (∑ j : Fin m, uμ j * (s j / μ)) - Real.log Z := by calc (∑ j : Fin m, uμ j * Real.log (uμ j)) = ∑ j : Fin m, uμ j * (s j / μ - Real.log Z) := by refine Finset.sum_congr rfl ?_ intro j hj simp [hlog_u j] _ = ∑ j : Fin m, (uμ j * (s j / μ) - uμ j * Real.log Z) := by refine Finset.sum_congr rfl ?_ intro j hj ring _ = (∑ j : Fin m, uμ j * (s j / μ)) - (∑ j : Fin m, uμ j * Real.log Z) := by simp [Finset.sum_sub_distrib] _ = (∑ j : Fin m, uμ j * (s j / μ)) - (Real.log Z * (∑ j : Fin m, uμ j)) := by congr 1 calc (∑ j : Fin m, uμ j * Real.log Z) = ∑ j : Fin m, (Real.log Z) * uμ j := by refine Finset.sum_congr rfl ?_ intro j hj ring _ = (Real.log Z) * (∑ j : Fin m, uμ j) := by simp [Finset.mul_sum] _ = (∑ j : Fin m, uμ j * (s j / μ)) - Real.log Z := by simp [hu_sum] have hmu_cancel : μ * (∑ j : Fin m, uμ j * (s j / μ)) = ∑ j : Fin m, uμ j * s j := by calc μ * (∑ j : Fin m, uμ j * (s j / μ)) = ∑ j : Fin m, μ * (uμ j * (s j / μ)) := by simp [Finset.mul_sum] _ = ∑ j : Fin m, uμ j * s j := by refine Finset.sum_congr rfl ?_ intro j hj calc μ * (uμ j * (s j / μ)) = uμ j * (μ * (s j / μ)) := by ring _ = uμ j * s j := by simp [mul_div_cancel₀ (s j) hμne] calc (∑ j : Fin m, uμ j * s j) - μ * (∑ j : Fin m, uμ j * Real.log (uμ j)) = (∑ j : Fin m, uμ j * s j) - μ * ((∑ j : Fin m, uμ j * (s j / μ)) - Real.log Z) := by simp [hsum_log] _ = (∑ j : Fin m, uμ j * s j) - μ * (∑ j : Fin m, uμ j * (s j / μ)) + μ * Real.log Z := by ring _ = μ * Real.log Z := by -- the linear term cancels with the entropy term using `μ ≠ 0` simp [hmu_cancel]

Any point of the simplex achieves objective value at most the softmax value .

lemma entropySimplex_obj_le_softmax (m : ℕ) (μ : ℝ) (s : Fin m → ℝ) (hm : 0 < m) (hμ : 0 < μ) : let Z : ℝ := ∑ j : Fin m, Real.exp (s j / μ) let _uμ : Fin m → ℝ := fun j => Real.exp (s j / μ) / Z ∀ v ∈ standardSimplex m, (∑ j, v j * s j) - μ * (∑ j, v j * Real.log (v j)) ≤ μ * Real.log Z := by classical dsimp set Z : ℝ := ∑ j : Fin m, Real.exp (s j / μ) with hZ set uμ : Fin m → ℝ := fun j => Real.exp (s j / μ) / Z with huμ have hZpos : 0 < Z := by simpa [hZ] using entropySimplex_softmax_den_pos (m := m) (μ := μ) (s := s) hm have hZne : Z ≠ 0 := ne_of_gt hZpos have hu_mem : uμ ∈ standardSimplex m := by have h := entropySimplex_softmax_den_pos_and_mem (m := m) (μ := μ) (s := s) hm simpa [hZ, huμ] using h.2 have hu_sum : ∑ j : Fin m, uμ j = (1 : ℝ) := hu_mem.2 have hu_pos : ∀ j : Fin m, 0 < uμ j := by intro j have : 0 < Real.exp (s j / μ) / Z := div_pos (Real.exp_pos (s j / μ)) hZpos simpa [huμ] using this have hμne : μ ≠ 0 := ne_of_gt hμ have hlog_u : ∀ j : Fin m, Real.log (uμ j) = s j / μ - Real.log Z := by intro j have hexp : Real.exp (s j / μ) ≠ 0 := Real.exp_ne_zero (s j / μ) simp [huμ, Real.log_div hexp hZne, Real.log_exp, sub_eq_add_neg] have hs_div : ∀ j : Fin m, s j / μ = Real.log (uμ j) + Real.log Z := by intro j have := hlog_u j linarith intro v hv have hv_sum : ∑ j : Fin m, v j = (1 : ℝ) := hv.2 have hlin : (∑ j : Fin m, v j * s j) = μ * (∑ j : Fin m, v j * (s j / μ)) := by calc (∑ j : Fin m, v j * s j) = ∑ j : Fin m, v j * (μ * (s j / μ)) := by refine Finset.sum_congr rfl ?_ intro j hj simp [mul_div_cancel₀ (s j) hμne, mul_comm] _ = ∑ j : Fin m, μ * (v j * (s j / μ)) := by refine Finset.sum_congr rfl ?_ intro j hj ring _ = μ * (∑ j : Fin m, v j * (s j / μ)) := by simp [Finset.mul_sum] have hsum_sdiv : (∑ j : Fin m, v j * (s j / μ)) = (∑ j : Fin m, v j * Real.log (uμ j)) + Real.log Z := by calc (∑ j : Fin m, v j * (s j / μ)) = ∑ j : Fin m, v j * (Real.log (uμ j) + Real.log Z) := by refine Finset.sum_congr rfl ?_ intro j hj simp [hs_div j] _ = ∑ j : Fin m, (v j * Real.log (uμ j) + v j * Real.log Z) := by refine Finset.sum_congr rfl ?_ intro j hj ring _ = (∑ j : Fin m, v j * Real.log (uμ j)) + (∑ j : Fin m, v j * Real.log Z) := by simp [Finset.sum_add_distrib] _ = (∑ j : Fin m, v j * Real.log (uμ j)) + (Real.log Z * (∑ j : Fin m, v j)) := by congr 1 calc (∑ j : Fin m, v j * Real.log Z) = ∑ j : Fin m, (Real.log Z) * v j := by refine Finset.sum_congr rfl ?_ intro j hj ring _ = (Real.log Z) * (∑ j : Fin m, v j) := by simp [Finset.mul_sum] _ = (∑ j : Fin m, v j * Real.log (uμ j)) + Real.log Z := by simp [hv_sum] have hsum_logdiv : (∑ j : Fin m, v j * Real.log (v j / uμ j)) = (∑ j : Fin m, v j * Real.log (v j)) - (∑ j : Fin m, v j * Real.log (uμ j)) := by calc (∑ j : Fin m, v j * Real.log (v j / uμ j)) = ∑ j : Fin m, (v j * Real.log (v j) - v j * Real.log (uμ j)) := by refine Finset.sum_congr rfl ?_ intro j hj have huj : uμ j ≠ 0 := ne_of_gt (hu_pos j) simp [entropySimplex_mul_log_div_eq (u := uμ j) (v := v j) huj] _ = (∑ j : Fin m, v j * Real.log (v j)) - (∑ j : Fin m, v j * Real.log (uμ j)) := by simp [Finset.sum_sub_distrib] have hkl : 0 ≤ ∑ j : Fin m, v j * Real.log (v j / uμ j) := by exact entropySimplex_KL_nonneg (hv := hv) (hu_pos := hu_pos) (hu_sum := hu_sum) have hdiff : 0 ≤ μ * Real.log Z - ((∑ j : Fin m, v j * s j) - μ * (∑ j : Fin m, v j * Real.log (v j))) := by have : μ * Real.log Z - ((∑ j : Fin m, v j * s j) - μ * (∑ j : Fin m, v j * Real.log (v j))) = μ * (∑ j : Fin m, v j * Real.log (v j / uμ j)) := by calc μ * Real.log Z - ((∑ j : Fin m, v j * s j) - μ * (∑ j : Fin m, v j * Real.log (v j))) = μ * Real.log Z - (∑ j : Fin m, v j * s j) + μ * (∑ j : Fin m, v j * Real.log (v j)) := by ring _ = μ * Real.log Z - μ * (∑ j : Fin m, v j * (s j / μ)) + μ * (∑ j : Fin m, v j * Real.log (v j)) := by simp [hlin] _ = μ * (Real.log Z - (∑ j : Fin m, v j * (s j / μ)) + (∑ j : Fin m, v j * Real.log (v j))) := by ring _ = μ * ((∑ j : Fin m, v j * Real.log (v j)) - (∑ j : Fin m, v j * Real.log (uμ j))) := by congr 1 simp [hsum_sdiv] ring _ = μ * (∑ j : Fin m, v j * Real.log (v j / uμ j)) := by simp [hsum_logdiv] have hdiff_nonneg : 0 ≤ μ * (∑ j : Fin m, v j * Real.log (v j / uμ j)) := mul_nonneg (le_of_lt hμ) hkl simpa [this] using hdiff_nonneg exact (sub_nonneg.mp hdiff)

Lemma 1.4.1.2. For Unknown identifier `μ`sorry > 0 : Propμ > 0 and failed to synthesize instance of type class Membership ?m.1 Type Hint: Type class instance resolution failures can be inspected with the `set_option trace.Meta.synthInstance true` command.Unknown identifier `s`s ∈ ℝ^Unknown identifier `m`m, define (4.13). The maximizer has entries (4.14), and .

theorem entropySimplex_softmax_maximizer (m : ℕ) (μ : ℝ) (s : Fin m → ℝ) (hm : 0 < m) (hμ : 0 < μ) : let Φμ : ℝ := sSup ((fun u => (∑ j, u j * s j) - μ * (∑ j, u j * Real.log (u j))) '' standardSimplex m) let uμ : Fin m → ℝ := fun j => Real.exp (s j / μ) / (∑ l, Real.exp (s l / μ)) uμ ∈ standardSimplex m ∧ (∀ v ∈ standardSimplex m, (∑ j, v j * s j) - μ * (∑ j, v j * Real.log (v j)) ≤ (∑ j, uμ j * s j) - μ * (∑ j, uμ j * Real.log (uμ j))) ∧ Φμ = μ * Real.log (∑ j, Real.exp (s j / μ)) := by classical dsimp set Z : ℝ := ∑ j : Fin m, Real.exp (s j / μ) with hZ set uμ : Fin m → ℝ := fun j => Real.exp (s j / μ) / Z with huμ have hZpos : 0 < Z := by simpa [hZ] using entropySimplex_softmax_den_pos (m := m) (μ := μ) (s := s) hm have hu_mem : uμ ∈ standardSimplex m := by have h := entropySimplex_softmax_den_pos_and_mem (m := m) (μ := μ) (s := s) hm simpa [hZ, huμ] using h.2 have hu_obj : (∑ j : Fin m, uμ j * s j) - μ * (∑ j : Fin m, uμ j * Real.log (uμ j)) = μ * Real.log Z := by have h := entropySimplex_obj_at_softmax (m := m) (μ := μ) (s := s) hm hμ simpa [hZ, huμ] using h have hupper : ∀ v ∈ standardSimplex m, (∑ j : Fin m, v j * s j) - μ * (∑ j : Fin m, v j * Real.log (v j)) ≤ (∑ j : Fin m, uμ j * s j) - μ * (∑ j : Fin m, uμ j * Real.log (uμ j)) := by intro v hv have hv_le : (∑ j : Fin m, v j * s j) - μ * (∑ j : Fin m, v j * Real.log (v j)) ≤ μ * Real.log Z := by have h := entropySimplex_obj_le_softmax (m := m) (μ := μ) (s := s) hm hμ simpa [hZ, huμ] using h v hv -- rewrite the softmax objective as `μ * log Z` simpa [hu_obj] using hv_le refine ⟨by simpa [huμ, hZ] using hu_mem, hupper, ?_⟩ -- identify the supremum with the objective value at `uμ` set S : Set ℝ := ((fun u : Fin m → ℝ => (∑ j : Fin m, u j * s j) - μ * (∑ j : Fin m, u j * Real.log (u j))) '' standardSimplex m) with hS have hS_nonempty : S.Nonempty := by refine ⟨(∑ j : Fin m, uμ j * s j) - μ * (∑ j : Fin m, uμ j * Real.log (uμ j)), ?_⟩ refine ⟨uμ, ?_, rfl⟩ simpa [hS] using hu_mem have hS_bdd : BddAbove S := by refine ⟨(∑ j : Fin m, uμ j * s j) - μ * (∑ j : Fin m, uμ j * Real.log (uμ j)), ?_⟩ intro y hy rcases hy with ⟨v, hv, rfl⟩ exact hupper v hv have hsSup_eq : sSup S = (∑ j : Fin m, uμ j * s j) - μ * (∑ j : Fin m, uμ j * Real.log (uμ j)) := by refine le_antisymm ?_ ?_ · -- `sSup S ≤ obj(uμ)` since `obj(uμ)` is an upper bound on the image refine csSup_le hS_nonempty ?_ intro y hy rcases hy with ⟨v, hv, rfl⟩ exact hupper v hv · -- `obj(uμ) ≤ sSup S` since `obj(uμ) ∈ S` refine le_csSup hS_bdd ?_ refine ⟨uμ, ?_, rfl⟩ simpa [hS] using hu_mem -- finish by evaluating at the softmax point have : sSup S = μ * Real.log Z := by simp [hsSup_eq, hu_obj] simpa [hS, hZ] using this

Evaluate a continuous linear functional as a coordinate sum against the standard basis vectors .

lemma matrixGame_contLin_apply_eq_sum_basis (m : ℕ) (ℓ : (Fin m → ℝ) →L[ℝ] ℝ) (u : Fin m → ℝ) : ℓ u = ∑ j : Fin m, u j * ℓ (fun k : Fin m => if k = j then (1 : ℝ) else 0) := by classical have hu : u = ∑ j : Fin m, u j • (fun k : Fin m => if k = j then (1 : ℝ) else 0) := by -- `pi_eq_sum_univ` uses the basis `fun k => if j = k then 1 else 0`; rewrite using `eq_comm`. simpa [eq_comm] using (pi_eq_sum_univ (x := u) (R := ℝ)) -- rewrite `u`, then push `ℓ` through the sum and scalars rw [hu] -- use `map_sum` for additive monoid homs have hmap := (map_sum ℓ (fun j : Fin m => u j • (fun k : Fin m => if k = j then (1 : ℝ) else 0)) (Finset.univ : Finset (Fin m))) -- clean up the `∑ x ∈ univ` binders and rewrite `•` as multiplication on `ℝ` simp [hmap, smul_eq_mul]

On the standard simplex Unknown identifier `Δ_m`Δ_m, rewrite the smoothed matrix-game integrand as the entropy objective with , absorbing the constant term via .

lemma matrixGame_entropy_objective_rewrite (m : ℕ) (μ : ℝ) (ℓ : (Fin m → ℝ) →L[ℝ] ℝ) (b : Fin m → ℝ) (u : Fin m → ℝ) (hu : u ∈ standardSimplex m) : (ℓ u + (∑ j : Fin m, b j * u j) - μ * (Real.log (m : ℝ) + ∑ j : Fin m, u j * Real.log (u j))) = (∑ j : Fin m, u j * (ℓ (fun k : Fin m => if k = j then (1 : ℝ) else 0) + b j - μ * Real.log (m : ℝ))) - μ * (∑ j : Fin m, u j * Real.log (u j)) := by classical have hℓ : ℓ u = ∑ j : Fin m, u j * ℓ (fun k : Fin m => if k = j then (1 : ℝ) else 0) := by simpa using matrixGame_contLin_apply_eq_sum_basis (m := m) (ℓ := ℓ) (u := u) have hu_sum : (∑ j : Fin m, u j) = (1 : ℝ) := hu.2 have hbu : (∑ j : Fin m, b j * u j) = ∑ j : Fin m, u j * b j := by simp [mul_comm] have hconst : (∑ j : Fin m, u j * (μ * Real.log (m : ℝ))) = μ * Real.log (m : ℝ) := by calc (∑ j : Fin m, u j * (μ * Real.log (m : ℝ))) = ∑ j : Fin m, (μ * Real.log (m : ℝ)) * u j := by simp [mul_comm] _ = (μ * Real.log (m : ℝ)) * (∑ j : Fin m, u j) := by simp [Finset.mul_sum] _ = μ * Real.log (m : ℝ) := by simp [hu_sum] have hsum : (∑ j : Fin m, u j * (ℓ (fun k : Fin m => if k = j then (1 : ℝ) else 0) + b j - μ * Real.log (m : ℝ))) = (∑ j : Fin m, u j * ℓ (fun k : Fin m => if k = j then (1 : ℝ) else 0)) + (∑ j : Fin m, u j * b j) - μ * Real.log (m : ℝ) := by calc (∑ j : Fin m, u j * (ℓ (fun k : Fin m => if k = j then (1 : ℝ) else 0) + b j - μ * Real.log (m : ℝ))) = ∑ j : Fin m, (u j * ℓ (fun k : Fin m => if k = j then (1 : ℝ) else 0) + u j * b j - u j * (μ * Real.log (m : ℝ))) := by refine Finset.sum_congr rfl ?_ intro j hj ring _ = (∑ j : Fin m, u j * ℓ (fun k : Fin m => if k = j then (1 : ℝ) else 0)) + (∑ j : Fin m, u j * b j) - (∑ j : Fin m, u j * (μ * Real.log (m : ℝ))) := by simp [Finset.sum_add_distrib, sub_eq_add_neg, add_left_comm, add_comm] _ = (∑ j : Fin m, u j * ℓ (fun k : Fin m => if k = j then (1 : ℝ) else 0)) + (∑ j : Fin m, u j * b j) - μ * Real.log (m : ℝ) := by simp [hconst] -- rewrite the linear terms and expand `-μ * (log m + ...)` calc (ℓ u + (∑ j : Fin m, b j * u j) - μ * (Real.log (m : ℝ) + ∑ j : Fin m, u j * Real.log (u j))) = (∑ j : Fin m, u j * ℓ (fun k : Fin m => if k = j then (1 : ℝ) else 0)) + (∑ j : Fin m, u j * b j) - μ * Real.log (m : ℝ) - μ * (∑ j : Fin m, u j * Real.log (u j)) := by simp [hℓ, hbu, mul_add, sub_eq_add_neg, add_assoc, add_left_comm, add_comm] _ = (∑ j : Fin m, u j * (ℓ (fun k : Fin m => if k = j then (1 : ℝ) else 0) + b j - μ * Real.log (m : ℝ))) - μ * (∑ j : Fin m, u j * Real.log (u j)) := by -- use `hsum` to compress the linear part have hsum' : (∑ j : Fin m, u j * ℓ (fun k : Fin m => if k = j then (1 : ℝ) else 0)) + (∑ j : Fin m, u j * b j) - μ * Real.log (m : ℝ) = ∑ j : Fin m, u j * (ℓ (fun k : Fin m => if k = j then (1 : ℝ) else 0) + b j - μ * Real.log (m : ℝ)) := by simpa using hsum.symm -- rewrite the linear part using `hsum'` simpa using congrArg (fun z => z - μ * (∑ j : Fin m, u j * Real.log (u j))) hsum'

Rewrite the log-sum-exp shift for Unknown identifier `m`sorry > 0 : Propm > 0 and Unknown identifier `μ`sorry ≠ 0 : Propμ ≠ 0.

lemma matrixGame_logsumexp_shift_by_log_m (m : ℕ) (μ : ℝ) (t : Fin m → ℝ) (hm : 0 < m) (hμ : μ ≠ 0) : (∑ j : Fin m, Real.exp ((t j - μ * Real.log (m : ℝ)) / μ)) = (1 / (m : ℝ)) * ∑ j : Fin m, Real.exp (t j / μ) := by classical have hmR : (0 : ℝ) < (m : ℝ) := by exact_mod_cast hm have hdiv : ∀ j : Fin m, (t j - μ * Real.log (m : ℝ)) / μ = t j / μ - Real.log (m : ℝ) := by intro j calc (t j - μ * Real.log (m : ℝ)) / μ = t j / μ - (μ * Real.log (m : ℝ)) / μ := by simp [sub_div] _ = t j / μ - Real.log (m : ℝ) := by simp [mul_div_cancel_left₀ (b := Real.log (m : ℝ)) hμ] calc (∑ j : Fin m, Real.exp ((t j - μ * Real.log (m : ℝ)) / μ)) = ∑ j : Fin m, Real.exp (t j / μ - Real.log (m : ℝ)) := by refine Finset.sum_congr rfl ?_ intro j hj simp [hdiv j] _ = ∑ j : Fin m, Real.exp (t j / μ) / (m : ℝ) := by refine Finset.sum_congr rfl ?_ intro j hj have : Real.exp (Real.log (m : ℝ)) = (m : ℝ) := by simpa using (Real.exp_log hmR) simp [Real.exp_sub, this] _ = (∑ j : Fin m, Real.exp (t j / μ)) / (m : ℝ) := by simpa using (Finset.sum_div (s := (Finset.univ : Finset (Fin m))) (f := fun j : Fin m => Real.exp (t j / μ)) (a := (m : ℝ))).symm _ = (1 / (m : ℝ)) * ∑ j : Fin m, Real.exp (t j / μ) := by simp [div_eq_mul_inv, mul_comm]

Proposition 1.4.1.3. In the matrix-game setting (4.10), under the entropy-distance setup of Lemma 1.4.1.2, the smoothed objective (4.1) for the primal problem is , with the minimization (eq:matrixgame_smooth).

theorem matrixGame_smoothedObjective_explicit (n m : ℕ) (A : (Fin n → ℝ) →L[ℝ] ((Fin m → ℝ) →L[ℝ] ℝ)) (c : Fin n → ℝ) (b : Fin m → ℝ) (μ : ℝ) (hμ : 0 < μ) : let fhat : (Fin n → ℝ) → ℝ := fun x => ∑ i, c i * x i let phihat : (Fin m → ℝ) → ℝ := fun u => -∑ j, b j * u j let d2 : (Fin m → ℝ) → ℝ := fun u => Real.log (m : ℝ) + ∑ j, u j * Real.log (u j) let fbar : (Fin n → ℝ) → ℝ := SmoothedObjective (standardSimplex m) A phihat d2 μ fhat fbar = fun x => (∑ i, c i * x i) + μ * Real.log ((1 / (m : ℝ)) * ∑ j, Real.exp (((A x) (fun k => if k = j then (1 : ℝ) else 0) + b j) / μ)) := by classical funext x by_cases hm0 : m = 0 · subst hm0 -- `Δ_0` is empty, so the smoothed max-term is `sSup ∅ = 0`, and the RHS sum is empty. have hsimplex0 : (standardSimplex 0 : Set (Fin 0 → ℝ)) = ∅ := by ext u simp [standardSimplex] simp [SmoothedObjective, SmoothedMaxFunction, Real.sSup_empty, standardSimplex] · have hm : 0 < m := Nat.pos_of_ne_zero hm0 have hμne : μ ≠ 0 := ne_of_gt hμ -- Evaluate the `sSup` in the smoothed max-function via the entropy simplex lemma. have hmax : SmoothedMaxFunction (standardSimplex m) A (fun u => -∑ j : Fin m, b j * u j) (fun u : Fin m → ℝ => Real.log (m : ℝ) + ∑ j : Fin m, u j * Real.log (u j)) μ x = μ * Real.log ((1 / (m : ℝ)) * ∑ j : Fin m, Real.exp (((A x) (fun k : Fin m => if k = j then (1 : ℝ) else 0) + b j) / μ)) := by set t : Fin m → ℝ := fun j : Fin m => (A x) (fun k : Fin m => if k = j then (1 : ℝ) else 0) + b j with ht set s : Fin m → ℝ := fun j : Fin m => t j - μ * Real.log (m : ℝ) with hs have himage : ((fun u : Fin m → ℝ => A x u + (∑ j : Fin m, b j * u j) - μ * (Real.log (m : ℝ) + ∑ j : Fin m, u j * Real.log (u j))) '' standardSimplex m) = ((fun u : Fin m → ℝ => (∑ j : Fin m, u j * s j) - μ * (∑ j : Fin m, u j * Real.log (u j))) '' standardSimplex m) := by refine Set.image_congr ?_ intro u hu have hrewrite := matrixGame_entropy_objective_rewrite (m := m) (μ := μ) (ℓ := (A x)) (b := b) (u := u) hu have hs' : ∀ j : Fin m, s j = (A x) (fun k : Fin m => if k = j then (1 : ℝ) else 0) + b j - μ * Real.log (m : ℝ) := by intro j simp [s, t, sub_eq_add_neg, add_left_comm, add_comm] simpa [hs', sub_eq_add_neg, add_assoc, add_left_comm, add_comm] using hrewrite have hentropy : sSup (((fun u : Fin m → ℝ => (∑ j : Fin m, u j * s j) - μ * (∑ j : Fin m, u j * Real.log (u j))) '' standardSimplex m)) = μ * Real.log (∑ j : Fin m, Real.exp (s j / μ)) := by have h := entropySimplex_softmax_maximizer (m := m) (μ := μ) (s := s) hm hμ simpa using h.2.2 have hshift : (∑ j : Fin m, Real.exp (s j / μ)) = (1 / (m : ℝ)) * ∑ j : Fin m, Real.exp (((A x) (fun k : Fin m => if k = j then (1 : ℝ) else 0) + b j) / μ) := by have hterm : (∑ j : Fin m, Real.exp (s j / μ)) = (1 / (m : ℝ)) * ∑ j : Fin m, Real.exp (t j / μ) := by have : (∑ j : Fin m, Real.exp (s j / μ)) = (∑ j : Fin m, Real.exp ((t j - μ * Real.log (m : ℝ)) / μ)) := by refine Finset.sum_congr rfl ?_ intro j hj simp [s] -- apply the shift lemma and rewrite `t` simpa [this, div_eq_mul_inv, one_div, mul_assoc, mul_left_comm, mul_comm] using (matrixGame_logsumexp_shift_by_log_m (m := m) (μ := μ) (t := t) hm hμne) -- unfold `t` in the RHS simp [t, hterm] simp [SmoothedMaxFunction, himage, hentropy, hshift] simp [SmoothedObjective, hmax]