Smooth Minimization of Non-Smooth Functions (Nesterov, 2004) -- Section 03 -- Part 2

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

Source header · Attribution source

Adding a convex function preserves strong convexity.

lemma section03_strongConvex_add_convex {E : Type*} [NormedAddCommGroup E] [NormedSpace ℝ E] {Q : Set E} {m : ℝ} {f g : E → ℝ} (hf : StrongConvexOn Q m f) (hg : ConvexOn ℝ Q g) : StrongConvexOn Q m (f + g) := by have hf' : UniformConvexOn Q (fun r => m / 2 * r ^ 2) f := hf have hg' : UniformConvexOn Q 0 g := hg.uniformConvexOn_zero have hsum : UniformConvexOn Q (fun r => m / 2 * r ^ 2 + 0) (f + g) := hf'.add hg' simpa [StrongConvexOn] using hsum

Convexity of the affine sum term in Unknown identifier `F_k`F_k.

lemma section03_Fk_sum_convex {E : Type*} [NormedAddCommGroup E] [NormedSpace ℝ E] [FiniteDimensional ℝ E] {Q : Set E} (hQ_convex : Convex ℝ Q) {f : E → ℝ} (α : ℕ → ℝ) (xSeq : ℕ → Q) (k : ℕ) (hα_pos : ∀ k, 0 < α k) : ConvexOn ℝ Q (fun x => Finset.sum (Finset.range (k + 1)) (fun i => α i * (f (xSeq i) + DualPairing ((fderiv ℝ f (xSeq i)).toLinearMap) (x - xSeq i)))) := by classical let term : ℕ → E → ℝ := fun i x => α i * (f (xSeq i) + DualPairing ((fderiv ℝ f (xSeq i)).toLinearMap) (x - xSeq i)) have hterm_convex : ∀ i, ConvexOn ℝ Q (term i) := by intro i let s : Module.Dual ℝ E := (fderiv ℝ f (xSeq i)).toLinearMap have hconst : ConvexOn ℝ Q (fun _ : E => f (xSeq i)) := convexOn_const _ hQ_convex have hlin : ConvexOn ℝ Q (fun x => DualPairing s (x - (xSeq i : E))) := section03_convex_dualpairing_sub (hQ_convex := hQ_convex) s (xSeq i) have hadd : ConvexOn ℝ Q (fun x => f (xSeq i) + DualPairing s (x - (xSeq i : E))) := by simpa [add_comm, add_left_comm, add_assoc] using hconst.add hlin have hα_nonneg : 0 ≤ α i := le_of_lt (hα_pos i) simpa [term, smul_eq_mul] using (hadd.smul hα_nonneg) refine Finset.induction_on (Finset.range (k + 1)) ?_ ?_ · simpa [term] using (convexOn_const (c := (0 : ℝ)) hQ_convex) · intro i s his hconv have hsum := hconv.add (hterm_convex i) simpa [term, Finset.sum_insert his, add_comm, add_left_comm, add_assoc] using hsum

Quadratic lower bound at a minimizer of Unknown identifier `F_k`F_k.

lemma section03_Fk_quadratic_lower_bound_at_zk {E : Type*} [NormedAddCommGroup E] [NormedSpace ℝ E] [FiniteDimensional ℝ E] {Q : Set E} {f d : E → ℝ} {L σ : ℝ} (α : ℕ → ℝ) (xSeq : ℕ → Q) (k : ℕ) (hQ_convex : Convex ℝ Q) (hconv : StrongConvexOn Q σ d) (hσ : 0 < σ) (hL : 0 < L) (hα_pos : ∀ k, 0 < α k) (hzk_min : IsMinOn (fun x : E => (L / σ) * d x + Finset.sum (Finset.range (k + 1)) (fun i => α i * (f (xSeq i) + DualPairing ((fderiv ℝ f (xSeq i)).toLinearMap) (x - xSeq i)))) Q (z_k Q f d L σ α xSeq k : E)) : ∀ x ∈ Q, psi_k Q f d L σ α xSeq k + (L / 2) * ‖x - (z_k Q f d L σ α xSeq k : E)‖ ^ 2 ≤ (L / σ) * d x + Finset.sum (Finset.range (k + 1)) (fun i => α i * (f (xSeq i) + DualPairing ((fderiv ℝ f (xSeq i)).toLinearMap) (x - xSeq i))) := by classical let Fk : E → ℝ := fun x => (L / σ) * d x + Finset.sum (Finset.range (k + 1)) (fun i => α i * (f (xSeq i) + DualPairing ((fderiv ℝ f (xSeq i)).toLinearMap) (x - xSeq i))) have hscaled : StrongConvexOn Q L (fun x => (L / σ) * d x) := by refine ⟨hconv.1, ?_⟩ intro x hx y hy a b ha hb hab have hconv_d := hconv.2 hx hy ha hb hab have hLσ_nonneg : 0 ≤ L / σ := by exact div_nonneg (le_of_lt hL) (le_of_lt hσ) have hscaled := mul_le_mul_of_nonneg_left hconv_d hLσ_nonneg have hσ_ne : (σ : ℝ) ≠ 0 := ne_of_gt hσ calc (L / σ) * d (a • x + b • y) ≤ (L / σ) * (a * d x + b * d y - a * b * ((σ / 2) * ‖x - y‖ ^ (2 : ℕ))) := hscaled _ = a * ((L / σ) * d x) + b * ((L / σ) * d y) - a * b * ((L / 2) * ‖x - y‖ ^ (2 : ℕ)) := by field_simp [hσ_ne, mul_comm, mul_left_comm, mul_assoc, sub_eq_add_neg, add_comm, add_left_comm, add_assoc] have hsum_convex : ConvexOn ℝ Q (fun x => Finset.sum (Finset.range (k + 1)) (fun i => α i * (f (xSeq i) + DualPairing ((fderiv ℝ f (xSeq i)).toLinearMap) (x - xSeq i)))) := section03_Fk_sum_convex (hQ_convex := hQ_convex) (α := α) (xSeq := xSeq) (k := k) (hα_pos := hα_pos) have hFk_strong : StrongConvexOn Q L Fk := by have hsum_uniform : UniformConvexOn Q 0 (fun x => Finset.sum (Finset.range (k + 1)) (fun i => α i * (f (xSeq i) + DualPairing ((fderiv ℝ f (xSeq i)).toLinearMap) (x - xSeq i)))) := hsum_convex.uniformConvexOn_zero have hscaled' : UniformConvexOn Q (fun r => L / 2 * r ^ 2) (fun x => (L / σ) * d x) := hscaled have hsum : UniformConvexOn Q (fun r => L / 2 * r ^ 2 + 0) (fun x => (L / σ) * d x + Finset.sum (Finset.range (k + 1)) (fun i => α i * (f (xSeq i) + DualPairing ((fderiv ℝ f (xSeq i)).toLinearMap) (x - xSeq i)))) := hscaled'.add hsum_uniform simpa [Fk, StrongConvexOn] using hsum intro x hx have hzk_mem : (z_k Q f d L σ α xSeq k : E) ∈ Q := (z_k Q f d L σ α xSeq k).property have hlower : Fk (z_k Q f d L σ α xSeq k : E) + (L / 2) * ‖x - (z_k Q f d L σ α xSeq k : E)‖ ^ (2 : ℕ) ≤ Fk x := by exact strongConvexOn_lower_quadratic_of_isMinOn Q Fk L (z_k Q f d L σ α xSeq k) hFk_strong hzk_mem hzk_min x hx have hBdd : BddBelow (Fk '' Q) := by refine ⟨Fk (z_k Q f d L σ α xSeq k : E), ?_⟩ intro b hb rcases hb with ⟨z, hz, rfl⟩ have hmin := (isMinOn_iff.mp hzk_min) z hz simpa [Fk] using hmin have hpsi_le : psi_k Q f d L σ α xSeq k ≤ Fk (z_k Q f d L σ α xSeq k : E) := by refine csInf_le hBdd ?_ exact ⟨(z_k Q f d L σ α xSeq k : E), hzk_mem, rfl⟩ have hpsi_le' : psi_k Q f d L σ α xSeq k + (L / 2) * ‖x - (z_k Q f d L σ α xSeq k : E)‖ ^ 2 ≤ Fk (z_k Q f d L σ α xSeq k : E) + (L / 2) * ‖x - (z_k Q f d L σ α xSeq k : E)‖ ^ 2 := by simpa [add_comm, add_left_comm, add_assoc] using (add_le_add_right hpsi_le ((L / 2) * ‖x - (z_k Q f d L σ α xSeq k : E)‖ ^ 2)) have hfinal := le_trans hpsi_le' hlower simpa [Fk, pow_two] using hfinal

Lemma 1.3.1. Let be positive numbers with and for all Unknown identifier `k`sorry ≥ 0 : Propk ≥ 0, where (equation (3.6)). Assume R_k : (Q : Set ?m.1) → (?m.1 → ℝ) → (?m.1 → ℝ) → ℝ → ℝ → (ℕ → ℝ) → (ℕ → ↑Q) → (ℕ → ↑Q) → ℕ → Prop(R_k) holds for some Unknown identifier `k`sorry ≥ 0 : Propk ≥ 0. Define (equation (tau_def)) and update , (equation (3.7)). Then holds.

theorem Rk_succ_update {E : Type*} [NormedAddCommGroup E] [NormedSpace ℝ E] [FiniteDimensional ℝ E] {Q : Set E} {f d : E → ℝ} {L σ : ℝ} (α : ℕ → ℝ) (hQ_closed : IsClosed Q) (hQ_convex : Convex ℝ Q) (hf_convex : ConvexOn ℝ Q f) (hf_diff : ∀ x ∈ Q, DifferentiableAt ℝ f x) (hL : 0 < L) (hgrad_lipschitz : ∀ x ∈ Q, ∀ y ∈ Q, DualNormDef ((fderiv ℝ f x).toLinearMap - (fderiv ℝ f y).toLinearMap) ≤ L * ‖x - y‖) (hconv : StrongConvexOn Q σ d) (hσ : 0 < σ) (xSeq ySeq : ℕ → Q) (k : ℕ) (hα_pos : ∀ k, 0 < α k) (hα_sq : ∀ k, (α (k + 1)) ^ 2 ≤ A_k α (k + 1)) (hRk : R_k Q f d L σ α xSeq ySeq k) (hzk_min : IsMinOn (fun x : E => (L / σ) * d x + Finset.sum (Finset.range (k + 1)) (fun i => α i * (f (xSeq i) + DualPairing ((fderiv ℝ f (xSeq i)).toLinearMap) (x - xSeq i)))) Q (z_k Q f d L σ α xSeq k : E)) (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) = T_Q Q f L (xSeq (k + 1))) : R_k Q f d L σ α xSeq ySeq (k + 1) := by classical let A := A_k α (k + 1) let τ := α (k + 1) / A have hτ_props : 0 < A ∧ 0 ≤ τ ∧ τ ≤ 1 ∧ τ ^ 2 ≤ 1 / A := by simpa [A, τ] using (section03_tau_props (α := α) k hα_pos hα_sq) rcases hτ_props with ⟨hA_pos, hτ_nonneg, hτ_le, hτ_sq⟩ have hA_nonneg : 0 ≤ A := le_of_lt hA_pos have hA_ne : (A : ℝ) ≠ 0 := ne_of_gt hA_pos let xk1 : E := xSeq (k + 1) let zk : E := z_k Q f d L σ α xSeq k let g : Module.Dual ℝ E := (fderiv ℝ f (xSeq (k + 1))).toLinearMap let model : E → ℝ := fun y => DualPairing g (y - xk1) + (L / 2) * ‖y - xk1‖ ^ 2 have hpoint : ∀ z ∈ Q, A * f (ySeq (k + 1)) ≤ (L / σ) * d z + Finset.sum (Finset.range (k + 2)) (fun i => α i * (f (xSeq i) + DualPairing ((fderiv ℝ f (xSeq i)).toLinearMap) (z - xSeq i))) := by intro z hz have hmodel_ge : model (ySeq (k + 1) : E) ≥ f (ySeq (k + 1)) - f xk1 := by have h := section03_model_at_TQ_ge_fdiff (hQ_convex := hQ_convex) (hf_diff := hf_diff) (hL := hL) (hgrad_lipschitz := hgrad_lipschitz) (x0 := xSeq (k + 1)) have h' : model (T_Q Q f L (xSeq (k + 1)) : E) ≥ f (T_Q Q f L (xSeq (k + 1))) - f xk1 := by simpa [model, g, xk1] using h simpa [hy_update] using h' have hfy_le : f (ySeq (k + 1)) ≤ f xk1 + model (ySeq (k + 1) : E) := by linarith [hmodel_ge] have hfy_mul : A * f (ySeq (k + 1)) ≤ A * (f xk1 + model (ySeq (k + 1) : E)) := by exact mul_le_mul_of_nonneg_left hfy_le hA_nonneg let y : E := τ • z + (1 - τ) • (ySeq k : E) have hy_data : y ∈ Q ∧ y - xk1 = τ • (z - zk) := by have h := section03_change_of_variables_y (hQ_convex := hQ_convex) (α := α) (xSeq := xSeq) (ySeq := ySeq) (k := k) (x := z) (hx := hz) (hτ_nonneg := hτ_nonneg) (hτ_le := hτ_le) (hx_update := hx_update) simpa [y, τ, xk1, zk] using h have hy_mem : y ∈ Q := hy_data.1 have hy_shift : y - xk1 = τ • (z - zk) := hy_data.2 have hmodel_le : model (ySeq (k + 1) : E) ≤ model y := by have h := R0_TQ_model_le (hQ_closed := hQ_closed) (hL := hL) (f := f) (x0 := xSeq (k + 1)) y hy_mem have h' : model (T_Q Q f L (xSeq (k + 1)) : E) ≤ model y := by simpa [model, g, xk1] using h simpa [hy_update] using h' have hmodel_le_mul : A * (f xk1 + model (ySeq (k + 1) : E)) ≤ A * (f xk1 + model y) := by have hadd : f xk1 + model (ySeq (k + 1) : E) ≤ f xk1 + model y := by have h := add_le_add_left hmodel_le (f xk1) simpa [add_comm, add_left_comm, add_assoc] using h exact mul_le_mul_of_nonneg_left hadd hA_nonneg have hmodel_eq : model y = (L / 2) * τ ^ 2 * ‖z - zk‖ ^ 2 + τ * DualPairing g (z - zk) := by have h := section03_change_of_variables_model (α := α) (xSeq := xSeq) (k := k) (x := z) (y := y) (τ := τ) (hy_shift := hy_shift) g calc model y = DualPairing g (y - xk1) + (L / 2) * ‖y - xk1‖ ^ 2 := rfl _ = (L / 2) * ‖y - xk1‖ ^ 2 + DualPairing g (y - xk1) := by ac_rfl _ = (L / 2) * τ ^ 2 * ‖z - zk‖ ^ 2 + τ * DualPairing g (z - zk) := by simpa [xk1, zk, y] using h.symm have hcoeff : A * ((L / 2) * τ ^ 2 * ‖z - zk‖ ^ 2 + τ * DualPairing g (z - zk)) ≤ (L / 2) * ‖z - zk‖ ^ 2 + α (k + 1) * DualPairing g (z - zk) := by have hcoeff_base : (L / 2) * τ ^ 2 * ‖z - zk‖ ^ 2 ≤ (L / (2 * A)) * ‖z - zk‖ ^ 2 := by have h := section03_quad_coeff_compare (L := L) (A := A) (τ := τ) (hL := le_of_lt hL) (hA := hA_pos) (hτ := hτ_sq) (v := (z - zk)) simpa [ge_iff_le] using h have hcoeff_add : (L / 2) * τ ^ 2 * ‖z - zk‖ ^ 2 + τ * DualPairing g (z - zk) ≤ (L / (2 * A)) * ‖z - zk‖ ^ 2 + τ * DualPairing g (z - zk) := by have h := add_le_add_right hcoeff_base (τ * DualPairing g (z - zk)) simpa [add_comm, add_left_comm, add_assoc] using h have hcoeff_mul : A * ((L / 2) * τ ^ 2 * ‖z - zk‖ ^ 2 + τ * DualPairing g (z - zk)) ≤ A * ((L / (2 * A)) * ‖z - zk‖ ^ 2 + τ * DualPairing g (z - zk)) := by exact mul_le_mul_of_nonneg_left hcoeff_add hA_nonneg have hAtau : A * τ = α (k + 1) := by calc A * τ = A * (α (k + 1) / A) := by simp [τ] _ = α (k + 1) := by field_simp [hA_ne] have hcoeff_simp : A * ((L / (2 * A)) * ‖z - zk‖ ^ 2 + τ * DualPairing g (z - zk)) = (L / 2) * ‖z - zk‖ ^ 2 + α (k + 1) * DualPairing g (z - zk) := by calc A * ((L / (2 * A)) * ‖z - zk‖ ^ 2 + τ * DualPairing g (z - zk)) = A * ((L / (2 * A)) * ‖z - zk‖ ^ 2) + A * (τ * DualPairing g (z - zk)) := by simp [mul_add, add_comm] _ = (L / 2) * ‖z - zk‖ ^ 2 + (A * τ) * DualPairing g (z - zk) := by field_simp [hA_ne, mul_comm, mul_left_comm, mul_assoc] _ = (L / 2) * ‖z - zk‖ ^ 2 + α (k + 1) * DualPairing g (z - zk) := by simp [hAtau, mul_comm] exact le_trans hcoeff_mul (by simp [hcoeff_simp]) have hmodel_bound : A * f (ySeq (k + 1)) ≤ A * f xk1 + (L / 2) * ‖z - zk‖ ^ 2 + α (k + 1) * DualPairing g (z - zk) := by calc A * f (ySeq (k + 1)) ≤ A * (f xk1 + model (ySeq (k + 1) : E)) := hfy_mul _ ≤ A * (f xk1 + model y) := hmodel_le_mul _ = A * (f xk1 + ((L / 2) * τ ^ 2 * ‖z - zk‖ ^ 2 + τ * DualPairing g (z - zk))) := by simp [hmodel_eq] _ = A * f xk1 + A * ((L / 2) * τ ^ 2 * ‖z - zk‖ ^ 2 + τ * DualPairing g (z - zk)) := by simp [mul_add, add_comm] _ ≤ A * f xk1 + (L / 2) * ‖z - zk‖ ^ 2 + α (k + 1) * DualPairing g (z - zk) := by have h := add_le_add_left hcoeff (A * f xk1) simpa [add_comm, add_left_comm, add_assoc] using h have hA_old_nonneg : 0 ≤ A_k α k := by unfold A_k exact Finset.sum_nonneg (fun i _ => le_of_lt (hα_pos i)) have hsupport : f (ySeq k) ≥ f xk1 + DualPairing g ((ySeq k : E) - xk1) := by have hxk1' : (xSeq (k + 1) : E) ∈ Q := (xSeq (k + 1)).property have hyk' : (ySeq k : E) ∈ Q := (ySeq k).property 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 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_old_nonneg have hpsi_linear : A_k α k * (f xk1 + DualPairing g ((ySeq k : E) - xk1)) ≤ psi_k Q f d L σ α xSeq k := by exact le_trans hsupport_scaled hRk have hpsi_plus : A_k α k * (f xk1 + DualPairing g ((ySeq k : E) - xk1)) + α (k + 1) * (f xk1 + DualPairing g (z - xk1)) ≤ psi_k Q f d L σ α xSeq k + α (k + 1) * (f xk1 + DualPairing g (z - xk1)) := by have h := add_le_add_right hpsi_linear (α (k + 1) * (f xk1 + DualPairing g (z - xk1))) simpa [add_comm, add_left_comm, add_assoc] using h have hcombine : A_k α k * DualPairing g ((ySeq k : E) - xk1) + α (k + 1) * DualPairing g (z - xk1) = α (k + 1) * DualPairing g (z - zk) := by have h := section03_dualpairing_combine_update (α := α) (xSeq := xSeq) (ySeq := ySeq) (k := k) (hA_pos := hA_pos) (hx_update := hx_update) g z simpa [xk1, zk] using h have hA_sum : A = A_k α k + α (k + 1) := by simp [A, A_k, Finset.sum_range_succ, add_comm, add_left_comm, add_assoc] have hpsi_plus' : A * f xk1 + α (k + 1) * DualPairing g (z - zk) ≤ psi_k Q f d L σ α xSeq k + α (k + 1) * (f xk1 + DualPairing g (z - xk1)) := by calc A * f xk1 + α (k + 1) * DualPairing g (z - zk) = A_k α k * (f xk1 + DualPairing g ((ySeq k : E) - xk1)) + α (k + 1) * (f xk1 + DualPairing g (z - xk1)) := by calc A * f xk1 + α (k + 1) * DualPairing g (z - zk) = (A_k α k + α (k + 1)) * f xk1 + α (k + 1) * DualPairing g (z - zk) := by simp [hA_sum] _ = A_k α k * f xk1 + α (k + 1) * f xk1 + α (k + 1) * DualPairing g (z - zk) := by ring _ = A_k α k * f xk1 + α (k + 1) * f xk1 + (A_k α k * DualPairing g ((ySeq k : E) - xk1) + α (k + 1) * DualPairing g (z - xk1)) := by simp [hcombine] _ = A_k α k * (f xk1 + DualPairing g ((ySeq k : E) - xk1)) + α (k + 1) * (f xk1 + DualPairing g (z - xk1)) := by ring _ ≤ psi_k Q f d L σ α xSeq k + α (k + 1) * (f xk1 + DualPairing g (z - xk1)) := by exact hpsi_plus have hpsi_plus'' : A * f xk1 + (L / 2) * ‖z - zk‖ ^ 2 + α (k + 1) * DualPairing g (z - zk) ≤ psi_k Q f d L σ α xSeq k + (L / 2) * ‖z - zk‖ ^ 2 + α (k + 1) * (f xk1 + DualPairing g (z - xk1)) := by have h := add_le_add_right hpsi_plus' ((L / 2) * ‖z - zk‖ ^ 2) simpa [add_comm, add_left_comm, add_assoc] using h have hFk_lower := section03_Fk_quadratic_lower_bound_at_zk (α := α) (xSeq := xSeq) (k := k) (hQ_convex := hQ_convex) (hconv := hconv) (hσ := hσ) (hL := hL) (hα_pos := hα_pos) (hzk_min := hzk_min) z hz have hFk1_lower : psi_k Q f d L σ α xSeq k + (L / 2) * ‖z - zk‖ ^ 2 + α (k + 1) * (f xk1 + DualPairing g (z - xk1)) ≤ (L / σ) * d z + Finset.sum (Finset.range (k + 2)) (fun i => α i * (f (xSeq i) + DualPairing ((fderiv ℝ f (xSeq i)).toLinearMap) (z - xSeq i))) := by let term : ℕ → ℝ := fun i => α i * (f (xSeq i) + DualPairing ((fderiv ℝ f (xSeq i)).toLinearMap) (z - xSeq i)) have h' : psi_k Q f d L σ α xSeq k + (L / 2) * ‖z - zk‖ ^ 2 + α (k + 1) * (f xk1 + DualPairing g (z - xk1)) ≤ (L / σ) * d z + Finset.sum (Finset.range (k + 1)) term + α (k + 1) * (f xk1 + DualPairing g (z - xk1)) := by have h := add_le_add_right hFk_lower (α (k + 1) * (f xk1 + DualPairing g (z - xk1))) simpa [add_comm, add_left_comm, add_assoc] using h have h'' : psi_k Q f d L σ α xSeq k + (L / 2) * ‖z - zk‖ ^ 2 + α (k + 1) * (f xk1 + DualPairing g (z - xk1)) ≤ (L / σ) * d z + Finset.sum (Finset.range (k + 1)) term + term (k + 1) := by simpa [term, xk1, g, add_assoc] using h' simpa [term, Finset.sum_range_succ, add_assoc] using h'' exact le_trans (le_trans hmodel_bound hpsi_plus'') hFk1_lower unfold R_k have hgoal : A_k α (k + 1) * f ↑(ySeq (k + 1)) ≤ sInf ((fun a ↦ L / σ * d a + ∑ x ∈ Finset.range (k + 1 + 1), α x * (f ↑(xSeq x) + DualPairing (↑(fderiv ℝ f ↑(xSeq x))) (a - ↑(xSeq x)))) '' Q) := by refine le_csInf ?_ ?_ · refine ⟨(L / σ) * d (xSeq (k + 1)) + Finset.sum (Finset.range (k + 2)) (fun i => α i * (f (xSeq i) + DualPairing ((fderiv ℝ f (xSeq i)).toLinearMap) ((xSeq (k + 1) : E) - xSeq i))), ?_⟩ exact ⟨(xSeq (k + 1) : E), (xSeq (k + 1)).property, rfl⟩ · intro b hb rcases hb with ⟨z, hz, rfl⟩ simpa [A] using hpoint z hz simpa [psi_k] using hgoal

Closed form for A_k (α : ℕ → ℝ) (k : ℕ) : ℝA_k when Unknown identifier `α_k`sorry = (sorry + 1) / 2 : Propα_k = (Unknown identifier `k`k+1)/2.

lemma section03_Ak_alpha_closed_form (k : ℕ) : A_k (fun k => ((k : ℝ) + 1) / 2) k = ((k : ℝ) + 1) * ((k : ℝ) + 2) / 4 := by induction k with | zero => simp [A_k] norm_num | succ k ih => have hsum : A_k (fun k => ((k : ℝ) + 1) / 2) (k + 1) = A_k (fun k => ((k : ℝ) + 1) / 2) k + ((k : ℝ) + 2) / 2 := by simp [A_k, Finset.sum_range_succ, add_comm, add_left_comm] ring have hcalc : A_k (fun k => ((k : ℝ) + 1) / 2) (k + 1) = ((k : ℝ) + 1 + 1) * ((k : ℝ) + 1 + 2) / 4 := by calc A_k (fun k => ((k : ℝ) + 1) / 2) (k + 1) = A_k (fun k => ((k : ℝ) + 1) / 2) k + ((k : ℝ) + 2) / 2 := hsum _ = ((k : ℝ) + 1) * ((k : ℝ) + 2) / 4 + ((k : ℝ) + 2) / 2 := by simp [ih] _ = ((k : ℝ) + 2) * ((k : ℝ) + 3) / 4 := by have h2 : (2 : ℝ) ≠ 0 := by norm_num have h4 : (4 : ℝ) ≠ 0 := by norm_num field_simp [h2, h4] ring _ = ((k : ℝ) + 1 + 1) * ((k : ℝ) + 1 + 2) / 4 := by ring simpa [add_assoc, add_left_comm, add_comm] using hcalc

Closed form for when Unknown identifier `α_k`sorry = (sorry + 1) / 2 : Propα_k = (Unknown identifier `k`k+1)/2.

lemma section03_tau_alpha_closed_form (k : ℕ) : (fun k => ((k : ℝ) + 1) / 2) (k + 1) / A_k (fun k => ((k : ℝ) + 1) / 2) (k + 1) = 2 / ((k : ℝ) + 3) := by have hAk : A_k (fun k => ((k : ℝ) + 1) / 2) (k + 1) = ((k : ℝ) + 2) * ((k : ℝ) + 3) / 4 := by calc A_k (fun k => ((k : ℝ) + 1) / 2) (k + 1) = ((k : ℝ) + 1 + 1) * ((k : ℝ) + 1 + 2) / 4 := by simpa using section03_Ak_alpha_closed_form (k + 1) _ = ((k : ℝ) + 2) * ((k : ℝ) + 3) / 4 := by ring have hk2_pos : 0 < (k : ℝ) + 2 := by have hk_nonneg : (0 : ℝ) ≤ (k : ℝ) := by exact_mod_cast (Nat.zero_le k) linarith have hk3_pos : 0 < (k : ℝ) + 3 := by have hk_nonneg : (0 : ℝ) ≤ (k : ℝ) := by exact_mod_cast (Nat.zero_le k) linarith have hk2_ne : (k : ℝ) + 2 ≠ 0 := ne_of_gt hk2_pos have hk3_ne : (k : ℝ) + 3 ≠ 0 := ne_of_gt hk3_pos have h2 : (2 : ℝ) ≠ 0 := by norm_num have h4 : (4 : ℝ) ≠ 0 := by norm_num have hnum : (k : ℝ) + 1 + 1 = (k : ℝ) + 2 := by ring calc (fun k => ((k : ℝ) + 1) / 2) (k + 1) / A_k (fun k => ((k : ℝ) + 1) / 2) (k + 1) = ((k : ℝ) + 2) / 2 / (((k : ℝ) + 2) * ((k : ℝ) + 3) / 4) := by simp [hAk, hnum] _ = 2 / ((k : ℝ) + 3) := by field_simp [hk2_ne, hk3_ne, h2, h4] ring

The initial step size satisfies .

lemma section03_alpha0_mem_Ioc : (fun k => ((k : ℝ) + 1) / 2) 0 ∈ Set.Ioc (0 : ℝ) 1 := by simp [Set.mem_Ioc] norm_num

The inequality for Unknown identifier `α_k`sorry = (sorry + 1) / 2 : Propα_k = (Unknown identifier `k`k+1)/2.

lemma section03_alpha_sq_le_Ak (k : ℕ) : (fun k => ((k : ℝ) + 1) / 2) (k + 1) ^ 2 ≤ A_k (fun k => ((k : ℝ) + 1) / 2) (k + 1) := by have hAk : A_k (fun k => ((k : ℝ) + 1) / 2) (k + 1) = ((k : ℝ) + 2) * ((k : ℝ) + 3) / 4 := by calc A_k (fun k => ((k : ℝ) + 1) / 2) (k + 1) = ((k : ℝ) + 1 + 1) * ((k : ℝ) + 1 + 2) / 4 := by simpa using section03_Ak_alpha_closed_form (k + 1) _ = ((k : ℝ) + 2) * ((k : ℝ) + 3) / 4 := by ring have hk_nonneg : (0 : ℝ) ≤ (k : ℝ) := by exact_mod_cast (Nat.zero_le k) have hk2_nonneg : 0 ≤ (k : ℝ) + 2 := by linarith have hk2_le : (k : ℝ) + 2 ≤ (k : ℝ) + 3 := by linarith have hineq : ((k : ℝ) + 2) ^ 2 ≤ ((k : ℝ) + 2) * ((k : ℝ) + 3) := by have h := mul_le_mul_of_nonneg_left hk2_le hk2_nonneg simpa [pow_two, mul_comm, mul_left_comm, mul_assoc] using h have hquarter : (0 : ℝ) ≤ (4 : ℝ)⁻¹ := by norm_num have hineq' : ((k : ℝ) + 2) ^ 2 / 4 ≤ ((k : ℝ) + 2) * ((k : ℝ) + 3) / 4 := by have h := mul_le_mul_of_nonneg_right hineq hquarter simpa [div_eq_mul_inv, mul_comm, mul_left_comm, mul_assoc] using h calc (fun k => ((k : ℝ) + 1) / 2) (k + 1) ^ 2 = (((k : ℝ) + 2) / 2) ^ 2 := by have hnum : (k : ℝ) + 1 + 1 = (k : ℝ) + 2 := by ring simp [hnum] _ = ((k : ℝ) + 2) ^ 2 / 4 := by have h2 : (2 : ℝ) ≠ 0 := by norm_num field_simp [h2] ring _ ≤ A_k (fun k => ((k : ℝ) + 1) / 2) (k + 1) := by simpa [hAk] using hineq'

Lemma 1.3.2. For Unknown identifier `k`sorry ≥ 0 : Propk ≥ 0, define Unknown identifier `α_k`sorry = (sorry + 1) / 2 : Propα_k = (Unknown identifier `k`k+1)/2 (equation (alpha_k_def)). Then Unknown identifier `τ_k`sorry = 2 / (sorry + 3) : Propτ_k = 2/(Unknown identifier `k`k+3) and (equation (3.10)), and the conditions (3.6) ( and ) are satisfied.

theorem alpha_seq_closed_form : let α : ℕ → ℝ := fun k => ((k : ℝ) + 1) / 2 (∀ k, A_k α k = ((k : ℝ) + 1) * ((k : ℝ) + 2) / 4) ∧ (∀ k, α (k + 1) / A_k α (k + 1) = 2 / ((k : ℝ) + 3)) ∧ α 0 ∈ Set.Ioc (0 : ℝ) 1 ∧ (∀ k, (α (k + 1)) ^ 2 ≤ A_k α (k + 1)) := by dsimp refine ⟨?_, ?_⟩ · intro k simpa using section03_Ak_alpha_closed_form k · refine ⟨?_, ?_⟩ · intro k simpa using section03_tau_alpha_closed_form k · refine ⟨?_, ?_⟩ · simpa using section03_alpha0_mem_Ioc · intro k simpa using section03_alpha_sq_le_Ak k

Algorithm 1.3.1. Assume Unknown identifier `f`f satisfies (grad_lipschitz) on Unknown identifier `Q`Q, and let Unknown identifier `d`d be a prox-function for Unknown identifier `Q`Q with parameter Unknown identifier `σ`σ. Initialize at a prox-center Unknown identifier `x0`x0 of Unknown identifier `Q`Q and set . For Unknown identifier `k`sorry ≥ 0 : Propk ≥ 0, iterate:

  1. compute and ;

  2. compute ;

  3. compute z_k.{u_1} {E : Type u_1} [SeminormedAddCommGroup E] [NormedSpace ℝ E] [FiniteDimensional ℝ E] (Q : Set E) (f d : E → ℝ) (L σ : ℝ) (α : ℕ → ℝ) (xSeq : ℕ → ↑Q) (k : ℕ) : ↑Qz_k as an argmin of over Unknown identifier `x`sorry ∈ sorry : Propx ∈ Unknown identifier `Q`Q (equation (alg311:zk));

  4. set (equation (3.11)).

def OptimalSchemeAlgorithm {E : Type*} [NormedAddCommGroup E] [NormedSpace ℝ E] [FiniteDimensional ℝ E] (Q : Set E) (f d : E → ℝ) (L σ : ℝ) (xSeq ySeq : ℕ → Q) : Prop := IsClosed Q ∧ ConvexOn ℝ Q f ∧ (∀ x ∈ Q, DifferentiableAt ℝ f x) ∧ 0 < L ∧ (∀ x ∈ Q, ∀ y ∈ Q, DualNormDef ((fderiv ℝ f x).toLinearMap - (fderiv ℝ f y).toLinearMap) ≤ L * ‖x - y‖) ∧ ProxFunction Q d ∧ StrongConvexOn Q σ d ∧ 0 < σ ∧ IsNormalizedProxCenter Q d (xSeq 0) ∧ ySeq 0 = T_Q Q f L (xSeq 0) ∧ (∀ k, ySeq k = T_Q Q f L (xSeq k)) ∧ (∀ k, IsMinOn (z_k_objective Q f d L σ (fun i => ((i : ℝ) + 1) / 2) xSeq k) Q (z_k Q f d L σ (fun i => ((i : ℝ) + 1) / 2) xSeq k : E)) ∧ (∀ k, (xSeq (k + 1) : E) = (2 / ((k : ℝ) + 3)) • (z_k Q f d L σ (fun i => ((i : ℝ) + 1) / 2) xSeq k : E) + (((k : ℝ) + 1) / ((k : ℝ) + 3)) • (ySeq k : E))

Definition 1.3.6. Define a modified selection rule: given , set and choose (equation (3.14)).

def ModifiedSelectionRule {E : Type*} [SeminormedAddCommGroup E] [NormedSpace ℝ E] [FiniteDimensional ℝ E] (Q : Set E) (f : E → ℝ) (L : ℝ) (xSeq ySeq : ℕ → Q) (k : ℕ) : Prop := let ytilde : Q := T_Q Q f L (xSeq (Nat.succ k)) let S : Set Q := ({ySeq k} ∪ {xSeq (Nat.succ k)} ∪ {ytilde}) ySeq (Nat.succ k) ∈ S ∧ ∀ z ∈ S, f (ySeq (Nat.succ k)) ≤ f z

Proposition 1.3.5. If overloaded, errors 1:1 Unknown identifier `y_k` invalid {...} notation, expected type is not known{y_k} is chosen by the rule (3.14), then (equation (3.15)).

theorem modified_selection_rule_monotone {E : Type*} [SeminormedAddCommGroup E] [NormedSpace ℝ E] [FiniteDimensional ℝ E] {Q : Set E} {f : E → ℝ} {L : ℝ} (xSeq ySeq : ℕ → Q) (hselect : ∀ k, ModifiedSelectionRule Q f L xSeq ySeq k) (h0 : f (ySeq 0) ≤ f (xSeq 0)) : (∀ k, f (ySeq (k + 1)) ≤ f (ySeq k)) ∧ (∀ k, f (ySeq k) ≤ f (xSeq 0)) := by have hmono_succ : ∀ k, f (ySeq (Nat.succ k)) ≤ f (ySeq k) := by intro k have hsel := hselect k dsimp [ModifiedSelectionRule] at hsel rcases hsel with ⟨_, hy_min⟩ have hyk_mem : ySeq k ∈ (({ySeq k} : Set Q) ∪ {xSeq (Nat.succ k)} ∪ {T_Q Q f L (xSeq (Nat.succ k))}) := by simp exact hy_min (ySeq k) hyk_mem have hmono : ∀ k, f (ySeq (k + 1)) ≤ f (ySeq k) := by intro k exact hmono_succ k have hbound_to_y0 : ∀ k, f (ySeq k) ≤ f (ySeq 0) := by intro k induction k with | zero => simp | succ k hk => exact le_trans (hmono_succ k) hk have hbound : ∀ k, f (ySeq k) ≤ f (xSeq 0) := by intro k exact le_trans (hbound_to_y0 k) h0 exact ⟨hmono, hbound⟩

The infimum defining Unknown identifier `ψ_k`ψ_k is bounded above by evaluation at any feasible point.

lemma section03_psi_k_le_eval_of_isMinOn {E : Type*} [NormedAddCommGroup E] [NormedSpace ℝ E] [FiniteDimensional ℝ E] {Q : Set E} {f d : E → ℝ} {L σ : ℝ} (α : ℕ → ℝ) (xSeq : ℕ → Q) (k : ℕ) (hzk_min : IsMinOn (fun x : E => (L / σ) * d x + Finset.sum (Finset.range (k + 1)) (fun i => α i * (f (xSeq i) + DualPairing ((fderiv ℝ f (xSeq i)).toLinearMap) (x - xSeq i)))) Q (z_k Q f d L σ α xSeq k : E)) : ∀ x ∈ Q, psi_k Q f d L σ α xSeq k ≤ (L / σ) * d x + Finset.sum (Finset.range (k + 1)) (fun i => α i * (f (xSeq i) + DualPairing ((fderiv ℝ f (xSeq i)).toLinearMap) (x - xSeq i))) := by classical let Fk : E → ℝ := fun x => (L / σ) * d x + Finset.sum (Finset.range (k + 1)) (fun i => α i * (f (xSeq i) + DualPairing ((fderiv ℝ f (xSeq i)).toLinearMap) (x - xSeq i))) have hBdd : BddBelow (Fk '' Q) := by refine ⟨Fk (z_k Q f d L σ α xSeq k : E), ?_⟩ intro b hb rcases hb with ⟨z, hz, rfl⟩ have hmin := (isMinOn_iff.mp hzk_min) z hz simpa [Fk] using hmin intro x hx have hpsi_le : psi_k Q f d L σ α xSeq k ≤ Fk x := by refine csInf_le hBdd ?_ exact ⟨x, hx, rfl⟩ simpa [psi_k, Fk] using hpsi_le

Upper bound Unknown identifier `ψ_k`ψ_k by evaluating the affine model at a point .

lemma section03_psik_upper_bound_at_xstar {E : Type*} [NormedAddCommGroup E] [NormedSpace ℝ E] [FiniteDimensional ℝ E] {Q : Set E} {f d : E → ℝ} {L σ : ℝ} (α : ℕ → ℝ) (xSeq : ℕ → Q) (k : ℕ) (hQ_convex : Convex ℝ Q) (hf_convex : ConvexOn ℝ Q f) (hf_diff : ∀ x ∈ Q, DifferentiableAt ℝ f x) (hα_pos : ∀ k, 0 < α k) (hzk_min : IsMinOn (fun x : E => (L / σ) * d x + Finset.sum (Finset.range (k + 1)) (fun i => α i * (f (xSeq i) + DualPairing ((fderiv ℝ f (xSeq i)).toLinearMap) (x - xSeq i)))) Q (z_k Q f d L σ α xSeq k : E)) : ∀ xstar ∈ Q, psi_k Q f d L σ α xSeq k ≤ (L / σ) * d xstar + A_k α k * f xstar := by classical intro xstar hxstar have hpsi_le := section03_psi_k_le_eval_of_isMinOn (α := α) (xSeq := xSeq) (k := k) (hzk_min := hzk_min) xstar hxstar have hsum_le : Finset.sum (Finset.range (k + 1)) (fun i => α i * (f (xSeq i) + DualPairing ((fderiv ℝ f (xSeq i)).toLinearMap) (xstar - xSeq i))) ≤ Finset.sum (Finset.range (k + 1)) (fun i => α i * f xstar) := by refine Finset.sum_le_sum ?_ intro i hi have hx_i : (xSeq i : E) ∈ Q := (xSeq i).property have hsupport : f xstar ≥ f (xSeq i) + DualPairing ((fderiv ℝ f (xSeq i)).toLinearMap) (xstar - xSeq i) := by exact section03_convex_support_fderiv (hQ_convex := hQ_convex) (hf_convex := hf_convex) (u := xstar) (v := (xSeq i : E)) hxstar hx_i (hf_diff (xSeq i) hx_i) have hα_nonneg : 0 ≤ α i := le_of_lt (hα_pos i) exact mul_le_mul_of_nonneg_left hsupport hα_nonneg have hsum_eq : Finset.sum (Finset.range (k + 1)) (fun i => α i * f xstar) = A_k α k * f xstar := by have hsum := (Finset.sum_mul (s := Finset.range (k + 1)) (f := α) (a := f xstar)) simpa [A_k, mul_comm, mul_left_comm, mul_assoc] using hsum.symm have hpsi_le' : psi_k Q f d L σ α xSeq k ≤ (L / σ) * d xstar + Finset.sum (Finset.range (k + 1)) (fun i => α i * f xstar) := by have h := add_le_add_left hsum_le ((L / σ) * d xstar) exact le_trans hpsi_le (by simpa [add_comm, add_left_comm, add_assoc] using h) calc psi_k Q f d L σ α xSeq k ≤ (L / σ) * d xstar + Finset.sum (Finset.range (k + 1)) (fun i => α i * f xstar) := hpsi_le' _ = (L / σ) * d xstar + A_k α k * f xstar := by simp [hsum_eq]

Convert 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 and an upper bound on Unknown identifier `ψ_k`ψ_k into a gap estimate.

lemma section03_rate_bound_from_Rk_and_psik_upper {E : Type*} [NormedAddCommGroup E] [NormedSpace ℝ E] [FiniteDimensional ℝ E] {Q : Set E} {f d : E → ℝ} {L σ : ℝ} (α : ℕ → ℝ) (xSeq ySeq : ℕ → Q) (xstar : E) (k : ℕ) (hA_pos : 0 < A_k α k) (hRk : R_k Q f d L σ α xSeq ySeq k) (hpsi : psi_k Q f d L σ α xSeq k ≤ (L / σ) * d xstar + A_k α k * f xstar) : f (ySeq k) - f xstar ≤ (L / σ) * d xstar / A_k α k := by have hcombine : A_k α k * f (ySeq k) ≤ (L / σ) * d xstar + A_k α k * f xstar := by exact le_trans hRk hpsi have hgap : A_k α k * (f (ySeq k) - f xstar) ≤ (L / σ) * d xstar := by linarith have hgap' : (f (ySeq k) - f xstar) * A_k α k ≤ (L / σ) * d xstar := by simpa [mul_comm, mul_left_comm, mul_assoc] using hgap have hA_ne : A_k α k ≠ 0 := ne_of_gt hA_pos have hAinv_pos : 0 < (A_k α k)⁻¹ := inv_pos.mpr hA_pos have hgap'' := mul_le_mul_of_nonneg_right hgap' (le_of_lt hAinv_pos) have hgap''' : f (ySeq k) - f xstar ≤ (L / σ) * d xstar / A_k α k := by simpa [div_eq_mul_inv, mul_assoc, hA_ne] using hgap'' exact hgap'''

The invariant 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 holds for all iterates of the optimal scheme.

lemma section03_optimalScheme_Rk_all {E : Type*} [NormedAddCommGroup E] [NormedSpace ℝ E] [FiniteDimensional ℝ E] {Q : Set E} {f d : E → ℝ} {L σ : ℝ} (xSeq ySeq : ℕ → Q) (hAlg : OptimalSchemeAlgorithm Q f d L σ xSeq ySeq) : ∀ k, R_k Q f d L σ (fun i => ((i : ℝ) + 1) / 2) xSeq ySeq k := by classical rcases hAlg with ⟨hQ_closed, hf_convex, hf_diff, hL, hgrad_lipschitz, hprox, hconv, hσ, hx0, hy0, hy_all, hzk_min_all, hx_update_all⟩ let α : ℕ → ℝ := fun i => ((i : ℝ) + 1) / 2 have hAlpha : (∀ k, A_k α k = ((k : ℝ) + 1) * ((k : ℝ) + 2) / 4) ∧ (∀ k, α (k + 1) / A_k α (k + 1) = 2 / ((k : ℝ) + 3)) ∧ α 0 ∈ Set.Ioc (0 : ℝ) 1 ∧ (∀ k, (α (k + 1)) ^ 2 ≤ A_k α (k + 1)) := by simpa [α] using (alpha_seq_closed_form) have hτ_formula := hAlpha.2.1 have hα0 := hAlpha.2.2.1 have hα_sq := hAlpha.2.2.2 have hα_pos : ∀ k, 0 < α k := by intro k have hk_nonneg : (0 : ℝ) ≤ (k : ℝ) := by exact_mod_cast (Nat.zero_le k) have hk1_pos : 0 < (k : ℝ) + 1 := by linarith have h2_pos : (0 : ℝ) < 2 := by norm_num simpa [α] using (div_pos hk1_pos h2_pos) have hQ_convex : Convex ℝ Q := hconv.1 have hR0 : R_k Q f d L σ α xSeq ySeq 0 := by refine R0_relation (α := α) (hQ_closed := hQ_closed) (hQ_convex := hQ_convex) (hf_diff := hf_diff) (hL := hL) (hgrad_lipschitz := hgrad_lipschitz) (hconv := hconv) (hσ := hσ) (xSeq := xSeq) (ySeq := ySeq) (x0 := xSeq 0) (hx0 := hx0) (hα0 := hα0) (hxSeq0 := rfl) (hySeq0 := hy0) intro k induction k with | zero => simpa [α] using hR0 | succ k hk => have hτ : α (k + 1) / A_k α (k + 1) = 2 / ((k : ℝ) + 3) := hτ_formula k have hτ' : 1 - α (k + 1) / A_k α (k + 1) = ((k : ℝ) + 1) / ((k : ℝ) + 3) := by have hk_nonneg : (0 : ℝ) ≤ (k : ℝ) := by exact_mod_cast (Nat.zero_le k) have hk3_pos : 0 < (k : ℝ) + 3 := by linarith have hk3_ne : (k : ℝ) + 3 ≠ 0 := ne_of_gt hk3_pos calc 1 - α (k + 1) / A_k α (k + 1) = 1 - 2 / ((k : ℝ) + 3) := by simp [hτ] _ = ((k : ℝ) + 1) / ((k : ℝ) + 3) := by field_simp [hk3_ne] ring have 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) := by have hx := hx_update_all k rw [hτ', hτ] simpa [α] using hx have hy_update : ySeq (k + 1) = T_Q Q f L (xSeq (k + 1)) := by simpa using hy_all (k + 1) have hzk_min : IsMinOn (z_k_objective Q f d L σ α xSeq k) Q (z_k Q f d L σ α xSeq k : E) := by simpa [α, z_k_objective] using hzk_min_all k exact Rk_succ_update (α := α) (hQ_closed := hQ_closed) (hQ_convex := hQ_convex) (hf_convex := hf_convex) (hf_diff := hf_diff) (hL := hL) (hgrad_lipschitz := hgrad_lipschitz) (hconv := hconv) (hσ := hσ) (xSeq := xSeq) (ySeq := ySeq) (k := k) (hα_pos := hα_pos) (hα_sq := hα_sq) (hRk := hk) (hzk_min := hzk_min) (hx_update := hx_update) (hy_update := hy_update)

Theorem 1.3.1. Let sequences Ambiguous use of subset notation: the type is a metavariable. Consider adding a type annotation, e.g. `(_ : Set _) ⊆ _`. The term will elaborate to a different constant depending on whether the type is tagged with `@[use_set_notation_for_order]`. Note: This linter can be disabled with `set_option linter.setNotationForOrder false`overloaded, errors 1:1 Unknown identifier `x_k` invalid {...} notation, expected type is not knownsorry ⊆ sorry : Prop{x_k} ⊆ Unknown identifier `Q`Q and Ambiguous use of subset notation: the type is a metavariable. Consider adding a type annotation, e.g. `(_ : Set _) ⊆ _`. The term will elaborate to a different constant depending on whether the type is tagged with `@[use_set_notation_for_order]`. Note: This linter can be disabled with `set_option linter.setNotationForOrder false`overloaded, errors 1:1 Unknown identifier `y_k` invalid {...} notation, expected type is not knownsorry ⊆ sorry : Prop{y_k} ⊆ Unknown identifier `Q`Q be generated by Algorithm 1.3.1. Then for any Unknown identifier `k`sorry ≥ 0 : Propk ≥ 0, `((k+1)(k+2)/4) f(y_k) ≤ min_{x ∈ Q} { (L/σ) d x + ∑_{i=0}^k (i+1)/2 [ f(x_i)

  • ⟪∇ f(x_i), x - x_i⟫ ] }(Unknown identifier `equation`equation (3.12))Invalid field notation: Identifier or numeral expected. Ifx* ∈ argmin_{x ∈ Q} f x, then f(y_k) - f(x*) ≤ 4 L d(x*) / (σ (k+1)(k+2))` (equation (3.13)).

theorem optimal_scheme_rate {E : Type*} [NormedAddCommGroup E] [NormedSpace ℝ E] [FiniteDimensional ℝ E] {Q : Set E} {f d : E → ℝ} {L σ : ℝ} (xSeq ySeq : ℕ → Q) (hAlg : OptimalSchemeAlgorithm Q f d L σ xSeq ySeq) : (∀ k : ℕ, (((k : ℝ) + 1) * ((k : ℝ) + 2) / 4) * f (ySeq k) ≤ psi_k Q f d L σ (fun i => ((i : ℝ) + 1) / 2) xSeq k) ∧ (∀ xstar : E, xstar ∈ Q → (∀ y ∈ Q, f xstar ≤ f y) → ∀ k : ℕ, f (ySeq k) - f xstar ≤ (4 * L * d xstar) / (σ * ((k : ℝ) + 1) * ((k : ℝ) + 2))) := by classical have hRk_all : ∀ k, R_k Q f d L σ (fun i => ((i : ℝ) + 1) / 2) xSeq ySeq k := section03_optimalScheme_Rk_all (xSeq := xSeq) (ySeq := ySeq) hAlg rcases hAlg with ⟨hQ_closed, hf_convex, hf_diff, hL, hgrad_lipschitz, hprox, hconv, hσ, hx0, hy0, hy_all, hzk_min_all, hx_update_all⟩ let α : ℕ → ℝ := fun i => ((i : ℝ) + 1) / 2 have hAlpha : (∀ k, A_k α k = ((k : ℝ) + 1) * ((k : ℝ) + 2) / 4) ∧ (∀ k, α (k + 1) / A_k α (k + 1) = 2 / ((k : ℝ) + 3)) ∧ α 0 ∈ Set.Ioc (0 : ℝ) 1 ∧ (∀ k, (α (k + 1)) ^ 2 ≤ A_k α (k + 1)) := by simpa [α] using (alpha_seq_closed_form) have hA_formula := hAlpha.1 have hα_pos : ∀ k, 0 < α k := by intro k have hk_nonneg : (0 : ℝ) ≤ (k : ℝ) := by exact_mod_cast (Nat.zero_le k) have hk1_pos : 0 < (k : ℝ) + 1 := by linarith have h2_pos : (0 : ℝ) < 2 := by norm_num simpa [α] using (div_pos hk1_pos h2_pos) have hQ_convex : Convex ℝ Q := hconv.1 refine ⟨?_, ?_⟩ · intro k have hRk := hRk_all k have hA_formula' : A_k (fun i => ((i : ℝ) + 1) / 2) k = ((k : ℝ) + 1) * ((k : ℝ) + 2) / 4 := by simpa [α] using hA_formula k simpa [R_k, hA_formula'] using hRk · intro xstar hxstar hxstar_min k have hpsi_upper : psi_k Q f d L σ α xSeq k ≤ (L / σ) * d xstar + A_k α k * f xstar := by have hzk_min : IsMinOn (z_k_objective Q f d L σ α xSeq k) Q (z_k Q f d L σ α xSeq k : E) := by simpa [α, z_k_objective] using hzk_min_all k exact section03_psik_upper_bound_at_xstar (α := α) (xSeq := xSeq) (k := k) (hQ_convex := hQ_convex) (hf_convex := hf_convex) (hf_diff := hf_diff) (hα_pos := hα_pos) (hzk_min := hzk_min) xstar hxstar have hA_pos : 0 < A_k α k := by have hα_nonneg : ∀ i ∈ Finset.range (k + 1), 0 ≤ α i := by intro i hi exact le_of_lt (hα_pos i) have hmem : 0 ∈ Finset.range (k + 1) := by simp have hA_ge : α 0 ≤ A_k α k := by simpa [A_k] using (Finset.single_le_sum hα_nonneg hmem) exact lt_of_lt_of_le (hα_pos 0) hA_ge have hgap := section03_rate_bound_from_Rk_and_psik_upper (α := α) (xSeq := xSeq) (ySeq := ySeq) (xstar := xstar) (k := k) (hA_pos := hA_pos) (hRk := hRk_all k) (hpsi := hpsi_upper) have hk_nonneg : (0 : ℝ) ≤ (k : ℝ) := by exact_mod_cast (Nat.zero_le k) have hk1_pos : 0 < (k : ℝ) + 1 := by linarith have hk2_pos : 0 < (k : ℝ) + 2 := by linarith have hk1_ne : (k : ℝ) + 1 ≠ 0 := ne_of_gt hk1_pos have hk2_ne : (k : ℝ) + 2 ≠ 0 := ne_of_gt hk2_pos have hσ_ne : (σ : ℝ) ≠ 0 := ne_of_gt hσ have hrewrite : (L / σ) * d xstar / A_k α k = (4 * L * d xstar) / (σ * ((k : ℝ) + 1) * ((k : ℝ) + 2)) := by calc (L / σ) * d xstar / A_k α k = (L / σ) * d xstar / (((k : ℝ) + 1) * ((k : ℝ) + 2) / 4) := by simp [hA_formula k] _ = (4 * L * d xstar) / (σ * ((k : ℝ) + 1) * ((k : ℝ) + 2)) := by field_simp [hσ_ne, hk1_ne, hk2_ne] simpa [hrewrite] using hgap