§6, display after (6.5) — for
ProvedPrimalDualSubgrad.Stoch.gap_lower_boundconvex-optimizationdual-averagingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1stochastic-optimization
Under the standing assumptions of §6, let be a minimizer of over . Fix and a realization of the samples, let be the points of the method of stochastic simple averages (6.3) on it and the gap (6.4). If , then for every
The gap of a run therefore dominates the average excess cost of the visited points against the optimum on the same samples; this is the second step of the proof of Theorem 7.
Formalization Note . The two inequalities are stated as a conjunction, each written with .
Preamble
import Mathlib import Definitions.Def_PrimalDualSubgrad_Stoch_ProxSetting import Definitions.Def_PrimalDualSubgrad_Stoch_SSA
Formal statement
namespace PrimalDualSubgrad.Stoch
open Finset MeasureTheory
variable {E : Type*} [NormedAddCommGroup E] [NormedSpace ℝ E] [FiniteDimensional ℝ E]
[MeasurableSpace E] [BorelSpace E]
variable {Ξ : Type*} [MeasurableSpace Ξ]
/-- Nesterov 2009, §6, display after (6.5), p. 26: for `D ≥ d(x*)` and every sample path,
`(1/S_k) δ̃_k(D) ≥ (1/(k+1)) Σ ⟨f'(x̃_i, ξ̃_i), x̃_i − x*⟩ ≥ (1/(k+1)) Σ [f(x̃_i, ξ̃_i) − f(x*, ξ̃_i)]`
(the two inequalities as a conjunction, the first written right-to-left). -/
theorem gap_lower_bound (Q : Set E) (d : E → ℝ) (σ : ℝ) (x0 : E) (hd : ProxFunction Q d σ x0)
(π : ℝ → StrongDual ℝ E → E) (hπ : IsArgminMap Q d π)
(μ : Measure Ξ) [IsProbabilityMeasure μ] (f : E → Ξ → ℝ) (f' : E → Ξ → StrongDual ℝ E)
(L : ℝ) (hf : StochOracle Q μ f f' L)
(xstar : E) (hxstar : xstar ∈ Q)
(hmin : ∀ x ∈ Q, expectedCost μ f xstar ≤ expectedCost μ f x)
(γ : ℝ) (hγ : 0 < γ) (ω : ℕ → Ξ) (k : ℕ) (D : ℝ) (hD : d xstar ≤ D) :
1 / ((k : ℝ) + 1) * ∑ i ∈ range (k + 1), f' (ssaRun π γ x0 f' ω i) (ω i) (ssaRun π γ x0 f' ω i - xstar)
≤ 1 / ((k : ℝ) + 1) * gap Q d (fun i => f' (ssaRun π γ x0 f' ω i) (ω i)) (ssaRun π γ x0 f' ω) k D ∧
1 / ((k : ℝ) + 1) * ∑ i ∈ range (k + 1), (f (ssaRun π γ x0 f' ω i) (ω i) - f xstar (ω i))
≤ 1 / ((k : ℝ) + 1) * ∑ i ∈ range (k + 1), f' (ssaRun π γ x0 f' ω i) (ω i) (ssaRun π γ x0 f' ω i - xstar) := by sorry
end PrimalDualSubgrad.Stoch
Source
Nesterov, Primal-dual subgradient methods for convex problems, Math. Program. 120 (2009), §6, display after (6.5), p. 26
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.