Smooth Minimization of Non-Smooth Functions (Nesterov, 2004) -- Section 05 -- Part 4

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

Source header · Attribution source

open scoped BigOperators

Rewrite the entropy V_Q.{u_1} {E : Type u_1} [NormedAddCommGroup E] [NormedSpace ℝ E] [FiniteDimensional ℝ E] (Q : Set E) (d : E → ℝ) (z : ↑Q) (g : Module.Dual ℝ E) : ↑QV_Q objective on the simplex.

lemma V_Q_entropy_objective_rewrite_on_simplex (n : ℕ) (z : standardSimplex n) (g : Module.Dual ℝ (Fin n → ℝ)) (hz_pos : ∀ i, 0 < z.1 i) : let d : (Fin n → ℝ) → ℝ := fun x => Real.log (n : ℝ) + ∑ i, x i * Real.log (x i) let gcoord : Fin n → ℝ := fun i => g (fun j => if j = i then (1 : ℝ) else 0) ∀ x ∈ standardSimplex n, DualPairing g (x - z) + bregmanDistance d z x = (∑ i, x i * Real.log (x i)) + ∑ i, x i * (gcoord i - Real.log (z.1 i)) - ∑ i, z.1 i * gcoord i := by classical intro d gcoord x hx have hpair : DualPairing g (x - z.1) = (∑ i : Fin n, x i * gcoord i) - ∑ i : Fin n, z.1 i * gcoord i := by have hpair' : DualPairing g (x - z.1) = ∑ i : Fin n, gcoord i * (x i - z.1 i) := by simpa [gcoord] using (DualPairing_eq_sum_gcoord_standardBasis (n := n) g (x - z.1)) calc DualPairing g (x - z.1) = ∑ i : Fin n, gcoord i * (x i - z.1 i) := hpair' _ = (∑ i : Fin n, gcoord i * x i) - ∑ i : Fin n, gcoord i * z.1 i := by simp [mul_sub, Finset.sum_sub_distrib] _ = (∑ i : Fin n, x i * gcoord i) - ∑ i : Fin n, z.1 i * gcoord i := by simp [mul_comm] have hbreg : bregmanDistance d z x = (∑ i : Fin n, x i * Real.log (x i)) - ∑ i : Fin n, x i * Real.log (z.1 i) := by have hbreg' := bregmanDistance_entropy_eq_sum_mul_log_div_on_simplex (n := n) (z := z) (x := x) hx hz_pos have hz_ne : ∀ i, z.1 i ≠ 0 := fun i => ne_of_gt (hz_pos i) calc bregmanDistance d z x = ∑ i, x i * Real.log (x i / z.1 i) := by simpa [d] using hbreg' _ = ∑ i, (x i * Real.log (x i) - x i * Real.log (z.1 i)) := by refine Finset.sum_congr rfl ?_ intro i hi simpa using (entropySimplex_mul_log_div_eq (u := z.1 i) (v := x i) (hz_ne i)) _ = (∑ i : Fin n, x i * Real.log (x i)) - ∑ i : Fin n, x i * Real.log (z.1 i) := by simp [Finset.sum_sub_distrib] have hlin : ∑ i : Fin n, x i * (gcoord i - Real.log (z.1 i)) = (∑ i : Fin n, x i * gcoord i) - ∑ i : Fin n, x i * Real.log (z.1 i) := by calc ∑ i : Fin n, x i * (gcoord i - Real.log (z.1 i)) = ∑ i : Fin n, (x i * gcoord i - x i * Real.log (z.1 i)) := by refine Finset.sum_congr rfl ?_ intro i hi ring _ = (∑ i : Fin n, x i * gcoord i) - ∑ i : Fin n, x i * Real.log (z.1 i) := by simp [Finset.sum_sub_distrib] calc DualPairing g (x - z) + bregmanDistance d z x = (∑ i : Fin n, x i * gcoord i) - ∑ i : Fin n, z.1 i * gcoord i + ((∑ i : Fin n, x i * Real.log (x i)) - ∑ i : Fin n, x i * Real.log (z.1 i)) := by simp [hpair, hbreg] _ = (∑ i : Fin n, x i * Real.log (x i)) + ((∑ i : Fin n, x i * gcoord i) - ∑ i : Fin n, x i * Real.log (z.1 i)) - ∑ i : Fin n, z.1 i * gcoord i := by ring _ = (∑ i : Fin n, x i * Real.log (x i)) + ∑ i : Fin n, x i * (gcoord i - Real.log (z.1 i)) - ∑ i : Fin n, z.1 i * gcoord i := by simp [hlin]

The softmax candidate minimizes the entropy V_Q.{u_1} {E : Type u_1} [NormedAddCommGroup E] [NormedSpace ℝ E] [FiniteDimensional ℝ E] (Q : Set E) (d : E → ℝ) (z : ↑Q) (g : Module.Dual ℝ E) : ↑QV_Q objective on the simplex.

lemma V_Q_entropy_candidate_isMinOn (n : ℕ) (z : standardSimplex n) (g : Module.Dual ℝ (Fin n → ℝ)) (hz_pos : ∀ i, 0 < z.1 i) : let d : (Fin n → ℝ) → ℝ := fun x => Real.log (n : ℝ) + ∑ i, x i * Real.log (x i) let gcoord : Fin n → ℝ := fun i => g (fun j => if j = i then (1 : ℝ) else 0) let s : Fin n → ℝ := fun i => Real.log (z.1 i) - gcoord i let u : Fin n → ℝ := fun i => Real.exp (s i) / (∑ j, Real.exp (s j)) u ∈ standardSimplex n ∧ IsMinOn (fun x => DualPairing g (x - z) + bregmanDistance d z x) (standardSimplex n) u := by classical intro d gcoord s u have hn : 0 < n := by cases n with | zero => have : (0 : ℝ) = (1 : ℝ) := by simpa using z.property.2 linarith | succ n' => exact Nat.succ_pos n' have hsoft := entropySimplex_softmax_maximizer (m := n) (μ := 1) (s := s) hn (by norm_num) rcases hsoft with ⟨hu_mem, hupper, -⟩ have hu_mem' : u ∈ standardSimplex n := by simpa [u] using hu_mem have hupper' : ∀ v ∈ standardSimplex n, (∑ j : Fin n, v j * s j) - (∑ j : Fin n, v j * Real.log (v j)) ≤ (∑ j : Fin n, u j * s j) - (∑ j : Fin n, u j * Real.log (u j)) := by intro v hv have h := hupper v hv simpa using h let Φ : (Fin n → ℝ) → ℝ := fun x => DualPairing g (x - z) + bregmanDistance d z x have hΦ : ∀ x ∈ standardSimplex n, Φ x = (∑ i, x i * Real.log (x i)) + ∑ i, x i * (gcoord i - Real.log (z.1 i)) - ∑ i, z.1 i * gcoord i := by intro x hx simpa [Φ, d, gcoord] using (V_Q_entropy_objective_rewrite_on_simplex (n := n) (z := z) (g := g) (hz_pos := hz_pos) x hx) have hΦ' : ∀ x ∈ standardSimplex n, Φ x = -((∑ j : Fin n, x j * s j) - (∑ j : Fin n, x j * Real.log (x j))) - ∑ i, z.1 i * gcoord i := by intro x hx have hsum_s : ∑ i : Fin n, x i * (gcoord i - Real.log (z.1 i)) = -∑ i : Fin n, x i * s i := by calc ∑ i : Fin n, x i * (gcoord i - Real.log (z.1 i)) = ∑ i : Fin n, -(x i * (Real.log (z.1 i) - gcoord i)) := by refine Finset.sum_congr rfl ?_ intro i hi ring _ = -∑ i : Fin n, x i * (Real.log (z.1 i) - gcoord i) := by simp [Finset.sum_neg_distrib] _ = -∑ i : Fin n, x i * s i := by simp [s] have hΦx := hΦ x hx calc Φ x = (∑ i, x i * Real.log (x i)) + ∑ i, x i * (gcoord i - Real.log (z.1 i)) - ∑ i, z.1 i * gcoord i := hΦx _ = (∑ i, x i * Real.log (x i)) + (-∑ i : Fin n, x i * s i) - ∑ i, z.1 i * gcoord i := by simp [hsum_s] _ = (∑ i, x i * Real.log (x i)) - ∑ i : Fin n, x i * s i - ∑ i, z.1 i * gcoord i := by ring _ = -((∑ j : Fin n, x j * s j) - (∑ j : Fin n, x j * Real.log (x j))) - ∑ i, z.1 i * gcoord i := by ring have hmin : IsMinOn Φ (standardSimplex n) u := by intro v hv have hΨ : -((∑ j : Fin n, u j * s j) - (∑ j : Fin n, u j * Real.log (u j))) ≤ -((∑ j : Fin n, v j * s j) - (∑ j : Fin n, v j * Real.log (v j))) := by have h := hupper' v hv linarith have hconst := add_le_add_right hΨ (-(∑ i : Fin n, z.1 i * gcoord i)) have hΦu := hΦ' u hu_mem' have hΦv := hΦ' v hv simpa [hΦu, hΦv] using hconst exact ⟨hu_mem', hmin⟩

The entropy V_Q.{u_1} {E : Type u_1} [NormedAddCommGroup E] [NormedSpace ℝ E] [FiniteDimensional ℝ E] (Q : Set E) (d : E → ℝ) (z : ↑Q) (g : Module.Dual ℝ E) : ↑QV_Q objective is strictly convex on the simplex.

lemma V_Q_entropy_objective_strictConvexOn (n : ℕ) (z : standardSimplex n) (g : Module.Dual ℝ (Fin n → ℝ)) : let d : (Fin n → ℝ) → ℝ := fun x => Real.log (n : ℝ) + ∑ i, x i * Real.log (x i) StrictConvexOn ℝ (standardSimplex n) (fun x => DualPairing g (x - z) + bregmanDistance d z x) := by classical intro d have hconvex : Convex ℝ (standardSimplex n) := by simpa [standardSimplex_eq_stdSimplex] using (convex_stdSimplex ℝ (Fin n)) have hstrong : StrongConvexOn (standardSimplex n) 1 d := by have h := (matrixGame_entropy_prox_parameters (n := n) (m := n)) simpa [d] using h.1 have hstrict : StrictConvexOn ℝ (standardSimplex n) d := StrongConvexOn.strictConvexOn hstrong (by norm_num) let s : Module.Dual ℝ (Fin n → ℝ) := g - (fderiv ℝ d z.1).toLinearMap have hlin : ConvexOn ℝ (standardSimplex n) (fun x => DualPairing s (x - z.1)) := by simpa using (section03_convex_dualpairing_sub (hQ_convex := hconvex) s z.1) have hstrict' : StrictConvexOn ℝ (standardSimplex n) (fun x => d x + DualPairing s (x - z.1)) := by exact StrictConvexOn.add_convexOn hstrict hlin have hstrict'' : StrictConvexOn ℝ (standardSimplex n) (fun x => (d x + DualPairing s (x - z.1)) + (-d z.1)) := by simpa [sub_eq_add_neg] using (StrictConvexOn.add_const hstrict' (-d z.1)) have hrewrite : (fun x => DualPairing g (x - z) + bregmanDistance d z x) = fun x => (d x + DualPairing s (x - z.1)) + (-d z.1) := by funext x simp [bregmanDistance, DualPairing, s, sub_eq_add_neg, add_assoc, add_left_comm, add_comm, map_add, map_neg] simpa [hrewrite] using hstrict''

Proposition 1.5.3.1. Let Unknown identifier `Q`sorry = sorry : PropQ = Unknown identifier `Δ_n`Δ_n and let the prox-function be the entropy distance . Then for Unknown identifier `z`sorry ∈ sorry : Propz ∈ Unknown identifier `Δ_n`Δ_n 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 `g`g ∈ ℝ^Unknown identifier `n`n, the mapping from Definition 1.5.3.1 has the explicit form , (equation (5.7)).

theorem V_Q_entropy_simplex_explicit (n : ℕ) (z : standardSimplex n) (g : Module.Dual ℝ (Fin n → ℝ)) (hz_pos : ∀ i, 0 < z.1 i) : let d : (Fin n → ℝ) → ℝ := fun x => Real.log (n : ℝ) + ∑ i, x i * Real.log (x i) let gcoord : Fin n → ℝ := fun i => g (fun j => if j = i then (1 : ℝ) else 0) ∀ i : Fin n, (V_Q (standardSimplex n) d z g : Fin n → ℝ) i = z.1 i * Real.exp (-gcoord i) / (∑ j, z.1 j * Real.exp (-gcoord j)) := by classical intro d gcoord i let s : Fin n → ℝ := fun j => Real.log (z.1 j) - gcoord j let u : Fin n → ℝ := fun j => Real.exp (s j) / (∑ k, Real.exp (s k)) have hu_min : u ∈ standardSimplex n ∧ IsMinOn (fun x => DualPairing g (x - z) + bregmanDistance d z x) (standardSimplex n) u := by simpa [d, gcoord, s, u] using (V_Q_entropy_candidate_isMinOn (n := n) (z := z) (g := g) (hz_pos := hz_pos)) have hmin_exists : ∃ x : standardSimplex n, IsMinOn (fun x : Fin n → ℝ => DualPairing g (x - z) + bregmanDistance d z x) (standardSimplex n) x := by refine ⟨⟨u, hu_min.1⟩, ?_⟩ simpa using hu_min.2 have hmin_VQ : IsMinOn (fun x : Fin n → ℝ => DualPairing g (x - z) + bregmanDistance d z x) (standardSimplex n) (V_Q (standardSimplex n) d z g) := by simpa using (V_Q_spec_isMinOn (Q := standardSimplex n) (d := d) z g hmin_exists) have hstrict : StrictConvexOn ℝ (standardSimplex n) (fun x => DualPairing g (x - z) + bregmanDistance d z x) := by simpa [d] using (V_Q_entropy_objective_strictConvexOn (n := n) (z := z) (g := g)) have hVQ_eq_u : (V_Q (standardSimplex n) d z g : Fin n → ℝ) = u := by refine StrictConvexOn.eq_of_isMinOn hstrict hmin_VQ hu_min.2 ?_ ?_ · exact (V_Q (standardSimplex n) d z g).property · exact hu_min.1 have hsimp : ∀ j, Real.exp (s j) = z.1 j * Real.exp (-gcoord j) := by intro j have hzj : 0 < z.1 j := hz_pos j calc Real.exp (s j) = Real.exp (Real.log (z.1 j) - gcoord j) := by rfl _ = Real.exp (Real.log (z.1 j)) / Real.exp (gcoord j) := by simp [Real.exp_sub] _ = z.1 j / Real.exp (gcoord j) := by simp [Real.exp_log hzj] _ = z.1 j * Real.exp (-gcoord j) := by simp [Real.exp_neg, div_eq_mul_inv] have hdenom : ∑ j, Real.exp (s j) = ∑ j, z.1 j * Real.exp (-gcoord j) := by refine Finset.sum_congr rfl ?_ intro j hj exact hsimp j have hu_i : u i = z.1 i * Real.exp (-gcoord i) / (∑ j, z.1 j * Real.exp (-gcoord j)) := by simp [u, hsimp] simp [hVQ_eq_u, hu_i]

Support-plane refinement of R_k.{u_1} {E : Type u_1} [SeminormedAddCommGroup E] [NormedSpace ℝ E] [FiniteDimensional ℝ E] (Q : Set E) (f d : E → ℝ) (L σ : ℝ) (α : ℕ → ℝ) (xSeq ySeq : ℕ → ↑Q) (k : ℕ) : PropR_k at for the modified update.

lemma section05_modified_Rk_support_at_xk1 {E : Type*} [NormedAddCommGroup E] [NormedSpace ℝ E] [FiniteDimensional ℝ E] {Q : Set E} {f d : E → ℝ} {L σ : ℝ} (α : ℕ → ℝ) (xSeq ySeq : ℕ → Q) (k : ℕ) (hQ_convex : Convex ℝ Q) (hf_convex : ConvexOn ℝ Q f) (hf_diff : ∀ x ∈ Q, DifferentiableAt ℝ f x) (hα_pos : ∀ k, 0 < α k) (hRk : R_k Q f d L σ α xSeq ySeq k) : let xk1 : E := xSeq (k + 1) let g : Module.Dual ℝ E := (fderiv ℝ f (xSeq (k + 1))).toLinearMap A_k α k * (f xk1 + DualPairing g ((ySeq k : E) - xk1)) ≤ psi_k Q f d L σ α xSeq k := by classical let xk1 : E := xSeq (k + 1) let g : Module.Dual ℝ E := (fderiv ℝ f (xSeq (k + 1))).toLinearMap have hxk1 : (xSeq (k + 1) : E) ∈ Q := (xSeq (k + 1)).property have hyk : (ySeq k : E) ∈ Q := (ySeq k).property have hsupport : f (ySeq k) ≥ f xk1 + DualPairing g ((ySeq k : E) - xk1) := by exact section03_convex_support_fderiv (hQ_convex := hQ_convex) (hf_convex := hf_convex) (u := (ySeq k : E)) (v := (xSeq (k + 1) : E)) hyk hxk1 (hf_diff (xSeq (k + 1)) hxk1) have hA_nonneg : 0 ≤ A_k α k := by unfold A_k exact Finset.sum_nonneg (fun i _ => le_of_lt (hα_pos i)) have hsupport_scaled : A_k α k * (f xk1 + DualPairing g ((ySeq k : E) - xk1)) ≤ A_k α k * f (ySeq k) := by exact mul_le_mul_of_nonneg_left hsupport hA_nonneg simpa [xk1, g] using (le_trans hsupport_scaled hRk)

Combine gradient pairings using the modified update.

lemma section05_modified_dualpairing_combine {E : Type*} [NormedAddCommGroup E] [NormedSpace ℝ E] [FiniteDimensional ℝ E] {Q : Set E} {f d : E → ℝ} {L σ : ℝ} (α : ℕ → ℝ) (xSeq ySeq : ℕ → Q) (k : ℕ) (hA_pos : 0 < A_k α (k + 1)) (hx_update : (xSeq (k + 1) : E) = (α (k + 1) / A_k α (k + 1)) • (z_k Q f d L σ α xSeq k : E) + (1 - α (k + 1) / A_k α (k + 1)) • (ySeq k : E)) (g : Module.Dual ℝ E) (x : E) : A_k α k * DualPairing g ((ySeq k : E) - (xSeq (k + 1) : E)) + α (k + 1) * DualPairing g (x - (xSeq (k + 1) : E)) = α (k + 1) * DualPairing g (x - (z_k Q f d L σ α xSeq k : E)) := by simpa using (section03_dualpairing_combine_update (α := α) (xSeq := xSeq) (ySeq := ySeq) (k := k) (hA_pos := hA_pos) (hx_update := hx_update) g x)

Convert the V_Q.{u_1} {E : Type u_1} [NormedAddCommGroup E] [NormedSpace ℝ E] [FiniteDimensional ℝ E] (Q : Set E) (d : E → ℝ) (z : ↑Q) (g : Module.Dual ℝ E) : ↑QV_Q minimizer into the scaled Bregman inequality.

lemma section05_VQ_scaled_min_property {E : Type*} [NormedAddCommGroup E] [NormedSpace ℝ E] [FiniteDimensional ℝ E] {Q : Set E} {f d : E → ℝ} {L σ : ℝ} (α : ℕ → ℝ) (xSeq : ℕ → Q) (k : ℕ) (g : Module.Dual ℝ E) (hVQ_min : IsMinOn (fun x : E => (L / σ) * bregmanDistance d (z_k Q f d L σ α xSeq k : E) x + α (k + 1) * DualPairing g (x - (z_k Q f d L σ α xSeq k : E))) Q (V_Q Q d (z_k Q f d L σ α xSeq k) (((σ / L) * α (k + 1)) • g) : E)) : ∀ x ∈ Q, (L / σ) * bregmanDistance d (z_k Q f d L σ α xSeq k : E) (V_Q Q d (z_k Q f d L σ α xSeq k) (((σ / L) * α (k + 1)) • g) : E) + α (k + 1) * DualPairing g ((V_Q Q d (z_k Q f d L σ α xSeq k) (((σ / L) * α (k + 1)) • g) : E) - (z_k Q f d L σ α xSeq k : E)) ≤ (L / σ) * bregmanDistance d (z_k Q f d L σ α xSeq k : E) x + α (k + 1) * DualPairing g (x - (z_k Q f d L σ α xSeq k : E)) := by intro x hx exact (isMinOn_iff.mp hVQ_min) x hx

Express via the modified prox update.

lemma section05_yminusx_equals_tau_smul {E : Type*} [NormedAddCommGroup E] [NormedSpace ℝ E] [FiniteDimensional ℝ E] {Q : Set E} {f d : E → ℝ} {L σ : ℝ} (α : ℕ → ℝ) (xSeq ySeq : ℕ → Q) (k : ℕ) (hx_update : (xSeq (k + 1) : E) = (α (k + 1) / A_k α (k + 1)) • (z_k Q f d L σ α xSeq k : E) + (1 - α (k + 1) / A_k α (k + 1)) • (ySeq k : E)) (hy_update : (ySeq (k + 1) : E) = let τk : ℝ := α (k + 1) / A_k α (k + 1) let γk : ℝ := (σ / L) * α (k + 1) τk • (V_Q Q d (z_k Q f d L σ α xSeq k) (γk • fderiv ℝ f (xSeq (k + 1))) : E) + (1 - τk) • (ySeq k : E)) : let τk : ℝ := α (k + 1) / A_k α (k + 1) let γk : ℝ := (σ / L) * α (k + 1) let xhat : E := V_Q Q d (z_k Q f d L σ α xSeq k) (γk • fderiv ℝ f (xSeq (k + 1))) (ySeq (k + 1) : E) - (xSeq (k + 1) : E) = τk • (xhat - (z_k Q f d L σ α xSeq k : E)) := by classical let τk : ℝ := α (k + 1) / A_k α (k + 1) let γk : ℝ := (σ / L) * α (k + 1) let xhat : E := V_Q Q d (z_k Q f d L σ α xSeq k) (γk • fderiv ℝ f (xSeq (k + 1))) have hy : (ySeq (k + 1) : E) = τk • xhat + (1 - τk) • (ySeq k : E) := by simpa [τk, γk, xhat] using hy_update have hx : (xSeq (k + 1) : E) = τk • (z_k Q f d L σ α xSeq k : E) + (1 - τk) • (ySeq k : E) := by simpa [τk] using hx_update calc (ySeq (k + 1) : E) - (xSeq (k + 1) : E) = (τk • xhat + (1 - τk) • (ySeq k : E)) - (τk • (z_k Q f d L σ α xSeq k : E) + (1 - τk) • (ySeq k : E)) := by simp [hy, hx] _ = τk • (xhat - (z_k Q f d L σ α xSeq k : E)) := by simp [sub_eq_add_neg, add_comm, add_left_comm, add_assoc, smul_add]

Final convexity step for the modified invariant update.

lemma section05_final_convexity_step {E : Type*} [NormedAddCommGroup E] [NormedSpace ℝ E] [FiniteDimensional ℝ E] {Q : Set E} {f : E → ℝ} (xSeq ySeq : ℕ → Q) (k : ℕ) (hQ_convex : Convex ℝ Q) (hf_convex : ConvexOn ℝ Q f) (hf_diff : ∀ x ∈ Q, DifferentiableAt ℝ f x) : let xk1 : E := xSeq (k + 1) let g : Module.Dual ℝ E := (fderiv ℝ f (xSeq (k + 1))).toLinearMap f (ySeq (k + 1)) ≥ f xk1 + DualPairing g ((ySeq (k + 1) : E) - xk1) := by classical let xk1 : E := xSeq (k + 1) let g : Module.Dual ℝ E := (fderiv ℝ f (xSeq (k + 1))).toLinearMap have hxk1 : (xSeq (k + 1) : E) ∈ Q := (xSeq (k + 1)).property have hyk1 : (ySeq (k + 1) : E) ∈ Q := (ySeq (k + 1)).property have hsupport : f (ySeq (k + 1)) ≥ f xk1 + DualPairing g ((ySeq (k + 1) : E) - xk1) := by exact section03_convex_support_fderiv (hQ_convex := hQ_convex) (hf_convex := hf_convex) (u := (ySeq (k + 1) : E)) (v := (xSeq (k + 1) : E)) hyk1 hxk1 (hf_diff (xSeq (k + 1)) hxk1) simpa [xk1, g] using hsupport