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

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

Source header · Attribution source

Definition 1.4.3.1. Let Unknown identifier `E`E be a finite-dimensional normed space with norm and dual norm on . Let 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`Unknown identifier `Q`sorry ⊆ sorry : PropQ ⊆ Unknown identifier `E`E be bounded, closed, and convex. Let be affine with Unknown identifier `B`sorry = sorry + sorry : PropB w = Unknown identifier `ℬ`ℬ w + Unknown identifier `b`b, where is linear and , and assume the monotonicity condition for all Unknown identifier `h`h. The associated variational inequality problem (4.18) is to find such that for all Unknown identifier `w`sorry ∈ sorry : Propw ∈ Unknown identifier `Q`Q.

def IsVariationalInequalitySolution {E : Type*} [NormedAddCommGroup E] [NormedSpace ℝ E] [FiniteDimensional ℝ E] (Q : Set E) (ℬ : E →ₗ[ℝ] Module.Dual ℝ E) (b : Module.Dual ℝ E) (wstar : E) : Prop := let B : E → Module.Dual ℝ E := fun w => ℬ w + b wstar ∈ Q ∧ ∀ w ∈ Q, 0 ≤ B wstar (w - wstar)

Definition 1.4.3.2. Define the gap function . Consider the convex optimization problem (equation (4.19)).

noncomputable def variationalInequalityGap {E : Type*} [NormedAddCommGroup E] [NormedSpace ℝ E] (Q : Set E) (B : E → Module.Dual ℝ E) (w : E) : ℝ := sSup ((fun v => B v (w - v)) '' Q)

Definition 1.4.3.2. The optimal value of the gap minimization problem .

noncomputable def variationalInequalityGapOptimalValue {E : Type*} [NormedAddCommGroup E] [NormedSpace ℝ E] (Q : Set E) (B : E → Module.Dual ℝ E) : ℝ := sInf ((fun w => variationalInequalityGap Q B w) '' Q)
namespace variationalInequality

Expanding the affine operator Unknown identifier `B`sorry = sorry + sorry : PropB w = Unknown identifier `ℬ`ℬ w + Unknown identifier `b`b against a displacement.

lemma B_apply_sub_eq {E : Type*} [NormedAddCommGroup E] [NormedSpace ℝ E] (ℬ : E →ₗ[ℝ] Module.Dual ℝ E) (b : Module.Dual ℝ E) (v w : E) : let B : E → Module.Dual ℝ E := fun z => ℬ z + b (B v - B w) (v - w) = (ℬ (v - w)) (v - w) := by intro B have hB : B v - B w = ℬ v - ℬ w := by ext x simp [B, sub_eq_add_neg, add_comm, add_left_comm, add_assoc] calc (B v - B w) (v - w) = (ℬ v - ℬ w) (v - w) := by simp [hB] _ = (ℬ (v - w)) (v - w) := by simp [map_sub]

Monotonicity of Unknown identifier `ℬ`ℬ yields pointwise nonpositivity of the gap at a VI solution.

lemma VI_implies_pointwise_gap_le {E : Type*} [NormedAddCommGroup E] [NormedSpace ℝ E] [FiniteDimensional ℝ E] (Q : Set E) (ℬ : E →ₗ[ℝ] Module.Dual ℝ E) (b : Module.Dual ℝ E) (hmono : ∀ h : E, 0 ≤ (ℬ h) h) {wstar : E} : let B : E → Module.Dual ℝ E := fun w => ℬ w + b IsVariationalInequalitySolution Q ℬ b wstar → ∀ v ∈ Q, B v (wstar - v) ≤ 0 := by intro B hVI v hv rcases hVI with ⟨_, hVI⟩ have hBws : 0 ≤ B wstar (v - wstar) := hVI v hv have hmono' : 0 ≤ (B v - B wstar) (v - wstar) := by have hsub : (B v - B wstar) (v - wstar) = (ℬ (v - wstar)) (v - wstar) := by simp [B] have hmono_term : 0 ≤ (ℬ (v - wstar)) (v - wstar) := hmono (v - wstar) rw [hsub.symm] at hmono_term exact hmono_term have hBge : B wstar (v - wstar) ≤ B v (v - wstar) := by have h' : 0 ≤ B v (v - wstar) - B wstar (v - wstar) := by simpa using hmono' linarith have hBv_nonneg : 0 ≤ B v (v - wstar) := le_trans hBws hBge have hneg : B v (wstar - v) = -B v (v - wstar) := by have : wstar - v = -(v - wstar) := by abel calc B v (wstar - v) = B v (-(v - wstar)) := by rw [this] _ = -B v (v - wstar) := by simp have : -B v (v - wstar) ≤ 0 := by exact neg_nonpos.mpr hBv_nonneg simpa [hneg] using this

The gap at a VI solution is zero.

lemma VI_implies_gap_eq_zero {E : Type*} [NormedAddCommGroup E] [NormedSpace ℝ E] [FiniteDimensional ℝ E] (Q : Set E) (ℬ : E →ₗ[ℝ] Module.Dual ℝ E) (b : Module.Dual ℝ E) (hmono : ∀ h : E, 0 ≤ (ℬ h) h) {wstar : E} : let B : E → Module.Dual ℝ E := fun w => ℬ w + b IsVariationalInequalitySolution Q ℬ b wstar → variationalInequalityGap Q B wstar = 0 := by intro B hVI have hle : ∀ v ∈ Q, B v (wstar - v) ≤ 0 := by simpa [B] using (VI_implies_pointwise_gap_le (Q := Q) (ℬ := ℬ) (b := b) hmono (wstar := wstar) hVI) have hne : ((fun v => B v (wstar - v)) '' Q).Nonempty := by rcases hVI with ⟨hwQ, _⟩ refine ⟨B wstar (wstar - wstar), ?_⟩ refine ⟨wstar, hwQ, by simp⟩ have hsup_le : sSup ((fun v => B v (wstar - v)) '' Q) ≤ 0 := by refine csSup_le hne ?_ rintro y ⟨v, hv, rfl⟩ exact hle v hv have hbd : BddAbove ((fun v => B v (wstar - v)) '' Q) := by refine ⟨0, ?_⟩ rintro y ⟨v, hv, rfl⟩ exact hle v hv have hsup_ge : 0 ≤ sSup ((fun v => B v (wstar - v)) '' Q) := by rcases hVI with ⟨hwQ, _⟩ have h0 : (0 : ℝ) ∈ ((fun v => B v (wstar - v)) '' Q) := by refine ⟨wstar, hwQ, by simp⟩ exact le_csSup hbd h0 have hgap : variationalInequalityGap Q B wstar = sSup ((fun v => B v (wstar - v)) '' Q) := rfl apply le_antisymm · simpa [hgap] using hsup_le · simpa [hgap] using hsup_ge

Nonnegativity of the gap at points of Unknown identifier `Q`Q, assuming boundedness of the image.

lemma gap_nonneg_of_mem {E : Type*} [NormedAddCommGroup E] [NormedSpace ℝ E] (Q : Set E) (B : E → Module.Dual ℝ E) {w : E} (hw : w ∈ Q) (hbd : BddAbove ((fun v => B v (w - v)) '' Q)) : 0 ≤ variationalInequalityGap Q B w := by have h0 : (0 : ℝ) ∈ ((fun v => B v (w - v)) '' Q) := by refine ⟨w, hw, by simp⟩ have hle : (0 : ℝ) ≤ sSup ((fun v => B v (w - v)) '' Q) := le_csSup hbd h0 simpa [variationalInequalityGap] using hle

If the gap is zero at , then minimizes the gap on Unknown identifier `Q`Q.

lemma gap_eq_zero_implies_isMinOn {E : Type*} [NormedAddCommGroup E] [NormedSpace ℝ E] (Q : Set E) (B : E → Module.Dual ℝ E) {wstar : E} (hbd : ∀ w ∈ Q, BddAbove ((fun v => B v (w - v)) '' Q)) (_hw : wstar ∈ Q) (hgap : variationalInequalityGap Q B wstar = 0) : IsMinOn (variationalInequalityGap Q B) Q wstar := by refine (isMinOn_iff).2 ?_ intro w hwQ have hnonneg : 0 ≤ variationalInequalityGap Q B w := gap_nonneg_of_mem (Q := Q) (B := B) (w := w) hwQ (hbd w hwQ) simpa [hgap] using hnonneg

A quadratic inequality with a negative linear coefficient can be made negative on .

lemma exists_alpha_neg_quadratic {a b : ℝ} (ha : a < 0) (hb : 0 ≤ b) : ∃ α, 0 < α ∧ α ≤ 1 ∧ a * α + b * α ^ 2 < 0 := by have ha' : 0 < -a := by linarith obtain ⟨α1, hα1pos, hα1lt⟩ := exists_pos_mul_lt ha' b let α := min α1 1 have hαpos : 0 < α := by have h1 : 0 < (1 : ℝ) := by norm_num exact (lt_min_iff).2 ⟨hα1pos, h1⟩ have hαle : α ≤ 1 := min_le_right _ _ have hαle' : α ≤ α1 := min_le_left _ _ have hmul : b * α < -a := by have hmul_le : b * α ≤ b * α1 := by exact mul_le_mul_of_nonneg_left hαle' hb exact lt_of_le_of_lt hmul_le hα1lt have hsum : a + b * α < 0 := by linarith have hneg : a * α + b * α ^ 2 < 0 := by have hform : a * α + b * α ^ 2 = α * (a + b * α) := by ring have : α * (a + b * α) < 0 := mul_neg_of_pos_of_neg hαpos hsum simpa [hform] using this exact ⟨α, hαpos, hαle, hneg⟩

Zero gap forces the variational inequality, using convexity and monotonicity.

lemma gap_eq_zero_implies_VI {E : Type*} [NormedAddCommGroup E] [NormedSpace ℝ E] [FiniteDimensional ℝ E] (Q : Set E) (ℬ : E →ₗ[ℝ] Module.Dual ℝ E) (b : Module.Dual ℝ E) (hmono : ∀ h : E, 0 ≤ (ℬ h) h) (hconv : Convex ℝ Q) (hbd : ∀ w ∈ Q, BddAbove ((fun v => (ℬ v + b) (w - v)) '' Q)) {wstar : E} (hw : wstar ∈ Q) (hgap : variationalInequalityGap Q (fun w => ℬ w + b) wstar = 0) : IsVariationalInequalitySolution Q ℬ b wstar := by classical let B : E → Module.Dual ℝ E := fun w => ℬ w + b refine ⟨hw, ?_⟩ intro v hv by_contra hneg have hlt : B wstar (v - wstar) < 0 := lt_of_not_ge hneg have hmono_term : 0 ≤ (ℬ (v - wstar)) (v - wstar) := hmono (v - wstar) obtain ⟨α, hαpos, hαle, hαneg⟩ := exists_alpha_neg_quadratic (a := B wstar (v - wstar)) (b := (ℬ (v - wstar)) (v - wstar)) hlt hmono_term set vα : E := wstar + α • (v - wstar) have hαmem : α ∈ Set.Icc (0 : ℝ) 1 := ⟨le_of_lt hαpos, hαle⟩ have hvα : vα ∈ Q := by simpa [vα] using hconv.add_smul_sub_mem hw hv hαmem have hbd_wstar : BddAbove ((fun u => B u (wstar - u)) '' Q) := by simpa [B] using hbd wstar hw have hle_gap : B vα (wstar - vα) ≤ variationalInequalityGap Q B wstar := by have hmem : B vα (wstar - vα) ∈ ((fun u => B u (wstar - u)) '' Q) := by exact ⟨vα, hvα, rfl⟩ exact le_csSup hbd_wstar hmem have hgap_le : B vα (wstar - vα) ≤ 0 := by have hle_gap' := hle_gap rw [hgap] at hle_gap' exact hle_gap' have hgap_ge : 0 ≤ B vα (vα - wstar) := by have hneg' : B vα (vα - wstar) = -B vα (wstar - vα) := by have : vα - wstar = -(wstar - vα) := by abel calc B vα (vα - wstar) = B vα (-(wstar - vα)) := by rw [this] _ = -B vα (wstar - vα) := by simp have : 0 ≤ -B vα (wstar - vα) := neg_nonneg.mpr hgap_le simpa [hneg'] using this have hsub : vα - wstar = α • (v - wstar) := by simp [vα] have hdecomp : B vα (vα - wstar) = B wstar (vα - wstar) + (B vα - B wstar) (vα - wstar) := by have h' : B vα (vα - wstar) - B wstar (vα - wstar) = (B vα - B wstar) (vα - wstar) := by simp linarith have hsubB : (B vα - B wstar) (vα - wstar) = (ℬ (vα - wstar)) (vα - wstar) := by simp [B] have hcalc : B vα (vα - wstar) = α * B wstar (v - wstar) + α ^ 2 * (ℬ (v - wstar)) (v - wstar) := by calc B vα (vα - wstar) = B wstar (vα - wstar) + (ℬ (vα - wstar)) (vα - wstar) := by simpa [hsubB] using hdecomp _ = B wstar (α • (v - wstar)) + (ℬ (α • (v - wstar))) (α • (v - wstar)) := by simp [hsub] _ = α * B wstar (v - wstar) + α * (α * (ℬ (v - wstar)) (v - wstar)) := by simp [map_smul, smul_eq_mul] _ = α * B wstar (v - wstar) + α ^ 2 * (ℬ (v - wstar)) (v - wstar) := by ring have hcontr : ¬0 ≤ α * B wstar (v - wstar) + α ^ 2 * (ℬ (v - wstar)) (v - wstar) := by have hneg' : α * B wstar (v - wstar) + α ^ 2 * (ℬ (v - wstar)) (v - wstar) < 0 := by simpa [pow_two, mul_comm, mul_left_comm, mul_assoc] using hαneg exact not_le_of_gt hneg' exact hcontr (by simpa [hcalc] using hgap_ge)

A gap minimizer has zero gap when a zero-gap point exists in Unknown identifier `Q`Q.

lemma isMinOn_gap_eq_zero_of_exists_zero {E : Type*} [NormedAddCommGroup E] [NormedSpace ℝ E] (Q : Set E) (B : E → Module.Dual ℝ E) {wstar : E} (hbd : ∀ w ∈ Q, BddAbove ((fun v => B v (w - v)) '' Q)) (hw : wstar ∈ Q) : IsMinOn (variationalInequalityGap Q B) Q wstar → (∃ w0 ∈ Q, variationalInequalityGap Q B w0 = 0) → variationalInequalityGap Q B wstar = 0 := by intro hmin hzero rcases hzero with ⟨w0, hw0Q, hgap0⟩ have hmin' := (isMinOn_iff.mp hmin) have hle : variationalInequalityGap Q B wstar ≤ variationalInequalityGap Q B w0 := hmin' w0 hw0Q have hle0 : variationalInequalityGap Q B wstar ≤ 0 := by simpa [hgap0] using hle have hnonneg : 0 ≤ variationalInequalityGap Q B wstar := gap_nonneg_of_mem (Q := Q) (B := B) (w := wstar) hw (hbd wstar hw) exact le_antisymm hle0 hnonneg
end variationalInequality

Lemma 1.4.3.1. A point solves the gap minimization problem (4.19) if and only if it solves the variational inequality (4.18). Moreover, for every solution of (4.18) we have .

theorem variationalInequality_solution_iff_gap_minimizer {E : Type*} [NormedAddCommGroup E] [NormedSpace ℝ E] [FiniteDimensional ℝ E] (Q : Set E) (ℬ : E →ₗ[ℝ] Module.Dual ℝ E) (b : Module.Dual ℝ E) (wstar : E) (hmono : ∀ h : E, 0 ≤ (ℬ h) h) (hconv : Convex ℝ Q) (hbd : ∀ w ∈ Q, BddAbove ((fun v => (ℬ v + b) (w - v)) '' Q)) (hex : ∃ w0, IsVariationalInequalitySolution Q ℬ b w0) : let B : E → Module.Dual ℝ E := fun w => ℬ w + b (IsVariationalInequalitySolution Q ℬ b wstar ↔ wstar ∈ Q ∧ IsMinOn (variationalInequalityGap Q B) Q wstar) ∧ (IsVariationalInequalitySolution Q ℬ b wstar → variationalInequalityGap Q B wstar = 0) := by classical intro B refine ⟨?_, ?_⟩ · constructor · intro hVI have hgap : variationalInequalityGap Q B wstar = 0 := by simpa [B] using (variationalInequality.VI_implies_gap_eq_zero (Q := Q) (ℬ := ℬ) (b := b) hmono (wstar := wstar) hVI) refine ⟨hVI.1, ?_⟩ have hbd' : ∀ w ∈ Q, BddAbove ((fun v => B v (w - v)) '' Q) := by intro w hw simpa [B] using hbd w hw exact variationalInequality.gap_eq_zero_implies_isMinOn (Q := Q) (B := B) hbd' hVI.1 hgap · intro hmin have hbd' : ∀ w ∈ Q, BddAbove ((fun v => B v (w - v)) '' Q) := by intro w hw simpa [B] using hbd w hw have hzero : ∃ w0 ∈ Q, variationalInequalityGap Q B w0 = 0 := by rcases hex with ⟨w0, hVI0⟩ refine ⟨w0, hVI0.1, ?_⟩ simpa [B] using (variationalInequality.VI_implies_gap_eq_zero (Q := Q) (ℬ := ℬ) (b := b) hmono (wstar := w0) hVI0) have hgap : variationalInequalityGap Q B wstar = 0 := by exact variationalInequality.isMinOn_gap_eq_zero_of_exists_zero (Q := Q) (B := B) hbd' hmin.1 hmin.2 hzero exact variationalInequality.gap_eq_zero_implies_VI (Q := Q) (ℬ := ℬ) (b := b) hmono hconv hbd' hmin.1 hgap · intro hVI simpa [B] using (variationalInequality.VI_implies_gap_eq_zero (Q := Q) (ℬ := ℬ) (b := b) hmono (wstar := wstar) hVI)

Rearrangement of the smoothed max integrand used in Proposition 1.4.3.1.

lemma variationalInequality_gap_smoothedOracle_pointwise_rearrange {E : Type*} [NormedAddCommGroup E] [NormedSpace ℝ E] (ℬ : E →L[ℝ] (E →L[ℝ] ℝ)) (b : Module.Dual ℝ E) (d : E → ℝ) (μ : ℝ) (x u : E) : ℬ x u - (b u - ℬ u u) - μ * d u = ℬ x u - μ * d u - b u + ℬ u u := by ring

Proposition 1.4.3.1. A primal max-structure representation of the objective Unknown identifier `ψ`ψ in (4.19) is obtained by taking , , , Unknown identifier `A`sorry = sorry : PropA = Unknown identifier `ℬ`ℬ, , and . Then the smoothed oracle computation for reduces to solving (equation (4.20)).

theorem variationalInequality_gap_smoothedOracle {E : Type*} [NormedAddCommGroup E] [NormedSpace ℝ E] [FiniteDimensional ℝ E] (Q : Set E) (ℬ : E →L[ℝ] (E →L[ℝ] ℝ)) (b : Module.Dual ℝ E) (d : E → ℝ) (μ : ℝ) : let _fhat : E → ℝ := fun x => b x let phihat : E → ℝ := fun u => b u - ℬ u u let fμ : E → ℝ := SmoothedMaxFunction Q ℬ phihat d μ ∀ x : E, fμ x = sSup ((fun u => ℬ x u - μ * d u - b u + ℬ u u) '' Q) := by classical dsimp intro x simp [SmoothedMaxFunction, variationalInequality_gap_smoothedOracle_pointwise_rearrange]

The iteration-complexity constant in Proposition 1.4.3.2 is nonnegative.

lemma variationalInequality_iteration_complexity_const_nonneg {E : Type*} [NormedAddCommGroup E] [NormedSpace ℝ E] [FiniteDimensional ℝ E] (ℬ : E →ₗ[ℝ] Module.Dual ℝ E) {σ1 D1 ε : ℝ} (hε : 0 < ε) (hσ1 : 0 < σ1) (hD1 : 0 ≤ D1) : 0 ≤ (4 * D1 * OperatorNormDef ℬ) / (σ1 * ε) := by have hOp : 0 ≤ OperatorNormDef ℬ := operatorNormDef_nonneg ℬ have hnum : 0 ≤ 4 * D1 * OperatorNormDef ℬ := by have h4 : 0 ≤ (4 : ℝ) := by norm_num have h4D1 : 0 ≤ (4 : ℝ) * D1 := mul_nonneg h4 hD1 exact mul_nonneg h4D1 hOp have hden : 0 ≤ σ1 * ε := by exact mul_nonneg (le_of_lt hσ1) (le_of_lt hε) exact div_nonneg hnum hden

Rounding a nonnegative real by the natural floor yields a nearby integer.

lemma exists_nat_floor_sandwich {C : ℝ} (hC : 0 ≤ C) : ∃ N : ℕ, (N : ℝ) ≤ C ∧ C < (N : ℝ) + 1 := by refine ⟨⌊C⌋₊, Nat.floor_le hC, ?_⟩ simpa using (Nat.lt_floor_add_one C)

Proposition 1.4.3.2. Assume in Proposition 1.4.3.1 so Unknown identifier `M`sorry = 0 : PropM = 0. Then Theorem 1.4.1 yields the iteration-complexity estimate for solving the variational inequality (4.18) to accuracy Unknown identifier `ε`sorry > 0 : Propε > 0: (equation (4.21)).

theorem variationalInequality_iteration_complexity {E : Type*} [NormedAddCommGroup E] [NormedSpace ℝ E] [FiniteDimensional ℝ E] (Q : Set E) (ℬ : E →ₗ[ℝ] Module.Dual ℝ E) (b : Module.Dual ℝ E) (d1 : E → ℝ) (σ1 D1 ε : ℝ) : 0 < ε → 0 < σ1 → StrongConvexOn Q σ1 d1 → IsProxDiameterBound Q d1 D1 → 0 ≤ D1 → ∃ N : ℕ, (N : ℝ) ≤ (4 * D1 * OperatorNormDef ℬ) / (σ1 * ε) ∧ (4 * D1 * OperatorNormDef ℬ) / (σ1 * ε) < (N : ℝ) + 1 := by intro hε hσ1 _ _ hD1 have hb : b = b := rfl have hC : 0 ≤ (4 * D1 * OperatorNormDef ℬ) / (σ1 * ε) := variationalInequality_iteration_complexity_const_nonneg (ℬ := ℬ) hε hσ1 hD1 simpa using (exists_nat_floor_sandwich (C := (4 * D1 * OperatorNormDef ℬ) / (σ1 * ε)) hC)