§3.3, proof of Theorem 3.8, pp. 272–273 — one step of Frank–Wolfe: δ_{s+1} ≤ (1 − γ_s)δ_s + (β/2)γ_s²R²
ProvedConvexOptAlg.FrankWolfe.thm_3_8_stepLet 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 . Let be a run of conditional gradient descent on with step sizes for all , and write . Then for every ,
This one-step recursion is the whole content of the analysis of Theorem 3.8; the rate then follows from a scalar induction.
Formalization Note is Metric.diam X, which is the supremum of over because is compact (hence bounded). The step sizes are required to lie in , which keeps every iterate in ; the book applies the recursion only to , which satisfies this. is the usual reading of "β-smooth". The minimizer is the book's standing assumption (p. 242).
import Mathlib import Definitions.Def_ConvexOptAlg_FrankWolfe_Defs
namespace ConvexOptAlg.FrankWolfe
/-- Bubeck, arXiv:1405.4980v2, proof of Theorem 3.8, pp. 272–273 (the displayed chain and its
rewriting): for a run of conditional gradient descent with step sizes `γ_s ∈ [0, 1]` on a convex
`f`, β-smooth in an arbitrary norm, over a compact convex `X` with minimizer `x∗`, and
`R = sup_{x,y∈X} ‖x − y‖ = diam X`, the gaps `δ_s = f(x_s) − f(x∗)` satisfy, for every `s ≥ 1`,
`δ_{s+1} ≤ (1 − γ_s) δ_s + (β/2) γ_s² R²`. -/
theorem thm_3_8_step {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γ : ∀ s : ℕ, 1 ≤ s → γ s ∈ Set.Icc (0 : ℝ) 1)
(x y : ℕ → E) (hrun : IsFrankWolfeRun X f' γ x y)
(s : ℕ) (hs : 1 ≤ s) :
f (x (s + 1)) - f xstar ≤
(1 - γ s) * (f (x s) - f xstar) + β / 2 * γ s ^ 2 * Metric.diam X ^ 2 := by sorry
end ConvexOptAlg.FrankWolfe
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.