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

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

Source header · Attribution source

open scoped NNReal

The averaging weights from equation (4.2).

noncomputable def averagedDualWeight (N i : ℕ) : ℝ := 2 * ((i : ℝ) + 1) / (((N : ℝ) + 1) * ((N : ℝ) + 2))
lemma averagedDualWeight_nonneg (N i : ℕ) : 0 ≤ averagedDualWeight N i := by have h1 : 0 < (N : ℝ) + 1 := by nlinarith have h2 : 0 < (N : ℝ) + 2 := by nlinarith have hi : 0 ≤ (i : ℝ) + 1 := by nlinarith have hnum : 0 ≤ 2 * ((i : ℝ) + 1) := by nlinarith exact div_nonneg hnum (le_of_lt (mul_pos h1 h2))

The averaging weights from (4.2) sum to 1 : ℕ1.

lemma averagedDualWeight_sum (N : ℕ) : Finset.sum (Finset.range (N + 1)) (fun i => averagedDualWeight N i) = (1 : ℝ) := by set denom : ℝ := ((N : ℝ) + 1) * ((N : ℝ) + 2) have hdenom_pos : 0 < denom := by have h1 : 0 < (N : ℝ) + 1 := by nlinarith have h2 : 0 < (N : ℝ) + 2 := by nlinarith simpa [denom] using mul_pos h1 h2 have hsum := sum_range_add_one_cast N calc Finset.sum (Finset.range (N + 1)) (fun i => averagedDualWeight N i) = Finset.sum (Finset.range (N + 1)) (fun i => (2 / denom) * ((i : ℝ) + 1)) := by refine Finset.sum_congr rfl ?_ intro i hi simp [averagedDualWeight, denom, div_eq_mul_inv, mul_comm, mul_assoc] _ = (2 / denom) * Finset.sum (Finset.range (N + 1)) (fun i => ((i : ℝ) + 1)) := by symm simpa using (Finset.mul_sum (s := Finset.range (N + 1)) (f := fun i => ((i : ℝ) + 1)) (a := (2 / denom))) _ = (2 / denom) * (denom / 2) := by simp [hsum, denom] _ = (1 : ℝ) := by field_simp [denom, hdenom_pos.ne']

The averaged dual point from equation (4.2) for a chosen maximizing branch.

noncomputable def averagedDualPoint_of_isSmoothedMaximizer {E1 E2 : Type*} [NormedAddCommGroup E1] [NormedSpace ℝ E1] [FiniteDimensional ℝ E1] [NormedAddCommGroup E2] [NormedSpace ℝ E2] [FiniteDimensional ℝ E2] (Q2 : Set E2) (A : E1 →L[ℝ] (E2 →L[ℝ] ℝ)) (phihat d2 : E2 → ℝ) (μ : ℝ) (uμ : E1 → E2) (xSeq : ℕ → E1) (N : ℕ) (hQ2_convex : Convex ℝ Q2) (hmax : ∀ x, IsSmoothedMaximizer Q2 A phihat d2 μ x (uμ x)) : Q2 := by classical refine ⟨Finset.sum (Finset.range (N + 1)) (fun i => averagedDualWeight N i • uμ (xSeq i)), ?_⟩ refine hQ2_convex.sum_mem ?_ ?_ ?_ · intro i hi exact averagedDualWeight_nonneg N i · exact averagedDualWeight_sum N · intro i hi exact (hmax (xSeq i)).1
@[simp] theorem averagedDualPoint_of_isSmoothedMaximizer_coe {E1 E2 : Type*} [NormedAddCommGroup E1] [NormedSpace ℝ E1] [FiniteDimensional ℝ E1] [NormedAddCommGroup E2] [NormedSpace ℝ E2] [FiniteDimensional ℝ E2] (Q2 : Set E2) (A : E1 →L[ℝ] (E2 →L[ℝ] ℝ)) (phihat d2 : E2 → ℝ) (μ : ℝ) (uμ : E1 → E2) (xSeq : ℕ → E1) (N : ℕ) (hQ2_convex : Convex ℝ Q2) (hmax : ∀ x, IsSmoothedMaximizer Q2 A phihat d2 μ x (uμ x)) : ((averagedDualPoint_of_isSmoothedMaximizer (Q2 := Q2) (A := A) (phihat := phihat) (d2 := d2) (μ := μ) (uμ := uμ) (xSeq := xSeq) (N := N) (hQ2_convex := hQ2_convex) (hmax := hmax) : Q2) : E2) = Finset.sum (Finset.range (N + 1)) (fun i => averagedDualWeight N i • uμ (xSeq i)) := rfl

The averaged dual point from equation (4.2), using smoothedMaximizer.{u_1, u_2} {E1 : Type u_1} {E2 : Type u_2} [NormedAddCommGroup E1] [NormedSpace ℝ E1] [FiniteDimensional ℝ E1] [NormedAddCommGroup E2] [NormedSpace ℝ E2] [FiniteDimensional ℝ E2] (Q2 : Set E2) (A : E1 →L[ℝ] E2 →L[ℝ] ℝ) (phihat d2 : E2 → ℝ) (μ : ℝ) (hQ2_closed : IsClosed Q2) (hQ2_bdd : Bornology.IsBounded Q2) (hQ2_nonempty : Q2.Nonempty) (hphihat : ContinuousOn phihat Q2) (hd2 : ContinuousOn d2 Q2) (x : E1) : E2smoothedMaximizer.

noncomputable def averagedDualPoint {E1 E2 : Type*} [NormedAddCommGroup E1] [NormedSpace ℝ E1] [FiniteDimensional ℝ E1] [NormedAddCommGroup E2] [NormedSpace ℝ E2] [FiniteDimensional ℝ E2] (Q2 : Set E2) (A : E1 →L[ℝ] (E2 →L[ℝ] ℝ)) (phihat d2 : E2 → ℝ) (μ : ℝ) (xSeq : ℕ → E1) (N : ℕ) (hQ2_convex : Convex ℝ Q2) (hQ2_closed : IsClosed Q2) (hQ2_bdd : Bornology.IsBounded Q2) (hQ2_nonempty : Q2.Nonempty) (hphihat : ContinuousOn phihat Q2) (hd2 : ContinuousOn d2 Q2) : Q2 := averagedDualPoint_of_isSmoothedMaximizer (Q2 := Q2) (A := A) (phihat := phihat) (d2 := d2) (μ := μ) (uμ := smoothedMaximizer Q2 A phihat d2 μ hQ2_closed hQ2_bdd hQ2_nonempty hphihat hd2) (xSeq := xSeq) (N := N) (hQ2_convex := hQ2_convex) (hmax := smoothedMaximizer_isSmoothedMaximizer (Q2 := Q2) (A := A) (phihat := phihat) (d2 := d2) (μ := μ) hQ2_closed hQ2_bdd hQ2_nonempty hphihat hd2)

Weighted linearization sum bound using the averaged dual point for a chosen maximizing branch. This is the general-branch helper form.

lemma weighted_sum_bound_hatu_of_isSmoothedMaximizer {E1 E2 : Type*} [NormedAddCommGroup E1] [NormedSpace ℝ E1] [FiniteDimensional ℝ E1] [NormedAddCommGroup E2] [NormedSpace ℝ E2] [FiniteDimensional ℝ E2] (Q1 : Set E1) (Q2 : Set E2) (A : E1 →L[ℝ] (E2 →L[ℝ] ℝ)) (fhat : E1 → ℝ) (phihat d2 : E2 → ℝ) (μ σ2 : ℝ) (uμ : E1 → E2) (xSeq : ℕ → Q1) (N : ℕ) (hatu : Q2) (hhatudef : (hatu : E2) = Finset.sum (Finset.range (N + 1)) (fun i => (2 * ((i : ℝ) + 1) / (((N : ℝ) + 1) * ((N : ℝ) + 2))) • uμ (xSeq i : E1))) (hQ1_open : IsOpen Q1) (hQ1_convex : Convex ℝ Q1) (hfhat_convex : ConvexOn ℝ Q1 fhat) (hfhat_diff : DifferentiableOn ℝ fhat Q1) (hphihat_convex : ConvexOn ℝ Q2 phihat) (hμ : 0 < μ) (hσ2 : 0 < σ2) (hconv : StrongConvexOn Q2 σ2 d2) (hd2_nonneg : ∀ u ∈ Q2, 0 ≤ d2 u) (hmax : ∀ x, IsSmoothedMaximizer Q2 A phihat d2 μ x (uμ x)) : ∀ x ∈ Q1, Finset.sum (Finset.range (N + 1)) (fun i => ((i : ℝ) + 1) * (SmoothedObjective Q2 A phihat d2 μ fhat (xSeq i : E1) + DualPairing ((fderiv ℝ (SmoothedObjective Q2 A phihat d2 μ fhat) (xSeq i)).toLinearMap) (x - xSeq i))) ≤ ((N : ℝ) + 1) * ((N : ℝ) + 2) / 2 * (fhat x + A x hatu - phihat hatu) := by classical intro x hx set denom : ℝ := ((N : ℝ) + 1) * ((N : ℝ) + 2) have hdenom_pos : 0 < denom := by have h1 : 0 < (N : ℝ) + 1 := by nlinarith have h2 : 0 < (N : ℝ) + 2 := by nlinarith simpa [denom] using mul_pos h1 h2 have hsum_w : Finset.sum (Finset.range (N + 1)) (fun i => (2 * ((i : ℝ) + 1) / denom)) = (1 : ℝ) := by have hsum := sum_range_add_one_cast N have hterm : ∀ i, 2 * ((i : ℝ) + 1) / denom = (2 / denom) * ((i : ℝ) + 1) := by intro i simp [div_eq_mul_inv, mul_comm, mul_assoc] calc Finset.sum (Finset.range (N + 1)) (fun i => 2 * ((i : ℝ) + 1) / denom) = Finset.sum (Finset.range (N + 1)) (fun i => (2 / denom) * ((i : ℝ) + 1)) := by refine Finset.sum_congr rfl ?_ intro i hi simp [hterm i] _ = (2 / denom) * Finset.sum (Finset.range (N + 1)) (fun i => ((i : ℝ) + 1)) := by symm simpa using (Finset.mul_sum (s := Finset.range (N + 1)) (f := fun i => ((i : ℝ) + 1)) (a := (2 / denom))) _ = (2 / denom) * (denom / 2) := by simp [hsum, denom] _ = (1 : ℝ) := by field_simp [denom, hdenom_pos.ne'] have hnonneg_w : ∀ i ∈ Finset.range (N + 1), 0 ≤ 2 * ((i : ℝ) + 1) / denom := by intro i hi have hi' : 0 ≤ (i : ℝ) + 1 := by nlinarith have hnum : 0 ≤ 2 * ((i : ℝ) + 1) := by nlinarith exact div_nonneg hnum (le_of_lt hdenom_pos) have hmem_u : ∀ i ∈ Finset.range (N + 1), uμ (xSeq i : E1) ∈ Q2 := by intro i hi exact (hmax (xSeq i)).1 have hphihat_jensen : phihat hatu ≤ Finset.sum (Finset.range (N + 1)) (fun i => (2 * ((i : ℝ) + 1) / denom) * phihat (uμ (xSeq i : E1))) := by have h := ConvexOn.map_sum_le (t := Finset.range (N + 1)) (w := fun i => 2 * ((i : ℝ) + 1) / denom) (p := fun i => uμ (xSeq i : E1)) hphihat_convex hnonneg_w hsum_w hmem_u simpa [hhatudef, smul_eq_mul, denom] using h have hphihat_sum : (denom / 2) * phihat hatu ≤ Finset.sum (Finset.range (N + 1)) (fun i => ((i : ℝ) + 1) * phihat (uμ (xSeq i : E1))) := by have hcoef_nonneg : 0 ≤ denom / 2 := by nlinarith [hdenom_pos] have hdenom_ne : denom ≠ 0 := by nlinarith [hdenom_pos] have hmul := mul_le_mul_of_nonneg_left hphihat_jensen hcoef_nonneg have hsum : (denom / 2) * Finset.sum (Finset.range (N + 1)) (fun i => (2 * ((i : ℝ) + 1) / denom) * phihat (uμ (xSeq i : E1))) = Finset.sum (Finset.range (N + 1)) (fun i => ((i : ℝ) + 1) * phihat (uμ (xSeq i : E1))) := by calc (denom / 2) * Finset.sum (Finset.range (N + 1)) (fun i => (2 * ((i : ℝ) + 1) / denom) * phihat (uμ (xSeq i : E1))) = Finset.sum (Finset.range (N + 1)) (fun i => (denom / 2) * ((2 * ((i : ℝ) + 1) / denom) * phihat (uμ (xSeq i : E1)))) := by simpa using (Finset.mul_sum (s := Finset.range (N + 1)) (f := fun i => (2 * ((i : ℝ) + 1) / denom) * phihat (uμ (xSeq i : E1))) (a := denom / 2)) _ = Finset.sum (Finset.range (N + 1)) (fun i => ((i : ℝ) + 1) * phihat (uμ (xSeq i : E1))) := by refine Finset.sum_congr rfl ?_ intro i hi field_simp [denom, hdenom_ne, mul_comm, mul_left_comm, mul_assoc] simpa [hsum] using hmul have hAx_hatu : A x hatu = Finset.sum (Finset.range (N + 1)) (fun i => (2 * ((i : ℝ) + 1) / denom) * A x (uμ (xSeq i : E1))) := by calc A x hatu = A x (Finset.sum (Finset.range (N + 1)) (fun i => (2 * ((i : ℝ) + 1) / denom) • uμ (xSeq i : E1))) := by simp [hhatudef] _ = Finset.sum (Finset.range (N + 1)) (fun i => (2 * ((i : ℝ) + 1) / denom) • A x (uμ (xSeq i : E1))) := by simp [map_sum, smul_eq_mul] _ = Finset.sum (Finset.range (N + 1)) (fun i => (2 * ((i : ℝ) + 1) / denom) * A x (uμ (xSeq i : E1))) := by simp [smul_eq_mul] have hAx_sum : Finset.sum (Finset.range (N + 1)) (fun i => ((i : ℝ) + 1) * A x (uμ (xSeq i : E1))) = (denom / 2) * A x hatu := by have hdenom_ne : denom ≠ 0 := by nlinarith [hdenom_pos] calc Finset.sum (Finset.range (N + 1)) (fun i => ((i : ℝ) + 1) * A x (uμ (xSeq i : E1))) = (denom / 2) * Finset.sum (Finset.range (N + 1)) (fun i => (2 * ((i : ℝ) + 1) / denom) * A x (uμ (xSeq i : E1))) := by symm calc (denom / 2) * Finset.sum (Finset.range (N + 1)) (fun i => (2 * ((i : ℝ) + 1) / denom) * A x (uμ (xSeq i : E1))) = Finset.sum (Finset.range (N + 1)) (fun i => (denom / 2) * ((2 * ((i : ℝ) + 1) / denom) * A x (uμ (xSeq i : E1)))) := by simpa using (Finset.mul_sum (s := Finset.range (N + 1)) (f := fun i => (2 * ((i : ℝ) + 1) / denom) * A x (uμ (xSeq i : E1))) (a := denom / 2)) _ = Finset.sum (Finset.range (N + 1)) (fun i => ((i : ℝ) + 1) * A x (uμ (xSeq i : E1))) := by refine Finset.sum_congr rfl ?_ intro i hi field_simp [denom, hdenom_ne, mul_comm, mul_left_comm, mul_assoc] _ = (denom / 2) * A x hatu := by simp [hAx_hatu] have hsum_fhat : Finset.sum (Finset.range (N + 1)) (fun i => ((i : ℝ) + 1) * fhat x) = (denom / 2) * fhat x := by calc Finset.sum (Finset.range (N + 1)) (fun i => ((i : ℝ) + 1) * fhat x) = Finset.sum (Finset.range (N + 1)) (fun i => fhat x * ((i : ℝ) + 1)) := by refine Finset.sum_congr rfl ?_ intro i hi simp [mul_comm] _ = (Finset.sum (Finset.range (N + 1)) (fun i => ((i : ℝ) + 1))) * fhat x := by simpa [mul_comm] using (Finset.sum_mul (s := Finset.range (N + 1)) (f := fun i => ((i : ℝ) + 1)) (a := fhat x)).symm _ = (denom / 2) * fhat x := by simp [sum_range_add_one_cast, denom] have hterm_le : ∀ i, SmoothedObjective Q2 A phihat d2 μ fhat (xSeq i : E1) + DualPairing ((fderiv ℝ (SmoothedObjective Q2 A phihat d2 μ fhat) (xSeq i)).toLinearMap) (x - xSeq i) ≤ fhat x + A x (uμ (xSeq i : E1)) - phihat (uμ (xSeq i : E1)) := by intro i exact smoothedObjective_linearization_of_isSmoothedMaximizer (Q1 := Q1) (Q2 := Q2) (A := A) (fhat := fhat) (phihat := phihat) (d2 := d2) (μ := μ) (σ2 := σ2) (uμ := uμ) (hQ1_open := hQ1_open) (hQ1_convex := hQ1_convex) (hfhat_convex := hfhat_convex) (hfhat_diff := hfhat_diff) (hphi := hphihat_convex) (hμ := hμ) (hσ2 := hσ2) (hconv := hconv) (hd2_nonneg := hd2_nonneg) (hmax := hmax) x hx (xSeq i) (xSeq i).property have hsum_term : Finset.sum (Finset.range (N + 1)) (fun i => ((i : ℝ) + 1) * (SmoothedObjective Q2 A phihat d2 μ fhat (xSeq i : E1) + DualPairing ((fderiv ℝ (SmoothedObjective Q2 A phihat d2 μ fhat) (xSeq i)).toLinearMap) (x - xSeq i))) ≤ Finset.sum (Finset.range (N + 1)) (fun i => ((i : ℝ) + 1) * (fhat x + A x (uμ (xSeq i : E1)) - phihat (uμ (xSeq i : E1)))) := by refine Finset.sum_le_sum ?_ intro i hi have hnonneg : 0 ≤ (i : ℝ) + 1 := by nlinarith exact mul_le_mul_of_nonneg_left (hterm_le i) hnonneg have hsum_rhs : Finset.sum (Finset.range (N + 1)) (fun i => ((i : ℝ) + 1) * (fhat x + A x (uμ (xSeq i : E1)) - phihat (uμ (xSeq i : E1)))) = (denom / 2) * fhat x + Finset.sum (Finset.range (N + 1)) (fun i => ((i : ℝ) + 1) * A x (uμ (xSeq i : E1))) - Finset.sum (Finset.range (N + 1)) (fun i => ((i : ℝ) + 1) * phihat (uμ (xSeq i : E1))) := by simp [mul_add, mul_sub, Finset.sum_add_distrib, Finset.sum_sub_distrib, hsum_fhat] have hfinal_rhs : (denom / 2) * fhat x + Finset.sum (Finset.range (N + 1)) (fun i => ((i : ℝ) + 1) * A x (uμ (xSeq i : E1))) - Finset.sum (Finset.range (N + 1)) (fun i => ((i : ℝ) + 1) * phihat (uμ (xSeq i : E1))) ≤ (denom / 2) * (fhat x + A x hatu - phihat hatu) := by have hphihat_sum' : -Finset.sum (Finset.range (N + 1)) (fun i => ((i : ℝ) + 1) * phihat (uμ (xSeq i : E1))) ≤ -(denom / 2) * phihat hatu := by linarith [hphihat_sum] have hAx_sum' : Finset.sum (Finset.range (N + 1)) (fun i => ((i : ℝ) + 1) * A x (uμ (xSeq i : E1))) = (denom / 2) * A x hatu := hAx_sum have hsum_fhat' : Finset.sum (Finset.range (N + 1)) (fun i => ((i : ℝ) + 1) * fhat x) = (denom / 2) * fhat x := hsum_fhat linarith [hAx_sum', hsum_fhat', hphihat_sum'] calc Finset.sum (Finset.range (N + 1)) (fun i => ((i : ℝ) + 1) * (SmoothedObjective Q2 A phihat d2 μ fhat (xSeq i : E1) + DualPairing ((fderiv ℝ (SmoothedObjective Q2 A phihat d2 μ fhat) (xSeq i)).toLinearMap) (x - xSeq i))) ≤ Finset.sum (Finset.range (N + 1)) (fun i => ((i : ℝ) + 1) * (fhat x + A x (uμ (xSeq i : E1)) - phihat (uμ (xSeq i : E1)))) := hsum_term _ = (denom / 2) * fhat x + Finset.sum (Finset.range (N + 1)) (fun i => ((i : ℝ) + 1) * A x (uμ (xSeq i : E1))) - Finset.sum (Finset.range (N + 1)) (fun i => ((i : ℝ) + 1) * phihat (uμ (xSeq i : E1))) := hsum_rhs _ ≤ (denom / 2) * (fhat x + A x hatu - phihat hatu) := hfinal_rhs

Canonical weighted linearization bound using the unique optimizer selected by smoothedMaximizer.{u_1, u_2} {E1 : Type u_1} {E2 : Type u_2} [NormedAddCommGroup E1] [NormedSpace ℝ E1] [FiniteDimensional ℝ E1] [NormedAddCommGroup E2] [NormedSpace ℝ E2] [FiniteDimensional ℝ E2] (Q2 : Set E2) (A : E1 →L[ℝ] E2 →L[ℝ] ℝ) (phihat d2 : E2 → ℝ) (μ : ℝ) (hQ2_closed : IsClosed Q2) (hQ2_bdd : Bornology.IsBounded Q2) (hQ2_nonempty : Q2.Nonempty) (hphihat : ContinuousOn phihat Q2) (hd2 : ContinuousOn d2 Q2) (x : E1) : E2smoothedMaximizer.

lemma weighted_sum_bound_hatu {E1 E2 : Type*} [NormedAddCommGroup E1] [NormedSpace ℝ E1] [FiniteDimensional ℝ E1] [NormedAddCommGroup E2] [NormedSpace ℝ E2] [FiniteDimensional ℝ E2] (Q1 : Set E1) (Q2 : Set E2) (A : E1 →L[ℝ] (E2 →L[ℝ] ℝ)) (fhat : E1 → ℝ) (phihat d2 : E2 → ℝ) (μ σ2 : ℝ) (xSeq : ℕ → Q1) (N : ℕ) (hatu : Q2) (hQ2_closed : IsClosed Q2) (hQ2_bdd : Bornology.IsBounded Q2) (hQ2_nonempty : Q2.Nonempty) (hphihat : ContinuousOn phihat Q2) (hd2 : ContinuousOn d2 Q2) (hhatudef : (hatu : E2) = Finset.sum (Finset.range (N + 1)) (fun i => (2 * ((i : ℝ) + 1) / (((N : ℝ) + 1) * ((N : ℝ) + 2))) • (smoothedMaximizer Q2 A phihat d2 μ hQ2_closed hQ2_bdd hQ2_nonempty hphihat hd2) (xSeq i : E1))) (hQ1_open : IsOpen Q1) (hQ1_convex : Convex ℝ Q1) (hfhat_convex : ConvexOn ℝ Q1 fhat) (hfhat_diff : DifferentiableOn ℝ fhat Q1) (hphihat_convex : ConvexOn ℝ Q2 phihat) (hμ : 0 < μ) (hσ2 : 0 < σ2) (hconv : StrongConvexOn Q2 σ2 d2) (hd2_nonneg : ∀ u ∈ Q2, 0 ≤ d2 u) : ∀ x ∈ Q1, Finset.sum (Finset.range (N + 1)) (fun i => ((i : ℝ) + 1) * (SmoothedObjective Q2 A phihat d2 μ fhat (xSeq i : E1) + DualPairing ((fderiv ℝ (SmoothedObjective Q2 A phihat d2 μ fhat) (xSeq i)).toLinearMap) (x - xSeq i))) ≤ ((N : ℝ) + 1) * ((N : ℝ) + 2) / 2 * (fhat x + A x hatu - phihat hatu) := by classical exact weighted_sum_bound_hatu_of_isSmoothedMaximizer (Q1 := Q1) (Q2 := Q2) (A := A) (fhat := fhat) (phihat := phihat) (d2 := d2) (μ := μ) (σ2 := σ2) (uμ := smoothedMaximizer Q2 A phihat d2 μ hQ2_closed hQ2_bdd hQ2_nonempty hphihat hd2) (xSeq := xSeq) (N := N) (hatu := hatu) hhatudef (hQ1_open := hQ1_open) (hQ1_convex := hQ1_convex) (hfhat_convex := hfhat_convex) (hfhat_diff := hfhat_diff) (hphihat_convex := hphihat_convex) (hμ := hμ) (hσ2 := hσ2) (hconv := hconv) (hd2_nonneg := hd2_nonneg) (hmax := smoothedMaximizer_isSmoothedMaximizer (Q2 := Q2) (A := A) (phihat := phihat) (d2 := d2) (μ := μ) hQ2_closed hQ2_bdd hQ2_nonempty hphihat hd2)

Weighted linearization bound using the canonical averaged dual point from equation (4.2), for a chosen maximizing branch.

lemma weighted_sum_bound_averagedDualPoint_of_isSmoothedMaximizer {E1 E2 : Type*} [NormedAddCommGroup E1] [NormedSpace ℝ E1] [FiniteDimensional ℝ E1] [NormedAddCommGroup E2] [NormedSpace ℝ E2] [FiniteDimensional ℝ E2] (Q1 : Set E1) (Q2 : Set E2) (A : E1 →L[ℝ] (E2 →L[ℝ] ℝ)) (fhat : E1 → ℝ) (phihat d2 : E2 → ℝ) (μ σ2 : ℝ) (uμ : E1 → E2) (xSeq : ℕ → Q1) (N : ℕ) (hQ1_open : IsOpen Q1) (hQ1_convex : Convex ℝ Q1) (hQ2_convex : Convex ℝ Q2) (hfhat_convex : ConvexOn ℝ Q1 fhat) (hfhat_diff : DifferentiableOn ℝ fhat Q1) (hphihat_convex : ConvexOn ℝ Q2 phihat) (hμ : 0 < μ) (hσ2 : 0 < σ2) (hconv : StrongConvexOn Q2 σ2 d2) (hd2_nonneg : ∀ u ∈ Q2, 0 ≤ d2 u) (hmax : ∀ x, IsSmoothedMaximizer Q2 A phihat d2 μ x (uμ x)) : let hatu : Q2 := averagedDualPoint_of_isSmoothedMaximizer (Q2 := Q2) (A := A) (phihat := phihat) (d2 := d2) (μ := μ) (uμ := uμ) (xSeq := fun i => (xSeq i : E1)) (N := N) (hQ2_convex := hQ2_convex) (hmax := hmax) ∀ x ∈ Q1, Finset.sum (Finset.range (N + 1)) (fun i => ((i : ℝ) + 1) * (SmoothedObjective Q2 A phihat d2 μ fhat (xSeq i : E1) + DualPairing ((fderiv ℝ (SmoothedObjective Q2 A phihat d2 μ fhat) (xSeq i)).toLinearMap) (x - xSeq i))) ≤ ((N : ℝ) + 1) * ((N : ℝ) + 2) / 2 * (fhat x + A x hatu - phihat hatu) := by classical simp only exact weighted_sum_bound_hatu_of_isSmoothedMaximizer (Q1 := Q1) (Q2 := Q2) (A := A) (fhat := fhat) (phihat := phihat) (d2 := d2) (μ := μ) (σ2 := σ2) (uμ := uμ) (xSeq := xSeq) (N := N) (hatu := averagedDualPoint_of_isSmoothedMaximizer (Q2 := Q2) (A := A) (phihat := phihat) (d2 := d2) (μ := μ) (uμ := uμ) (xSeq := fun i => (xSeq i : E1)) (N := N) (hQ2_convex := hQ2_convex) (hmax := hmax)) (by simp [averagedDualPoint_of_isSmoothedMaximizer, averagedDualWeight]) (hQ1_open := hQ1_open) (hQ1_convex := hQ1_convex) (hfhat_convex := hfhat_convex) (hfhat_diff := hfhat_diff) (hphihat_convex := hphihat_convex) (hμ := hμ) (hσ2 := hσ2) (hconv := hconv) (hd2_nonneg := hd2_nonneg) (hmax := hmax)

Weighted linearization bound using the canonical averaged dual point from equation (4.2), with .

lemma weighted_sum_bound_averagedDualPoint {E1 E2 : Type*} [NormedAddCommGroup E1] [NormedSpace ℝ E1] [FiniteDimensional ℝ E1] [NormedAddCommGroup E2] [NormedSpace ℝ E2] [FiniteDimensional ℝ E2] (Q1 : Set E1) (Q2 : Set E2) (A : E1 →L[ℝ] (E2 →L[ℝ] ℝ)) (fhat : E1 → ℝ) (phihat d2 : E2 → ℝ) (μ σ2 : ℝ) (xSeq : ℕ → Q1) (N : ℕ) (hQ2_convex : Convex ℝ Q2) (hQ2_closed : IsClosed Q2) (hQ2_bdd : Bornology.IsBounded Q2) (hQ2_nonempty : Q2.Nonempty) (hphihat : ContinuousOn phihat Q2) (hd2 : ContinuousOn d2 Q2) (hQ1_open : IsOpen Q1) (hQ1_convex : Convex ℝ Q1) (hfhat_convex : ConvexOn ℝ Q1 fhat) (hfhat_diff : DifferentiableOn ℝ fhat Q1) (hphihat_convex : ConvexOn ℝ Q2 phihat) (hμ : 0 < μ) (hσ2 : 0 < σ2) (hconv : StrongConvexOn Q2 σ2 d2) (hd2_nonneg : ∀ u ∈ Q2, 0 ≤ d2 u) : let hatu : Q2 := averagedDualPoint (Q2 := Q2) (A := A) (phihat := phihat) (d2 := d2) (μ := μ) (xSeq := fun i => (xSeq i : E1)) (N := N) (hQ2_convex := hQ2_convex) (hQ2_closed := hQ2_closed) (hQ2_bdd := hQ2_bdd) (hQ2_nonempty := hQ2_nonempty) (hphihat := hphihat) (hd2 := hd2) ∀ x ∈ Q1, Finset.sum (Finset.range (N + 1)) (fun i => ((i : ℝ) + 1) * (SmoothedObjective Q2 A phihat d2 μ fhat (xSeq i : E1) + DualPairing ((fderiv ℝ (SmoothedObjective Q2 A phihat d2 μ fhat) (xSeq i)).toLinearMap) (x - xSeq i))) ≤ ((N : ℝ) + 1) * ((N : ℝ) + 2) / 2 * (fhat x + A x hatu - phihat hatu) := by classical simp only exact weighted_sum_bound_averagedDualPoint_of_isSmoothedMaximizer (Q1 := Q1) (Q2 := Q2) (A := A) (fhat := fhat) (phihat := phihat) (d2 := d2) (μ := μ) (σ2 := σ2) (uμ := smoothedMaximizer Q2 A phihat d2 μ hQ2_closed hQ2_bdd hQ2_nonempty hphihat hd2) (xSeq := xSeq) (N := N) (hQ1_open := hQ1_open) (hQ1_convex := hQ1_convex) (hQ2_convex := hQ2_convex) (hfhat_convex := hfhat_convex) (hfhat_diff := hfhat_diff) (hphihat_convex := hphihat_convex) (hμ := hμ) (hσ2 := hσ2) (hconv := hconv) (hd2_nonneg := hd2_nonneg) (hmax := smoothedMaximizer_isSmoothedMaximizer (Q2 := Q2) (A := A) (phihat := phihat) (d2 := d2) (μ := μ) hQ2_closed hQ2_bdd hQ2_nonempty hphihat hd2)

Paper-facing canonical weighted linearization bound using the averaged dual point from equation (4.2).

lemma weighted_sum_bound {E1 E2 : Type*} [NormedAddCommGroup E1] [NormedSpace ℝ E1] [FiniteDimensional ℝ E1] [NormedAddCommGroup E2] [NormedSpace ℝ E2] [FiniteDimensional ℝ E2] (Q1 : Set E1) (Q2 : Set E2) (A : E1 →L[ℝ] (E2 →L[ℝ] ℝ)) (fhat : E1 → ℝ) (phihat d2 : E2 → ℝ) (μ σ2 : ℝ) (xSeq : ℕ → Q1) (N : ℕ) (hQ2_convex : Convex ℝ Q2) (hQ2_closed : IsClosed Q2) (hQ2_bdd : Bornology.IsBounded Q2) (hQ2_nonempty : Q2.Nonempty) (hphihat : ContinuousOn phihat Q2) (hd2 : ContinuousOn d2 Q2) (hQ1_open : IsOpen Q1) (hQ1_convex : Convex ℝ Q1) (hfhat_convex : ConvexOn ℝ Q1 fhat) (hfhat_diff : DifferentiableOn ℝ fhat Q1) (hphihat_convex : ConvexOn ℝ Q2 phihat) (hμ : 0 < μ) (hσ2 : 0 < σ2) (hconv : StrongConvexOn Q2 σ2 d2) (hd2_nonneg : ∀ u ∈ Q2, 0 ≤ d2 u) : let hatu : Q2 := averagedDualPoint (Q2 := Q2) (A := A) (phihat := phihat) (d2 := d2) (μ := μ) (xSeq := fun i => (xSeq i : E1)) (N := N) (hQ2_convex := hQ2_convex) (hQ2_closed := hQ2_closed) (hQ2_bdd := hQ2_bdd) (hQ2_nonempty := hQ2_nonempty) (hphihat := hphihat) (hd2 := hd2) ∀ x ∈ Q1, Finset.sum (Finset.range (N + 1)) (fun i => ((i : ℝ) + 1) * (SmoothedObjective Q2 A phihat d2 μ fhat (xSeq i : E1) + DualPairing ((fderiv ℝ (SmoothedObjective Q2 A phihat d2 μ fhat) (xSeq i)).toLinearMap) (x - xSeq i))) ≤ ((N : ℝ) + 1) * ((N : ℝ) + 2) / 2 * (fhat x + A x hatu - phihat hatu) := by exact weighted_sum_bound_averagedDualPoint (Q1 := Q1) (Q2 := Q2) (A := A) (fhat := fhat) (phihat := phihat) (d2 := d2) (μ := μ) (σ2 := σ2) (xSeq := xSeq) (N := N) (hQ2_convex := hQ2_convex) (hQ2_closed := hQ2_closed) (hQ2_bdd := hQ2_bdd) (hQ2_nonempty := hQ2_nonempty) (hphihat := hphihat) (hd2 := hd2) (hQ1_open := hQ1_open) (hQ1_convex := hQ1_convex) (hfhat_convex := hfhat_convex) (hfhat_diff := hfhat_diff) (hphihat_convex := hphihat_convex) (hμ := hμ) (hσ2 := hσ2) (hconv := hconv) (hd2_nonneg := hd2_nonneg)

If Unknown identifier `μ`μ is chosen as in the smoothing rule, its square satisfies the scaling identity.

lemma mu_sq_identity (D1 D2 σ1 σ2 μ Aop : ℝ) (N : ℕ) (hμ_def : μ = (2 * Aop / ((N : ℝ) + 1)) * Real.sqrt (D1 / (σ1 * σ2 * D2))) (hσ1 : 0 < σ1) (hσ2 : 0 < σ2) (hD1 : 0 ≤ D1) (hD2 : 0 ≤ D2) (hD2ne : D2 ≠ 0) : μ ^ 2 * (σ1 * σ2 * D2) * ((N : ℝ) + 1) ^ 2 = 4 * Aop ^ 2 * D1 := by have hdenom_nonneg : 0 ≤ σ1 * σ2 * D2 := by have hσ1_nonneg : 0 ≤ σ1 := le_of_lt hσ1 have hσ2_nonneg : 0 ≤ σ2 := le_of_lt hσ2 have hσ12_nonneg : 0 ≤ σ1 * σ2 := mul_nonneg hσ1_nonneg hσ2_nonneg exact mul_nonneg hσ12_nonneg hD2 have hnonneg : 0 ≤ D1 / (σ1 * σ2 * D2) := by exact div_nonneg hD1 hdenom_nonneg have hμ_sq : μ ^ 2 = (2 * Aop / ((N : ℝ) + 1)) ^ 2 * (D1 / (σ1 * σ2 * D2)) := by calc μ ^ 2 = ((2 * Aop / ((N : ℝ) + 1)) * Real.sqrt (D1 / (σ1 * σ2 * D2))) ^ 2 := by simp [hμ_def] _ = (2 * Aop / ((N : ℝ) + 1)) ^ 2 * (Real.sqrt (D1 / (σ1 * σ2 * D2))) ^ 2 := by ring _ = (2 * Aop / ((N : ℝ) + 1)) ^ 2 * (D1 / (σ1 * σ2 * D2)) := by simp [Real.sq_sqrt hnonneg] have hσ1ne : σ1 ≠ 0 := ne_of_gt hσ1 have hσ2ne : σ2 ≠ 0 := ne_of_gt hσ2 have hN1ne : ((N : ℝ) + 1) ≠ 0 := by nlinarith field_simp [hσ1ne, hσ2ne, hD2ne, hN1ne] at hμ_sq nlinarith [hμ_sq]

If Unknown identifier `μ`μ is chosen as in the smoothing rule, then Unknown identifier `μ`sorry * sorry : ?m.5μ * Unknown identifier `D2`D2 simplifies to the sqrt expression.

lemma mu_mul_D2_sqrt (D1 D2 σ1 σ2 μ Aop : ℝ) (N : ℕ) (hμ_def : μ = (2 * Aop / ((N : ℝ) + 1)) * Real.sqrt (D1 / (σ1 * σ2 * D2))) (hD2 : 0 ≤ D2) (hσ1 : 0 < σ1) (hσ2 : 0 < σ2) : μ * D2 = (2 * Aop / ((N : ℝ) + 1)) * Real.sqrt (D1 * D2 / (σ1 * σ2)) := by by_cases hD2zero : D2 = 0 · simp [hμ_def, hD2zero] · have hσ1ne : σ1 ≠ 0 := ne_of_gt hσ1 have hσ2ne : σ2 ≠ 0 := ne_of_gt hσ2 have hD2ne : D2 ≠ 0 := hD2zero have hsqrt : Real.sqrt (D2 * D2) = D2 := by simpa using (Real.sqrt_mul_self hD2) have hmul : D1 / (σ1 * σ2 * D2) * (D2 * D2) = D1 * D2 / (σ1 * σ2) := by field_simp [hD2ne, hσ1ne, hσ2ne] have hmul_sqrt : Real.sqrt (D1 / (σ1 * σ2 * D2)) * Real.sqrt (D2 * D2) = Real.sqrt (D1 / (σ1 * σ2 * D2) * (D2 * D2)) := by have hnonneg : 0 ≤ D2 * D2 := mul_nonneg hD2 hD2 have h := (Real.sqrt_mul' (x := D1 / (σ1 * σ2 * D2)) (hy := hnonneg)) simpa [mul_comm, mul_left_comm, mul_assoc] using h.symm have hcalc : Real.sqrt (D1 / (σ1 * σ2 * D2)) * D2 = Real.sqrt (D1 * D2 / (σ1 * σ2)) := by calc Real.sqrt (D1 / (σ1 * σ2 * D2)) * D2 = Real.sqrt (D1 / (σ1 * σ2 * D2)) * Real.sqrt (D2 * D2) := by simp [hsqrt] _ = Real.sqrt (D1 / (σ1 * σ2 * D2) * (D2 * D2)) := by simpa using hmul_sqrt _ = Real.sqrt (D1 * D2 / (σ1 * σ2)) := by simp [hmul] calc μ * D2 = (2 * Aop / ((N : ℝ) + 1)) * (Real.sqrt (D1 / (σ1 * σ2 * D2)) * D2) := by simp [hμ_def, mul_left_comm, mul_comm] _ = (2 * Aop / ((N : ℝ) + 1)) * Real.sqrt (D1 * D2 / (σ1 * σ2)) := by simp [hcalc]

The inverse-Unknown identifier `μ`μ term equals Unknown identifier `μ`sorry * sorry : ?m.5μ * Unknown identifier `D2`D2 scaled by (sorry + 1) / (sorry + 2) : ℕ(Unknown identifier `N`N+1)/(Unknown identifier `N`N+2).

lemma mu_inv_term_eq (D1 D2 σ1 σ2 μ Aop : ℝ) (N : ℕ) (hμ_def : μ = (2 * Aop / ((N : ℝ) + 1)) * Real.sqrt (D1 / (σ1 * σ2 * D2))) (hσ1 : 0 < σ1) (hσ2 : 0 < σ2) (hD1 : 0 ≤ D1) (hD2 : 0 ≤ D2) (hμ : μ ≠ 0) : (4 * (1 / (μ * σ2)) * Aop ^ 2 * D1) / (σ1 * ((N : ℝ) + 1) * ((N : ℝ) + 2)) = μ * D2 * ((N : ℝ) + 1) / ((N : ℝ) + 2) := by have hD2ne : D2 ≠ 0 := by intro hD2zero apply hμ simp [hμ_def, hD2zero] have hμ_sq' := mu_sq_identity (D1 := D1) (D2 := D2) (σ1 := σ1) (σ2 := σ2) (μ := μ) (Aop := Aop) (N := N) hμ_def hσ1 hσ2 hD1 hD2 hD2ne have hσ1ne : σ1 ≠ 0 := ne_of_gt hσ1 have hσ2ne : σ2 ≠ 0 := ne_of_gt hσ2 have hN1ne : ((N : ℝ) + 1) ≠ 0 := by nlinarith have hN2ne : ((N : ℝ) + 2) ≠ 0 := by nlinarith field_simp [hμ, hσ1ne, hσ2ne, hN1ne, hN2ne] simpa [mul_comm, mul_left_comm, mul_assoc] using hμ_sq'.symm

The inverse-Unknown identifier `μ`μ term is bounded by the sqrt expression.

lemma mu_inv_term_le (D1 D2 σ1 σ2 μ Aop : ℝ) (N : ℕ) (hμ_def : μ = (2 * Aop / ((N : ℝ) + 1)) * Real.sqrt (D1 / (σ1 * σ2 * D2))) (hσ1 : 0 < σ1) (hσ2 : 0 < σ2) (hD1 : 0 ≤ D1) (hD2 : 0 ≤ D2) (hAop : 0 ≤ Aop) : (4 * (1 / (μ * σ2)) * Aop ^ 2 * D1) / (σ1 * ((N : ℝ) + 1) * ((N : ℝ) + 2)) ≤ (2 * Aop / ((N : ℝ) + 1)) * Real.sqrt (D1 * D2 / (σ1 * σ2)) := by by_cases hμ : μ = 0 · have hNpos : 0 < (N : ℝ) + 1 := by nlinarith have hfrac_nonneg : 0 ≤ (2 * Aop) / ((N : ℝ) + 1) := by exact div_nonneg (by nlinarith [hAop]) (le_of_lt hNpos) have hsqrt_nonneg : 0 ≤ Real.sqrt (D1 * D2 / (σ1 * σ2)) := by exact Real.sqrt_nonneg _ have hRHS_nonneg : 0 ≤ (2 * Aop / ((N : ℝ) + 1)) * Real.sqrt (D1 * D2 / (σ1 * σ2)) := by exact mul_nonneg hfrac_nonneg hsqrt_nonneg simpa [hμ] using hRHS_nonneg · have hμterm_eq := mu_inv_term_eq (D1 := D1) (D2 := D2) (σ1 := σ1) (σ2 := σ2) (μ := μ) (Aop := Aop) (N := N) hμ_def hσ1 hσ2 hD1 hD2 hμ have hratio_le : ((N : ℝ) + 1) / ((N : ℝ) + 2) ≤ (1 : ℝ) := by have hN2pos : 0 < (N : ℝ) + 2 := by nlinarith exact (div_le_one hN2pos).2 (by nlinarith) have hμ_nonneg : 0 ≤ μ := by have hNpos : 0 < (N : ℝ) + 1 := by nlinarith have hsqrt_nonneg : 0 ≤ Real.sqrt (D1 / (σ1 * σ2 * D2)) := by exact Real.sqrt_nonneg _ have hfrac_nonneg : 0 ≤ (2 * Aop) / ((N : ℝ) + 1) := by exact div_nonneg (by nlinarith [hAop]) (le_of_lt hNpos) simpa [hμ_def] using mul_nonneg hfrac_nonneg hsqrt_nonneg have hμD2_nonneg : 0 ≤ μ * D2 := by exact mul_nonneg hμ_nonneg hD2 have hscale_le : μ * D2 * (((N : ℝ) + 1) / ((N : ℝ) + 2)) ≤ μ * D2 := by have hle := mul_le_mul_of_nonneg_left hratio_le hμD2_nonneg simpa [mul_assoc] using hle have hμD2 := mu_mul_D2_sqrt (D1 := D1) (D2 := D2) (σ1 := σ1) (σ2 := σ2) (μ := μ) (Aop := Aop) (N := N) hμ_def hD2 hσ1 hσ2 calc (4 * (1 / (μ * σ2)) * Aop ^ 2 * D1) / (σ1 * ((N : ℝ) + 1) * ((N : ℝ) + 2)) = μ * D2 * (((N : ℝ) + 1) / ((N : ℝ) + 2)) := by simpa [div_eq_mul_inv, mul_assoc] using hμterm_eq _ ≤ μ * D2 := hscale_le _ = (2 * Aop / ((N : ℝ) + 1)) * Real.sqrt (D1 * D2 / (σ1 * σ2)) := by simpa using hμD2

Simplify the Unknown identifier `μ`μ-dependent terms in the gap bound.

lemma mu_simplify_bound (D1 D2 σ1 σ2 μ : ℝ) (N : ℕ) (Aop : ℝ) (hμ_def : μ = (2 * Aop / ((N : ℝ) + 1)) * Real.sqrt (D1 / (σ1 * σ2 * D2))) (hD1 : 0 ≤ D1) (hD2 : 0 ≤ D2) (hσ1 : 0 < σ1) (hσ2 : 0 < σ2) (hAop : 0 ≤ Aop) : μ * D2 + (4 * (1 / (μ * σ2)) * Aop ^ 2 * D1) / (σ1 * ((N : ℝ) + 1) * ((N : ℝ) + 2)) ≤ (4 * Aop / ((N : ℝ) + 1)) * Real.sqrt (D1 * D2 / (σ1 * σ2)) := by have hμD2 := mu_mul_D2_sqrt (D1 := D1) (D2 := D2) (σ1 := σ1) (σ2 := σ2) (μ := μ) (Aop := Aop) (N := N) hμ_def hD2 hσ1 hσ2 have hμinv := mu_inv_term_le (D1 := D1) (D2 := D2) (σ1 := σ1) (σ2 := σ2) (μ := μ) (Aop := Aop) (N := N) hμ_def hσ1 hσ2 hD1 hD2 hAop have hsum : μ * D2 + (4 * (1 / (μ * σ2)) * Aop ^ 2 * D1) / (σ1 * ((N : ℝ) + 1) * ((N : ℝ) + 2)) ≤ (2 * Aop / ((N : ℝ) + 1)) * Real.sqrt (D1 * D2 / (σ1 * σ2)) + (2 * Aop / ((N : ℝ) + 1)) * Real.sqrt (D1 * D2 / (σ1 * σ2)) := by linarith [hμD2, hμinv] calc μ * D2 + (4 * (1 / (μ * σ2)) * Aop ^ 2 * D1) / (σ1 * ((N : ℝ) + 1) * ((N : ℝ) + 2)) ≤ (2 * Aop / ((N : ℝ) + 1)) * Real.sqrt (D1 * D2 / (σ1 * σ2)) + (2 * Aop / ((N : ℝ) + 1)) * Real.sqrt (D1 * D2 / (σ1 * σ2)) := hsum _ = (4 * Aop / ((N : ℝ) + 1)) * Real.sqrt (D1 * D2 / (σ1 * σ2)) := by ring

Convert an iteration lower bound to an ε-accuracy bound.

lemma epsilon_bound_from_gap {a b ε : ℝ} {N : ℕ} (hε : 0 < ε) (ha : 0 ≤ a) (hb : 0 ≤ b) (hN : (N : ℝ) + 1 ≥ a / ε + Real.sqrt (b / ε)) : a / ((N : ℝ) + 1) + b / ((N : ℝ) + 1) ^ (2 : ℕ) ≤ ε := by set t : ℝ := (N : ℝ) + 1 with ht_def have htpos : 0 < t := by have htpos' : 0 < (N : ℝ) + 1 := by exact_mod_cast (Nat.succ_pos N) simpa [ht_def] using htpos' have htne : t ≠ 0 := ne_of_gt htpos set s : ℝ := t - a / ε with hs_def have hs : Real.sqrt (b / ε) ≤ s := by have hN' : a / ε + Real.sqrt (b / ε) ≤ t := by simpa [ht_def] using hN linarith [hN'] have hs_nonneg : 0 ≤ s := le_trans (Real.sqrt_nonneg _) hs have hbε_nonneg : 0 ≤ b / ε := div_nonneg hb (le_of_lt hε) have hb_le : b ≤ ε * s ^ (2 : ℕ) := by have hsq : (Real.sqrt (b / ε)) ^ (2 : ℕ) ≤ s ^ (2 : ℕ) := by have hsqrt_nonneg : 0 ≤ Real.sqrt (b / ε) := Real.sqrt_nonneg _ have hmul := mul_le_mul hs hs hsqrt_nonneg hs_nonneg simpa [pow_two] using hmul have hsq' : b / ε ≤ s ^ (2 : ℕ) := by simpa [Real.sq_sqrt hbε_nonneg] using hsq have hmul := mul_le_mul_of_nonneg_left hsq' (le_of_lt hε) simpa [div_eq_mul_inv, hε.ne', mul_assoc, mul_left_comm, mul_comm] using hmul have hb_le' : b ≤ a * s + ε * s ^ (2 : ℕ) := by have has_nonneg : 0 ≤ a * s := mul_nonneg ha hs_nonneg linarith [hb_le, has_nonneg] have ht_as : t = a / ε + s := by simp [hs_def] have hineq : a * t + b ≤ ε * t ^ (2 : ℕ) := by have hεne : ε ≠ 0 := ne_of_gt hε calc a * t + b ≤ a * t + (a * s + ε * s ^ (2 : ℕ)) := by have h := add_le_add_left hb_le' (a * t) simpa [add_assoc, add_left_comm, add_comm] using h _ = a * (a / ε + s) + (a * s + ε * s ^ (2 : ℕ)) := by simp [ht_as] _ = ε * (a / ε + s) ^ (2 : ℕ) := by -- clear the single denominator `ε` and expand field_simp [hεne, pow_two] _ = ε * t ^ (2 : ℕ) := by simp [ht_as] have ht2pos : 0 < t ^ (2 : ℕ) := by simpa using (pow_pos htpos 2) have hcalc : a / t + b / t ^ (2 : ℕ) = (a * t + b) / t ^ (2 : ℕ) := by field_simp [htne, pow_two] have hineq' : (a * t + b) / t ^ (2 : ℕ) ≤ ε := by exact (div_le_iff₀ ht2pos).2 hineq have hfinal : a / t + b / t ^ (2 : ℕ) ≤ ε := by calc a / t + b / t ^ (2 : ℕ) = (a * t + b) / t ^ (2 : ℕ) := hcalc _ ≤ ε := hineq' -- rewrite in terms of `t = (N:ℝ) + 1` simpa [ht_def] using hfinal