Theorem 3.8, p. 272 — conditional gradient descent with γ_s = 2/(s + 1) satisfies f(x_t) − f(x*) ≤ 2βR²/(t + 1) in any norm
ProvedConvexOptAlg.FrankWolfe.theorem_3_8Let be a finite-dimensional real vector space with an arbitrary norm and dual norm , and let be nonempty, compact and convex, with diameter
Let be differentiable, convex on , and -smooth with respect to on (), i.e. for , and let minimize over . Run conditional gradient descent from any with step sizes for :
Then for every ,
The rate is independent of the dimension and of the norm in which smoothness is measured, and the method needs only a linear minimization oracle over instead of a projection.
Formalization Note The gradient is an explicit derivative map f' with HasFDerivAt f (f' x) x, is f' x v, and is the operator norm on E →L[ℝ] ℝ. is Metric.diam X, which equals the supremum above because is compact. Convexity and smoothness are assumed on only, which is weaker than the book's global assumptions. The existence of the minimizer is the book's standing assumption (p. 242); is the usual reading of "β-smooth". Every choice of minimizer is allowed, and the conclusion holds for every run.
import Mathlib import Definitions.Def_ConvexOptAlg_FrankWolfe_Defs
namespace ConvexOptAlg.FrankWolfe
/-- Bubeck, arXiv:1405.4980v2, Theorem 3.8, p. 272: let `X` be a compact convex set in a
finite-dimensional real normed space, `f` convex and β-smooth w.r.t. the norm `‖·‖` on `X`,
`x∗ ∈ X` a minimizer of `f` over `X`, `R = sup_{x,y∈X} ‖x − y‖ = diam X`, and `γ_s = 2/(s+1)` for
`s ≥ 1`. Then every run of conditional gradient descent (3.8)–(3.9) satisfies, for every `t ≥ 2`,
`f(x_t) − f(x∗) ≤ 2βR²/(t + 1)`. -/
theorem theorem_3_8 {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 = 2 / ((s : ℝ) + 1))
(x y : ℕ → E) (hrun : IsFrankWolfeRun X f' γ x y)
(t : ℕ) (ht : 2 ≤ t) :
f (x t) - f xstar ≤ 2 * β * Metric.diam X ^ 2 / ((t : ℝ) + 1) := by sorry
end ConvexOptAlg.FrankWolfe
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.