Theorem 6.8, p. 341 — RCD(γ) on an α-strongly convex coordinate-smooth f satisfies E f(x_{t+1}) − f(x*) ≤ (1 − 1/κ_γ)^t (f(x₁) − f(x*))
ProvedConvexOptAlg.CoordDescent.theorem_6_8Let and . Let and , and let be differentiable and such that
- is -strongly convex w.r.t. : for all ;
- for every and , is -smooth, i.e. .
Let be the minimizer of and . Run RCD(γ) from : with drawn independently from . Then for every ,
Random coordinate descent therefore converges linearly on strongly convex, coordinate-wise smooth functions, with a rate governed by the sum of the coordinate smoothness constants rather than the global smoothness constant; recovers sampling proportional to .
Formalization Note is EuclideanSpace ℝ (Fin n) and the gradient is an explicit map with HasGradientAt f (g x) x. The expectation over is the finite sum . The side conditions , , are added (they make , and the step meaningful); is any minimizer (the book's standing assumption; uniqueness, assumed "for sake of notation", is not used). Convexity and differentiability, standing assumptions of §6.4, follow from the hypotheses. The book's is not assumed; it follows from the two hypotheses.
import Mathlib import Definitions.Def_ConvexOptAlg_CoordDescent_Defs
namespace ConvexOptAlg.CoordDescent
/-- Theorem 6.8 (Bubeck, arXiv:1405.4980v2, p. 341): let `γ ≥ 0`, let `f : ℝⁿ → ℝ` be α-strongly convex
with respect to `‖·‖_[1−γ]` and such that `u ↦ f(x + u eᵢ)` is βᵢ-smooth for every `i ∈ [n]`,
`x ∈ ℝⁿ`, and let `κ_γ = Σᵢ βᵢ^γ / α`. Then RCD(γ) started at `x₁` satisfies, for every `t ≥ 0`,
`E f(x_{t+1}) − f(x*) ≤ (1 − 1/κ_γ)^t (f(x₁) − f(x*))`, the expectation being over the coordinates
`i₁, …, i_t` drawn independently from `p_γ`. Side conditions: `n ≥ 1`, `α > 0`, `βᵢ > 0`; `x*` is the
minimizer (standing assumption). -/
theorem theorem_6_8 {n : ℕ} (hn : 0 < n) (f : EuclideanSpace ℝ (Fin n) → ℝ)
(g : EuclideanSpace ℝ (Fin n) → EuclideanSpace ℝ (Fin n)) (β : Fin n → ℝ) (γ α : ℝ)
(hγ : 0 ≤ γ) (hβ : ∀ i, 0 < β i) (hα : 0 < α)
(hsc : IsStronglyConvexWNorm f g β (1 - γ) α) (hsm : IsCoordSmooth f g β)
(xstar : EuclideanSpace ℝ (Fin n)) (hmin : ∀ y, f xstar ≤ f y)
(x₁ : EuclideanSpace ℝ (Fin n)) (t : ℕ) :
rcdExpect β γ t (fun idx => f (rcdIter β g x₁ t idx)) - f xstar ≤
(1 - 1 / kappa β γ α) ^ t * (f x₁ - f xstar) := by sorry
end ConvexOptAlg.CoordDescent
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.