Smooth Minimization of Non-Smooth Functions (Nesterov, 2004) -- Section 04 -- Part 3
Lean contributors (project-level attribution): Wanli Ma, Zichen Wang.
open scoped NNRealset_option maxHeartbeats 350000 in
/-- Theorem 1.4.1.
Assume the structural model (2.2) and that `fhat` is differentiable with M-Lipschitz gradient on
`Q1`. Let `d1` be a prox-function of `Q1` with parameter `σ1 > 0` and prox-diameter `D1` as in
(4.3_D1). Let `d2` be a prox-function of `Q2` with strong convexity parameter `σ2 > 0` and define
`D2 := max_{u ∈ Q2} d2 u` as in Proposition 2.7. Apply Algorithm 3.11 to the smoothed problem
(4.1) with `μ = μ(N) = (2‖A‖_{1,2}/(N+1)) * sqrt(D1/(σ1 σ2 D2))` (equation (thm3_muN)). After `N`
iterations define `\hat x := y_N` and
`\hat u := ∑_{i=0}^N 2(i+1)/((N+1)(N+2)) u_μ(x_i)` (4.2). Then `0 ≤ f(\hat x) - φ(\hat u)` and the
duality-gap bound (4.3) holds, and consequently the ε-solution bound (4.4) holds, for a chosen
maximizing branch. This is the general-branch helper form. -/
private theorem algorithm311_duality_gap_bound_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 : E2 → ℝ)
(d1 : E1 → ℝ) (d2 : E2 → ℝ) (σ1 σ2 M D1 : ℝ) (xSeq ySeq : ℕ → Q1) (uμ : E1 → E2)
(N : ℕ) (hatu : Q2) :
let A' : E1 →ₗ[ℝ] Module.Dual ℝ E2 :=
{ toFun := fun x => (A x).toLinearMap
map_add' := by
intro x y
ext u
simp
map_smul' := by
intro c x
ext u
simp }
let D2 : ℝ := sSup (d2 '' Q2)
let μ : ℝ :=
(2 * OperatorNormDef A' / ((N : ℝ) + 1)) *
Real.sqrt (D1 / (σ1 * σ2 * D2))
let fbar : E1 → ℝ := SmoothedObjective Q2 A phihat d2 μ fhat
let f : E1 → ℝ := fun x => fhat x + sSup ((fun u => A x u - phihat u) '' Q2)
let φ : Q2 → ℝ := AdjointFormPotential Q1 Q2 A fhat phihat
LipschitzOnWith (Real.toNNReal M) (fun x => fderiv ℝ fhat x) Q1 →
0 < σ1 →
0 < σ2 →
StrongConvexOn Q1 σ1 d1 →
StrongConvexOn Q2 σ2 d2 →
IsProxDiameterBound Q1 d1 D1 →
OptimalSchemeAlgorithm Q1 fbar d1
(M + (1 / (μ * σ2)) * (OperatorNormDef A') ^ 2) σ1 xSeq ySeq →
(∀ x, IsSmoothedMaximizer Q2 A phihat d2 μ x (uμ x)) →
(hatu : E2) =
Finset.sum (Finset.range (N + 1)) (fun i =>
(2 * ((i : ℝ) + 1) / (((N : ℝ) + 1) * ((N : ℝ) + 2))) •
uμ (xSeq i : E1)) →
ConvexOn ℝ Q1 fhat →
DifferentiableOn ℝ fhat Q1 →
ConvexOn ℝ Q2 phihat →
0 < μ →
0 ≤ M →
0 ≤ D1 →
0 < M + (1 / (μ * σ2)) * (OperatorNormDef A') ^ 2 →
IsClosed Q1 →
IsOpen Q1 →
(∀ u ∈ Q2, 0 ≤ d2 u) →
(∀ x, BddAbove ((fun u => A x u - phihat u) '' Q2)) →
BddAbove (d2 '' Q2) →
Q2.Nonempty →
(∀ u, BddBelow ((fun x => A x u + fhat x) '' Q1)) →
0 ≤ f (ySeq N : E1) - φ hatu ∧
f (ySeq N : E1) - φ hatu ≤
(4 * OperatorNormDef A' / ((N : ℝ) + 1)) * Real.sqrt (D1 * D2 / (σ1 * σ2)) +
(4 * M * D1) / (σ1 * ((N : ℝ) + 1) ^ (2 : ℕ)) ∧
∀ ε > 0,
(N : ℝ) ≥
(4 * OperatorNormDef A' / ε) * Real.sqrt (D1 * D2 / (σ1 * σ2)) +
2 * Real.sqrt (M * D1 / (σ1 * ε)) →
f (ySeq N : E1) - φ hatu ≤ ε := by
classical
dsimp
intro hLipschitz hσ1 hσ2 hconv1 hconv2 hD1 hAlg hmax hhatudef
hfhat_convex hfhat_diff hphihat_convex hμ_pos hM_nonneg hD1_nonneg hL_pos
hQ1_closed hQ1_open hd2_nonneg hbd0 hbd_d2 hQ2_nonempty hbdBelow
set A' : E1 →ₗ[ℝ] Module.Dual ℝ E2 :=
{ toFun := fun x => (A x).toLinearMap
map_add' := by
intro x y
ext u
simp
map_smul' := by
intro c x
ext u
simp } with hA'
set μ : ℝ :=
(2 * OperatorNormDef A' / ((N : ℝ) + 1)) *
Real.sqrt (D1 / (σ1 * σ2 * sSup (d2 '' Q2))) with hμ_def
set f : E1 → ℝ := fun x => fhat x + sSup ((fun u => A x u - phihat u) '' Q2) with hf
set φ : Q2 → ℝ := AdjointFormPotential Q1 Q2 A fhat phihat with hφ
have hμ_nonneg' : 0 ≤ μ := by
exact le_of_lt hμ_pos
have hD2_nonneg : 0 ≤ sSup (d2 '' Q2) := by
refine sSup_image_nonneg (s := Q2) (f := d2) (hbd := hbd_d2) (hne := hQ2_nonempty)
?_
intro u hu
exact hd2_nonneg u hu
have hgap_nonneg :
0 ≤
(fhat (ySeq N : E1) + sSup ((fun u => A (ySeq N : E1) u - phihat u) '' Q2)) -
AdjointFormPotential Q1 Q2 A fhat phihat hatu := by
have hdual :=
adjointForm_duality_gap_nonneg (Q1 := Q1) (Q2 := Q2) (A := A) (fhat := fhat)
(phihat := phihat) (hbd0 := hbd0) (hbdBelow := hbdBelow)
have hy : (ySeq N : E1) ∈ Q1 := (ySeq N).property
exact hdual (x := (ySeq N : E1)) hy (u := hatu)
have hsmoothed :
fhat (ySeq N : E1) + sSup ((fun u => A (ySeq N : E1) u - phihat u) '' Q2) ≤
SmoothedObjective Q2 A phihat d2 μ fhat (ySeq N : E1) + μ * sSup (d2 '' Q2) := by
have hbound :=
smoothedObjective_bound (Q2 := Q2) (A := A) (phihat := phihat) (d2 := d2) (μ := μ)
(fhat := fhat)
simpa using (hbound (x := (ySeq N : E1)) hμ_nonneg' hd2_nonneg hbd0 hbd_d2)
have hgap_smoothed :
(fhat (ySeq N : E1) + sSup ((fun u => A (ySeq N : E1) u - phihat u) '' Q2)) -
AdjointFormPotential Q1 Q2 A fhat phihat hatu ≤
μ * sSup (d2 '' Q2) +
(SmoothedObjective Q2 A phihat d2 μ fhat (ySeq N : E1) -
AdjointFormPotential Q1 Q2 A fhat phihat hatu) := by
have h' :=
sub_le_sub_right hsmoothed (AdjointFormPotential Q1 Q2 A fhat phihat hatu)
-- regroup the right-hand side as `μ * D2 + (fbar - φ)`
have h'' :
(SmoothedObjective Q2 A phihat d2 μ fhat (ySeq N : E1) + μ * sSup (d2 '' Q2)) -
AdjointFormPotential Q1 Q2 A fhat phihat hatu =
μ * sSup (d2 '' Q2) +
(SmoothedObjective Q2 A phihat d2 μ fhat (ySeq N : E1) -
AdjointFormPotential Q1 Q2 A fhat phihat hatu) := by
ring
exact le_trans h' (le_of_eq h'')
refine And.intro hgap_nonneg ?_
have hgap_fbar :
SmoothedObjective Q2 A phihat d2 μ fhat (ySeq N : E1) -
AdjointFormPotential Q1 Q2 A fhat phihat hatu ≤
(4 * (M + (1 / (μ * σ2)) * (OperatorNormDef A') ^ 2) * D1) /
(σ1 * ((N : ℝ) + 1) * ((N : ℝ) + 2)) := by
have hQ1_convex : Convex ℝ Q1 := convex_of_strongConvexOn hconv1
set L : ℝ := M + (1 / (μ * σ2)) * (OperatorNormDef A') ^ 2
set denom : ℝ := ((N : ℝ) + 1) * ((N : ℝ) + 2)
have hdenom_expr : ((N : ℝ) + 1) * ((N : ℝ) + 2) = denom := by
simp [denom]
have hdenom_div2 : ((N : ℝ) + 1) * ((N : ℝ) + 2) / 2 = denom / 2 := by
simpa using congrArg (fun z : ℝ => z / 2) hdenom_expr
have hL_pos' : 0 < L := by
simpa [L] using hL_pos
have hdenom_pos : 0 < denom := by
have h1 : 0 < (N : ℝ) + 1 := by
exact_mod_cast (Nat.succ_pos N)
have h2 : 0 < (N : ℝ) + 2 := by
exact_mod_cast (Nat.succ_pos (N + 1))
simpa [denom] using mul_pos h1 h2
have hcoef : (2 / denom) * (denom / 2) = (1 : ℝ) := by
field_simp [denom, hdenom_pos.ne']
have hbound_all :
∀ x ∈ Q1,
SmoothedObjective Q2 A phihat d2 μ fhat (ySeq N : E1) + phihat hatu -
(4 * L * D1) / (σ1 * denom) ≤ A x hatu + fhat x := by
intro x hx
have hrate :=
fbar_rate_bound (xSeq := xSeq) (ySeq := ySeq) (N := N) (Q := Q1)
(f := SmoothedObjective Q2 A phihat d2 μ fhat) (d := d1) (L := L) (σ := σ1) (D := D1)
(hL := hL_pos') (hσ := hσ1) (hAlg := hAlg) (hD := hD1) hx
have hsum_bound :=
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 := hatu) hhatudef (hQ1_open := hQ1_open) (hQ1_convex := hQ1_convex)
(hfhat_convex := hfhat_convex) (hfhat_diff := hfhat_diff)
(hphihat_convex := hphihat_convex) (hμ := hμ_pos) (hσ2 := hσ2)
(hconv := hconv2) (hd2_nonneg := hd2_nonneg) (hmax := hmax) x hx
have hcoef_nonneg : 0 ≤ 2 / denom := by
exact div_nonneg (by norm_num) (le_of_lt hdenom_pos)
have hsum_mul :=
mul_le_mul_of_nonneg_left hsum_bound hcoef_nonneg
have hrate_comm :
SmoothedObjective Q2 A phihat d2 μ fhat (ySeq N : E1) ≤
(4 * L * D1) / (σ1 * denom) +
(2 / denom) *
∑ i ∈ Finset.range (N + 1),
(↑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)) := by
simpa [hdenom_expr] using hrate
have hrate_sum :
(4 * L * D1) / (σ1 * denom) +
(2 / denom) *
∑ i ∈ Finset.range (N + 1),
(↑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)) ≤
(4 * L * D1) / (σ1 * denom) +
(2 / denom) *
(((N : ℝ) + 1) * ((N : ℝ) + 2) / 2 * (fhat x + A x hatu - phihat hatu)) := by
exact add_le_add_right hsum_mul ((4 * L * D1) / (σ1 * denom))
have hrate_tmp := le_trans hrate_comm hrate_sum
have hrate' :
SmoothedObjective Q2 A phihat d2 μ fhat (ySeq N : E1) ≤
(4 * L * D1) / (σ1 * denom) +
(2 / denom) * ((denom / 2) * (fhat x + A x hatu - phihat hatu)) := by
have hrhs :
(4 * L * D1) / (σ1 * denom) +
(2 / denom) *
(((N : ℝ) + 1) * ((N : ℝ) + 2) / 2 * (fhat x + A x hatu - phihat hatu)) =
(4 * L * D1) / (σ1 * denom) +
(2 / denom) * ((denom / 2) * (fhat x + A x hatu - phihat hatu)) := by
rw [hdenom_div2]
exact le_trans hrate_tmp (le_of_eq hrhs)
have hrate'' :
SmoothedObjective Q2 A phihat d2 μ fhat (ySeq N : E1) ≤
(4 * L * D1) / (σ1 * denom) + (fhat x + A x hatu - phihat hatu) := by
have hrhs :
(4 * L * D1) / (σ1 * denom) +
(2 / denom) * ((denom / 2) * (fhat x + A x hatu - phihat hatu)) =
(4 * L * D1) / (σ1 * denom) + (fhat x + A x hatu - phihat hatu) := by
-- reassociate then cancel the coefficient using `hcoef`
have hcancel :
(2 / denom) * ((denom / 2) * (fhat x + A x hatu - phihat hatu)) =
(fhat x + A x hatu - phihat hatu) := by
calc
(2 / denom) * ((denom / 2) * (fhat x + A x hatu - phihat hatu)) =
((2 / denom) * (denom / 2)) * (fhat x + A x hatu - phihat hatu) := by
simpa [mul_assoc] using
(mul_assoc (2 / denom) (denom / 2) (fhat x + A x hatu - phihat hatu)).symm
_ = (1 : ℝ) * (fhat x + A x hatu - phihat hatu) := by
rw [hcoef]
_ = fhat x + A x hatu - phihat hatu := by
simp
simp [hcancel]
exact le_trans hrate' (le_of_eq hrhs)
refine (sub_le_iff_le_add).2 ?_
have hrate_add := add_le_add hrate'' (le_rfl : phihat hatu ≤ phihat hatu)
-- `(+ phihat hatu)` cancels the `(- phihat hatu)` on the right.
have hrate_add' :
SmoothedObjective Q2 A phihat d2 μ fhat (ySeq N : E1) + phihat hatu ≤
(4 * L * D1) / (σ1 * denom) + (fhat x + A x hatu) := by
have hrhs :
((4 * L * D1) / (σ1 * denom) + (fhat x + A x hatu - phihat hatu)) + phihat hatu =
(4 * L * D1) / (σ1 * denom) + (fhat x + A x hatu) := by
ring
exact le_trans hrate_add (le_of_eq hrhs)
have hrhs :
(4 * L * D1) / (σ1 * denom) + (fhat x + A x hatu) =
A x hatu + fhat x + (4 * L * D1) / (σ1 * denom) := by
ring
exact le_trans hrate_add' (le_of_eq hrhs)
have hbound_inf :
SmoothedObjective Q2 A phihat d2 μ fhat (ySeq N : E1) + phihat hatu -
(4 * L * D1) / (σ1 * denom) ≤
sInf ((fun x => A x hatu + fhat x) '' Q1) := by
have hnonempty : ((fun x => A x hatu + fhat x) '' Q1).Nonempty := by
refine ⟨A (xSeq 0 : E1) hatu + fhat (xSeq 0 : E1), ?_⟩
exact ⟨xSeq 0, (xSeq 0).property, rfl⟩
refine le_csInf hnonempty ?_
intro y hy
rcases hy with ⟨x, hx, rfl⟩
exact hbound_all x hx
have hgap :
SmoothedObjective Q2 A phihat d2 μ fhat (ySeq N : E1) -
AdjointFormPotential Q1 Q2 A fhat phihat hatu ≤
(4 * L * D1) / (σ1 * denom) := by
have hφ :
AdjointFormPotential Q1 Q2 A fhat phihat hatu =
-phihat hatu + sInf ((fun x => A x hatu + fhat x) '' Q1) := by
rfl
have hle :
SmoothedObjective Q2 A phihat d2 μ fhat (ySeq N : E1) + phihat hatu ≤
sInf ((fun x => A x hatu + fhat x) '' Q1) + (4 * L * D1) / (σ1 * denom) := by
exact (sub_le_iff_le_add).1 hbound_inf
have hsub :
SmoothedObjective Q2 A phihat d2 μ fhat (ySeq N : E1) + phihat hatu -
sInf ((fun x => A x hatu + fhat x) '' Q1) ≤
(4 * L * D1) / (σ1 * denom) := by
have := sub_le_sub_right hle (sInf ((fun x => A x hatu + fhat x) '' Q1))
-- simplify the right-hand side `(sInf + C) - sInf`
have hrhs :
(sInf ((fun x => A x hatu + fhat x) '' Q1) + (4 * L * D1) / (σ1 * denom)) -
sInf ((fun x => A x hatu + fhat x) '' Q1) =
(4 * L * D1) / (σ1 * denom) := by
ring
simpa [hrhs] using this
-- rewrite `fbar - φ` as `fbar + phihat - sInf`
have hrewrite :
SmoothedObjective Q2 A phihat d2 μ fhat (ySeq N : E1) -
AdjointFormPotential Q1 Q2 A fhat phihat hatu =
SmoothedObjective Q2 A phihat d2 μ fhat (ySeq N : E1) + phihat hatu -
sInf ((fun x => A x hatu + fhat x) '' Q1) := by
rw [hφ]
ring
simpa [hrewrite] using hsub
simpa [L, denom, mul_assoc] using hgap
have hgap_bound :
f (ySeq N : E1) - φ hatu ≤
μ * sSup (d2 '' Q2) +
(4 * (M + (1 / (μ * σ2)) * (OperatorNormDef A') ^ 2) * D1) /
(σ1 * ((N : ℝ) + 1) * ((N : ℝ) + 2)) := by
have h2' :
μ * sSup (d2 '' Q2) +
(SmoothedObjective Q2 A phihat d2 μ fhat (ySeq N : E1) -
AdjointFormPotential Q1 Q2 A fhat phihat hatu) ≤
μ * sSup (d2 '' Q2) +
(4 * (M + (1 / (μ * σ2)) * (OperatorNormDef A') ^ 2) * D1) /
(σ1 * ((N : ℝ) + 1) * ((N : ℝ) + 2)) := by
exact
add_le_add (le_rfl : μ * sSup (d2 '' Q2) ≤ μ * sSup (d2 '' Q2)) hgap_fbar
have h' := le_trans hgap_smoothed h2'
simpa [hf, hφ] using h'
have hgap_bound' :
f (ySeq N : E1) - φ hatu ≤
(4 * OperatorNormDef A' / ((N : ℝ) + 1)) *
Real.sqrt (D1 * sSup (d2 '' Q2) / (σ1 * σ2)) +
(4 * M * D1) / (σ1 * ((N : ℝ) + 1) ^ (2 : ℕ)) := by
set D2 : ℝ := sSup (d2 '' Q2)
set denom : ℝ := ((N : ℝ) + 1) * ((N : ℝ) + 2)
set K : ℝ := (1 / (μ * σ2)) * (OperatorNormDef A') ^ 2
have hdenom_pos : 0 < denom := by
have h1 : 0 < (N : ℝ) + 1 := by
exact_mod_cast (Nat.succ_pos N)
have h2 : 0 < (N : ℝ) + 2 := by
exact_mod_cast (Nat.succ_pos (N + 1))
simpa [denom] using mul_pos h1 h2
have hμterm :
μ * D2 +
(4 * K * D1) / (σ1 * denom) ≤
(4 * OperatorNormDef A' / ((N : ℝ) + 1)) *
Real.sqrt (D1 * D2 / (σ1 * σ2)) := by
have hAop_nonneg : 0 ≤ OperatorNormDef A' := operatorNormDef_nonneg (A := A')
have hμ_def' :
μ = (2 * OperatorNormDef A' / ((N : ℝ) + 1)) *
Real.sqrt (D1 / (σ1 * σ2 * D2)) := by
simpa [D2] using hμ_def
have hμterm' :=
mu_simplify_bound (D1 := D1) (D2 := D2) (σ1 := σ1) (σ2 := σ2) (μ := μ) (N := N)
(Aop := OperatorNormDef A') hμ_def' hD1_nonneg hD2_nonneg hσ1 hσ2 hAop_nonneg
simpa [K, denom, mul_assoc] using hμterm'
have hgap_bound'' :
f (ySeq N : E1) - φ hatu ≤
μ * D2 +
(4 * M * D1) / (σ1 * denom) +
(4 * K * D1) / (σ1 * denom) := by
have hgap := hgap_bound
have hgap' :
f (ySeq N : E1) - φ hatu ≤
μ * D2 +
(4 * (M + K) * D1) /
(σ1 * denom) := by
simpa [D2, denom, K, mul_assoc] using hgap
have hsplit :
μ * D2 +
(4 * (M + K) * D1) /
(σ1 * denom) =
μ * D2 +
(4 * M * D1) / (σ1 * denom) +
(4 * K * D1) / (σ1 * denom) := by
ring_nf
have hgap'' :
f (ySeq N : E1) - φ hatu ≤
μ * D2 +
(4 * M * D1) / (σ1 * denom) +
(4 * K * D1) / (σ1 * denom) := by
simpa [hsplit] using hgap'
exact hgap''
have hMterm :
(4 * M * D1) / (σ1 * denom) ≤
(4 * M * D1) / (σ1 * ((N : ℝ) + 1) ^ (2 : ℕ)) := by
have hnum_nonneg : 0 ≤ 4 * M * D1 := by nlinarith [hM_nonneg, hD1_nonneg]
have hdenom_le :
σ1 * ((N : ℝ) + 1) ^ (2 : ℕ) ≤ σ1 * denom := by
have h' : ((N : ℝ) + 1) ^ (2 : ℕ) ≤ denom := by
have hpos : 0 ≤ (N : ℝ) + 1 := by
exact_mod_cast (Nat.zero_le (N + 1))
have hle : (N : ℝ) + 1 ≤ (N : ℝ) + 2 := by
exact_mod_cast (Nat.le_succ (N + 1))
have hmul :
((N : ℝ) + 1) * ((N : ℝ) + 1) ≤ ((N : ℝ) + 1) * ((N : ℝ) + 2) := by
exact mul_le_mul_of_nonneg_left hle hpos
simpa [pow_two, denom] using hmul
have hσ1_nonneg : 0 ≤ σ1 := le_of_lt hσ1
exact mul_le_mul_of_nonneg_left h' hσ1_nonneg
have hdenom_pos : 0 < σ1 * ((N : ℝ) + 1) ^ (2 : ℕ) := by
have hNpos : 0 < (N : ℝ) + 1 := by
exact_mod_cast (Nat.succ_pos N)
have hpow_pos : 0 < ((N : ℝ) + 1) ^ (2 : ℕ) := by
exact pow_pos hNpos 2
exact mul_pos hσ1 hpow_pos
exact (div_le_div_of_nonneg_left hnum_nonneg hdenom_pos hdenom_le)
have hgap_bound''' :
f (ySeq N : E1) - φ hatu ≤
(4 * OperatorNormDef A' / ((N : ℝ) + 1)) *
Real.sqrt (D1 * D2 / (σ1 * σ2)) +
(4 * M * D1) / (σ1 * denom) := by
set A : ℝ := (4 * M * D1) / (σ1 * denom)
set B : ℝ := (4 * K * D1) / (σ1 * denom)
have hgap_bound''_ab :
f (ySeq N : E1) - φ hatu ≤ μ * D2 + B + A := by
have hgap' : f (ySeq N : E1) - φ hatu ≤ μ * D2 + A + B := by
dsimp [A, B]
exact hgap_bound''
have hrhs : μ * D2 + A + B = μ * D2 + B + A := by
abel
exact le_trans hgap' (le_of_eq hrhs)
have hμterm' : μ * D2 + B + A ≤
(4 * OperatorNormDef A' / ((N : ℝ) + 1)) *
Real.sqrt (D1 * D2 / (σ1 * σ2)) + A := by
have hμtermB :
μ * D2 + B ≤
(4 * OperatorNormDef A' / ((N : ℝ) + 1)) *
Real.sqrt (D1 * D2 / (σ1 * σ2)) := by
dsimp [B]
exact hμterm
exact add_le_add_left hμtermB A
exact le_trans hgap_bound''_ab hμterm'
have hgap_bound'''' :
f (ySeq N : E1) - φ hatu ≤
(4 * OperatorNormDef A' / ((N : ℝ) + 1)) *
Real.sqrt (D1 * D2 / (σ1 * σ2)) +
(4 * M * D1) / (σ1 * ((N : ℝ) + 1) ^ (2 : ℕ)) := by
set T : ℝ :=
(4 * OperatorNormDef A' / ((N : ℝ) + 1)) * Real.sqrt (D1 * D2 / (σ1 * σ2))
have hadd : T + (4 * M * D1) / (σ1 * denom) ≤ T + (4 * M * D1) / (σ1 * ((N : ℝ) + 1) ^ (2 : ℕ)) := by
exact add_le_add (le_rfl : T ≤ T) hMterm
have hgap' :
f (ySeq N : E1) - φ hatu ≤ T + (4 * M * D1) / (σ1 * denom) := by
dsimp [T]
exact hgap_bound'''
exact le_trans hgap' hadd
dsimp [D2] at hgap_bound''''
exact hgap_bound''''
refine And.intro hgap_bound' ?_
intro ε hε hN
set a : ℝ :=
4 * OperatorNormDef A' * Real.sqrt (D1 * sSup (d2 '' Q2) / (σ1 * σ2))
set b : ℝ := 4 * M * D1 / σ1
have ha : 0 ≤ a := by
have hAop : 0 ≤ OperatorNormDef A' := operatorNormDef_nonneg (A := A')
have hsqrt : 0 ≤ Real.sqrt (D1 * sSup (d2 '' Q2) / (σ1 * σ2)) := by
exact Real.sqrt_nonneg _
nlinarith [hAop, hsqrt]
have hb : 0 ≤ b := by
have hσ1_nonneg : 0 ≤ σ1 := le_of_lt hσ1
have hnum_nonneg : 0 ≤ 4 * M * D1 := by
have h4_nonneg : (0 : ℝ) ≤ 4 := by norm_num
have h4M_nonneg : 0 ≤ 4 * M := mul_nonneg h4_nonneg hM_nonneg
exact mul_nonneg h4M_nonneg hD1_nonneg
dsimp [b]
exact div_nonneg hnum_nonneg hσ1_nonneg
have hN' :
(N : ℝ) + 1 ≥ a / ε + Real.sqrt (b / ε) := by
have hAop :
(4 * OperatorNormDef A' / ε) *
Real.sqrt (D1 * sSup (d2 '' Q2) / (σ1 * σ2)) =
a / ε := by
dsimp [a]
simpa using
(div_mul_eq_mul_div (4 * OperatorNormDef A') ε
(Real.sqrt (D1 * sSup (d2 '' Q2) / (σ1 * σ2))))
have hB : 2 * Real.sqrt (M * D1 / (σ1 * ε)) = Real.sqrt (b / ε) := by
have hbε : b / ε = 4 * (M * D1 / (σ1 * ε)) := by
dsimp [b]
calc
(4 * M * D1 / σ1) / ε = (4 * M * D1) / (σ1 * ε) := by
simp [div_div, mul_assoc]
_ = (4 * (M * D1)) / (σ1 * ε) := by simp [mul_assoc]
_ = 4 * (M * D1 / (σ1 * ε)) := by
simpa [mul_assoc] using (mul_div_assoc (4 : ℝ) (M * D1) (σ1 * ε))
-- rewrite the right-hand side using `hbε`
rw [hbε]
have hs :
Real.sqrt (4 * (M * D1 / (σ1 * ε))) =
(2 : ℝ) * Real.sqrt (M * D1 / (σ1 * ε)) := by
have h :=
Real.sqrt_mul (by norm_num : (0 : ℝ) ≤ 4) (M * D1 / (σ1 * ε))
have hsqrt4 : Real.sqrt (4 : ℝ) = (2 : ℝ) := by
have h :=
Real.sqrt_mul_self (x := (2 : ℝ)) (by norm_num : (0 : ℝ) ≤ (2 : ℝ))
simpa [show (2 : ℝ) * 2 = 4 by norm_num] using h
calc
Real.sqrt (4 * (M * D1 / (σ1 * ε))) =
Real.sqrt 4 * Real.sqrt (M * D1 / (σ1 * ε)) := h
_ = (2 : ℝ) * Real.sqrt (M * D1 / (σ1 * ε)) := by
rw [hsqrt4]
exact hs.symm
have hmain : a / ε + Real.sqrt (b / ε) ≤ (N : ℝ) := by
-- rewrite the bound hypothesis `hN` into the `a,b` notation
have hab :
a / ε + Real.sqrt (b / ε) =
(4 * OperatorNormDef A' / ε) *
Real.sqrt (D1 * sSup (d2 '' Q2) / (σ1 * σ2)) +
2 * Real.sqrt (M * D1 / (σ1 * ε)) := by
-- rewrite each term separately
rw [hAop.symm, hB.symm]
-- `hN` already has the right inequality direction (`≥`)
have : (4 * OperatorNormDef A' / ε) *
Real.sqrt (D1 * sSup (d2 '' Q2) / (σ1 * σ2)) +
2 * Real.sqrt (M * D1 / (σ1 * ε)) ≤ (N : ℝ) := by
simpa using hN
simpa [hab] using this
have hNle : (N : ℝ) ≤ (N : ℝ) + 1 := by
exact le_add_of_nonneg_right (by norm_num)
exact le_trans hmain hNle
have hε_bound :=
epsilon_bound_from_gap (a := a) (b := b) (ε := ε) (N := N) hε ha hb hN'
have hgap_bound'' :
f (ySeq N : E1) - φ hatu ≤ a / ((N : ℝ) + 1) + b / ((N : ℝ) + 1) ^ (2 : ℕ) := by
have hrhs :
(4 * OperatorNormDef A' / ((N : ℝ) + 1)) *
Real.sqrt (D1 * sSup (d2 '' Q2) / (σ1 * σ2)) +
(4 * M * D1) / (σ1 * ((N : ℝ) + 1) ^ (2 : ℕ)) =
a / ((N : ℝ) + 1) + b / ((N : ℝ) + 1) ^ (2 : ℕ) := by
dsimp [a, b]
rw [div_mul_eq_mul_div (4 * OperatorNormDef A') ((N : ℝ) + 1)
(Real.sqrt (D1 * sSup (d2 '' Q2) / (σ1 * σ2)))]
rw [div_mul_eq_div_div (4 * M * D1) σ1 (((N : ℝ) + 1) ^ (2 : ℕ))]
exact le_trans hgap_bound' (le_of_eq hrhs)
linarith [hgap_bound'', hε_bound]
Compatibility-layer version of Theorem 1.4.1 that still takes an explicit averaged dual point
together with its defining equality.
theorem algorithm311_duality_gap_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 : E2 → ℝ) (d1 : E1 → ℝ) (d2 : E2 → ℝ) (σ1 σ2 M D1 : ℝ)
(xSeq ySeq : ℕ → 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) :
let A' : E1 →ₗ[ℝ] Module.Dual ℝ E2 :=
{ toFun := fun x => (A x).toLinearMap
map_add' := by
intro x y
ext u
simp
map_smul' := by
intro c x
ext u
simp }
let D2 : ℝ := sSup (d2 '' Q2)
let μ : ℝ :=
(2 * OperatorNormDef A' / ((N : ℝ) + 1)) *
Real.sqrt (D1 / (σ1 * σ2 * D2))
let uμ : E1 → E2 :=
smoothedMaximizer Q2 A phihat d2 μ hQ2_closed hQ2_bdd hQ2_nonempty hphihat hd2
let fbar : E1 → ℝ := SmoothedObjective Q2 A phihat d2 μ fhat
let f : E1 → ℝ := fun x => fhat x + sSup ((fun u => A x u - phihat u) '' Q2)
let φ : Q2 → ℝ := AdjointFormPotential Q1 Q2 A fhat phihat
LipschitzOnWith (Real.toNNReal M) (fun x => fderiv ℝ fhat x) Q1 →
0 < σ1 →
0 < σ2 →
StrongConvexOn Q1 σ1 d1 →
StrongConvexOn Q2 σ2 d2 →
IsProxDiameterBound Q1 d1 D1 →
OptimalSchemeAlgorithm Q1 fbar d1
(M + (1 / (μ * σ2)) * (OperatorNormDef A') ^ 2) σ1 xSeq ySeq →
(hatu : E2) =
Finset.sum (Finset.range (N + 1)) (fun i =>
(2 * ((i : ℝ) + 1) / (((N : ℝ) + 1) * ((N : ℝ) + 2))) •
uμ (xSeq i : E1)) →
ConvexOn ℝ Q1 fhat →
DifferentiableOn ℝ fhat Q1 →
ConvexOn ℝ Q2 phihat →
0 < μ →
0 ≤ M →
0 ≤ D1 →
0 < M + (1 / (μ * σ2)) * (OperatorNormDef A') ^ 2 →
IsClosed Q1 →
IsOpen Q1 →
(∀ u ∈ Q2, 0 ≤ d2 u) →
(∀ x, BddAbove ((fun u => A x u - phihat u) '' Q2)) →
BddAbove (d2 '' Q2) →
(∀ u, BddBelow ((fun x => A x u + fhat x) '' Q1)) →
0 ≤ f (ySeq N : E1) - φ hatu ∧
f (ySeq N : E1) - φ hatu ≤
(4 * OperatorNormDef A' / ((N : ℝ) + 1)) * Real.sqrt (D1 * D2 / (σ1 * σ2)) +
(4 * M * D1) / (σ1 * ((N : ℝ) + 1) ^ (2 : ℕ)) ∧
∀ ε > 0,
(N : ℝ) ≥
(4 * OperatorNormDef A' / ε) * Real.sqrt (D1 * D2 / (σ1 * σ2)) +
2 * Real.sqrt (M * D1 / (σ1 * ε)) →
f (ySeq N : E1) - φ hatu ≤ ε := by
classical
simp only
intro hLipschitz hσ1 hσ2 hconv1 hconv2 hD1 hAlg hhatudef
hfhat_convex hfhat_diff hphihat_convex hμ_pos hM_nonneg hD1_nonneg hL_pos
hQ1_closed hQ1_open hd2_nonneg hbd0 hbd_d2 hbdBelow
let A' : E1 →ₗ[ℝ] Module.Dual ℝ E2 :=
{ toFun := fun x => (A x).toLinearMap
map_add' := by
intro x y
ext u
simp
map_smul' := by
intro c x
ext u
simp }
let μ : ℝ :=
(2 * OperatorNormDef A' / ((N : ℝ) + 1)) *
Real.sqrt (D1 / (σ1 * σ2 * sSup (d2 '' Q2)))
let uμ : E1 → E2 := smoothedMaximizer Q2 A phihat d2 μ hQ2_closed hQ2_bdd hQ2_nonempty hphihat hd2
have hmax : ∀ x, IsSmoothedMaximizer Q2 A phihat d2 μ x (uμ x) := by
simpa [uμ] using
(smoothedMaximizer_isSmoothedMaximizer (Q2 := Q2) (A := A) (phihat := phihat)
(d2 := d2) (μ := μ) hQ2_closed hQ2_bdd hQ2_nonempty hphihat hd2)
simpa [A', μ, uμ] using
(algorithm311_duality_gap_bound_of_isSmoothedMaximizer
(Q1 := Q1) (Q2 := Q2) (A := A) (fhat := fhat)
(phihat := phihat) (d1 := d1) (d2 := d2) (σ1 := σ1) (σ2 := σ2) (M := M)
(D1 := D1) (xSeq := xSeq) (ySeq := ySeq) (uμ := uμ) (N := N) (hatu := hatu)
hLipschitz hσ1 hσ2 hconv1 hconv2 hD1 hAlg hmax hhatudef hfhat_convex hfhat_diff
hphihat_convex hμ_pos hM_nonneg hD1_nonneg hL_pos hQ1_closed hQ1_open
hd2_nonneg hbd0 hbd_d2 hQ2_nonempty hbdBelow)
Paper-facing version of Theorem 1.4.1 where is defined canonically by the weighted
average (4.2), instead of being passed in together with a separate defining equality.
theorem algorithm311_duality_gap_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 : E2 → ℝ) (d1 : E1 → ℝ) (d2 : E2 → ℝ) (σ1 σ2 M D1 : ℝ)
(xSeq ySeq : ℕ → 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) :
let A' : E1 →ₗ[ℝ] Module.Dual ℝ E2 :=
{ toFun := fun x => (A x).toLinearMap
map_add' := by
intro x y
ext u
simp
map_smul' := by
intro c x
ext u
simp }
let D2 : ℝ := sSup (d2 '' Q2)
let μ : ℝ :=
(2 * OperatorNormDef A' / ((N : ℝ) + 1)) *
Real.sqrt (D1 / (σ1 * σ2 * D2))
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)
let fbar : E1 → ℝ := SmoothedObjective Q2 A phihat d2 μ fhat
let f : E1 → ℝ := fun x => fhat x + sSup ((fun u => A x u - phihat u) '' Q2)
let φ : Q2 → ℝ := AdjointFormPotential Q1 Q2 A fhat phihat
LipschitzOnWith (Real.toNNReal M) (fun x => fderiv ℝ fhat x) Q1 →
0 < σ1 →
0 < σ2 →
StrongConvexOn Q1 σ1 d1 →
StrongConvexOn Q2 σ2 d2 →
IsProxDiameterBound Q1 d1 D1 →
OptimalSchemeAlgorithm Q1 fbar d1
(M + (1 / (μ * σ2)) * (OperatorNormDef A') ^ 2) σ1 xSeq ySeq →
ConvexOn ℝ Q1 fhat →
DifferentiableOn ℝ fhat Q1 →
ConvexOn ℝ Q2 phihat →
0 < μ →
0 ≤ M →
0 ≤ D1 →
0 < M + (1 / (μ * σ2)) * (OperatorNormDef A') ^ 2 →
IsClosed Q1 →
IsOpen Q1 →
(∀ u ∈ Q2, 0 ≤ d2 u) →
(∀ x, BddAbove ((fun u => A x u - phihat u) '' Q2)) →
BddAbove (d2 '' Q2) →
(∀ u, BddBelow ((fun x => A x u + fhat x) '' Q1)) →
0 ≤ f (ySeq N : E1) - φ hatu ∧
f (ySeq N : E1) - φ hatu ≤
(4 * OperatorNormDef A' / ((N : ℝ) + 1)) * Real.sqrt (D1 * D2 / (σ1 * σ2)) +
(4 * M * D1) / (σ1 * ((N : ℝ) + 1) ^ (2 : ℕ)) ∧
∀ ε > 0,
(N : ℝ) ≥
(4 * OperatorNormDef A' / ε) * Real.sqrt (D1 * D2 / (σ1 * σ2)) +
2 * Real.sqrt (M * D1 / (σ1 * ε)) →
f (ySeq N : E1) - φ hatu ≤ ε := by
classical
simp only
intro hLipschitz hσ1 hσ2 hconv1 hconv2 hD1 hAlg hfhat_convex hfhat_diff
hphihat_convex hμ_pos hM_nonneg hD1_nonneg hL_pos hQ1_closed hQ1_open
hd2_nonneg hbd0 hbd_d2 hbdBelow
let A' : E1 →ₗ[ℝ] Module.Dual ℝ E2 :=
{ toFun := fun x => (A x).toLinearMap
map_add' := by
intro x y
ext u
simp
map_smul' := by
intro c x
ext u
simp }
let μ : ℝ :=
(2 * OperatorNormDef A' / ((N : ℝ) + 1)) *
Real.sqrt (D1 / (σ1 * σ2 * sSup (d2 '' Q2)))
let uμ : E1 → E2 := smoothedMaximizer Q2 A phihat d2 μ hQ2_closed hQ2_bdd hQ2_nonempty hphihat hd2
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)
have hhatudef :
(hatu : E2) =
Finset.sum (Finset.range (N + 1)) (fun i =>
(2 * ((i : ℝ) + 1) / (((N : ℝ) + 1) * ((N : ℝ) + 2))) •
uμ (xSeq i : E1)) := by
simp [hatu, uμ, averagedDualPoint, averagedDualPoint_of_isSmoothedMaximizer, averagedDualWeight]
exact algorithm311_duality_gap_bound_hatu
(Q1 := Q1) (Q2 := Q2) (A := A) (fhat := fhat) (phihat := phihat) (d1 := d1) (d2 := d2)
(σ1 := σ1) (σ2 := σ2) (M := M) (D1 := D1) (xSeq := xSeq) (ySeq := ySeq) (N := N)
(hatu := hatu) (hQ2_closed := hQ2_closed) (hQ2_bdd := hQ2_bdd) (hQ2_nonempty := hQ2_nonempty)
(hphihat := hphihat) (hd2 := hd2)
hLipschitz hσ1 hσ2 hconv1 hconv2 hD1 hAlg hhatudef hfhat_convex hfhat_diff
hphihat_convex hμ_pos hM_nonneg hD1_nonneg hL_pos hQ1_closed hQ1_open hd2_nonneg
hbd0 hbd_d2 hbdBelow
Paper-facing canonical version of Theorem 1.4.1 where is defined by the weighted
average (4.2).
theorem algorithm311_duality_gap_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 : E2 → ℝ) (d1 : E1 → ℝ) (d2 : E2 → ℝ) (σ1 σ2 M D1 : ℝ)
(xSeq ySeq : ℕ → 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) :
let A' : E1 →ₗ[ℝ] Module.Dual ℝ E2 :=
{ toFun := fun x => (A x).toLinearMap
map_add' := by
intro x y
ext u
simp
map_smul' := by
intro c x
ext u
simp }
let D2 : ℝ := sSup (d2 '' Q2)
let μ : ℝ :=
(2 * OperatorNormDef A' / ((N : ℝ) + 1)) *
Real.sqrt (D1 / (σ1 * σ2 * D2))
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)
let fbar : E1 → ℝ := SmoothedObjective Q2 A phihat d2 μ fhat
let f : E1 → ℝ := fun x => fhat x + sSup ((fun u => A x u - phihat u) '' Q2)
let φ : Q2 → ℝ := AdjointFormPotential Q1 Q2 A fhat phihat
LipschitzOnWith (Real.toNNReal M) (fun x => fderiv ℝ fhat x) Q1 →
0 < σ1 →
0 < σ2 →
StrongConvexOn Q1 σ1 d1 →
StrongConvexOn Q2 σ2 d2 →
IsProxDiameterBound Q1 d1 D1 →
OptimalSchemeAlgorithm Q1 fbar d1
(M + (1 / (μ * σ2)) * (OperatorNormDef A') ^ 2) σ1 xSeq ySeq →
ConvexOn ℝ Q1 fhat →
DifferentiableOn ℝ fhat Q1 →
ConvexOn ℝ Q2 phihat →
0 < μ →
0 ≤ M →
0 ≤ D1 →
0 < M + (1 / (μ * σ2)) * (OperatorNormDef A') ^ 2 →
IsClosed Q1 →
IsOpen Q1 →
(∀ u ∈ Q2, 0 ≤ d2 u) →
(∀ x, BddAbove ((fun u => A x u - phihat u) '' Q2)) →
BddAbove (d2 '' Q2) →
(∀ u, BddBelow ((fun x => A x u + fhat x) '' Q1)) →
0 ≤ f (ySeq N : E1) - φ hatu ∧
f (ySeq N : E1) - φ hatu ≤
(4 * OperatorNormDef A' / ((N : ℝ) + 1)) * Real.sqrt (D1 * D2 / (σ1 * σ2)) +
(4 * M * D1) / (σ1 * ((N : ℝ) + 1) ^ (2 : ℕ)) ∧
∀ ε > 0,
(N : ℝ) ≥
(4 * OperatorNormDef A' / ε) * Real.sqrt (D1 * D2 / (σ1 * σ2)) +
2 * Real.sqrt (M * D1 / (σ1 * ε)) →
f (ySeq N : E1) - φ hatu ≤ ε := by
exact algorithm311_duality_gap_bound_averagedDualPoint
(Q1 := Q1) (Q2 := Q2) (A := A) (fhat := fhat) (phihat := phihat) (d1 := d1) (d2 := d2)
(σ1 := σ1) (σ2 := σ2) (M := M) (D1 := D1) (xSeq := xSeq) (ySeq := ySeq) (N := N)
(hQ2_convex := hQ2_convex) (hQ2_closed := hQ2_closed) (hQ2_bdd := hQ2_bdd)
(hQ2_nonempty := hQ2_nonempty) (hphihat := hphihat) (hd2 := hd2)