§3.3, proof of Theorem 3.8, p. 273 — initialization: with γ₁ = 1, δ₂ ≤ (β/2)R²
ProvedConvexOptAlg.FrankWolfe.thm_3_8_initconvex-optimizationfrank-wolfep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-bookp2o-v1
Let be a finite-dimensional real normed space, nonempty, compact and convex, with diameter , and let be differentiable, convex on and -smooth with respect to on for some . Let minimize over , and let be a run of conditional gradient descent on whose first step size is . Then
With one has , so this is the base case of the induction that proves Theorem 3.8, whatever the starting point .
Formalization Note Only is constrained; the later step sizes play no role. is Metric.diam X ( compact). and the existence of are as in the book (standing assumption, p. 242).
Preamble
import Mathlib import Definitions.Def_ConvexOptAlg_FrankWolfe_Defs
Formal statement
namespace ConvexOptAlg.FrankWolfe
/-- Bubeck, arXiv:1405.4980v2, proof of Theorem 3.8, p. 273 ("the initialization is done at step 2
with the above inequality yielding δ₂ ≤ (β/2)R²"): for a run of conditional gradient descent with
`γ₁ = 1` on a convex `f`, β-smooth in an arbitrary norm, over a compact convex `X` with minimizer
`x∗`, and `R = diam X`, one has `f(x₂) − f(x∗) ≤ (β/2) R²`. -/
theorem thm_3_8_init {E : Type*} [NormedAddCommGroup E] [NormedSpace ℝ E] [FiniteDimensional ℝ E]
(X : Set E) (hXc : IsCompact X) (hXconv : Convex ℝ X)
(f : E → ℝ) (f' : E → E →L[ℝ] ℝ) (β : ℝ) (hβ : 0 ≤ β)
(hf : ConvexOn ℝ X f) (hsmooth : IsBetaSmoothNormOn X f f' β)
(xstar : E) (hxstar : xstar ∈ X) (hopt : ∀ z ∈ X, f xstar ≤ f z)
(γ : ℕ → ℝ) (hγ1 : γ 1 = 1)
(x y : ℕ → E) (hrun : IsFrankWolfeRun X f' γ x y) :
f (x 2) - f xstar ≤ β / 2 * Metric.diam X ^ 2 := by sorry
end ConvexOptAlg.FrankWolfe
Source
Bubeck, arXiv:1405.4980v2, §3.3, proof of Theorem 3.8, p. 273 ("the initialization is done at step 2 with the above inequality yielding δ₂ ≤ (β/2)R²")
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.