Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

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*))

Proved
ConvexOptAlg.CoordDescent.theorem_6_8

by mikedeng1 · Oct 5, 2026 · Mathlib 0df444a (Lean v4.33.1)

convex-optimizationcoordinate-descentlinear-convergencep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-bookp2o-v1randomized-algorithms

Let n≥1n\ge1n≥1 and γ≥0\gamma\ge0γ≥0. Let β1,…,βn>0\beta_1,\dots,\beta_n>0β1​,…,βn​>0 and α>0\alpha>0α>0, and let f:Rn→Rf:\mathbb R^n\to\mathbb Rf:Rn→R be differentiable and such that

  1. fff is α\alphaα-strongly convex w.r.t. ∥x∥[1−γ]=∑iβi1−γxi2\|x\|_{[1-\gamma]}=\sqrt{\sum_i\beta_i^{1-\gamma}x_i^2}∥x∥[1−γ]​=∑i​βi1−γ​xi2​​: f(x)−f(y)≤∇f(x)⊤(x−y)−α2∥x−y∥[1−γ]2f(x)-f(y)\le\nabla f(x)^\top(x-y)-\frac{\alpha}{2}\|x-y\|_{[1-\gamma]}^2f(x)−f(y)≤∇f(x)⊤(x−y)−2α​∥x−y∥[1−γ]2​ for all x,yx,yx,y;
  2. for every i∈[n]i\in[n]i∈[n] and x∈Rnx\in\mathbb R^nx∈Rn, u↦f(x+uei)u\mapsto f(x+ue_i)u↦f(x+uei​) is βi\beta_iβi​-smooth, i.e. ∣∇if(x+uei)−∇if(x)∣≤βi∣u∣|\nabla_i f(x+ue_i)-\nabla_i f(x)|\le\beta_i|u|∣∇i​f(x+uei​)−∇i​f(x)∣≤βi​∣u∣.

Let x∗x^*x∗ be the minimizer of fff and κγ=∑i=1nβiγ/α\kappa_\gamma=\sum_{i=1}^n\beta_i^\gamma/\alphaκγ​=∑i=1n​βiγ​/α. Run RCD(γ) from x1∈Rnx_1\in\mathbb R^nx1​∈Rn: xs+1=xs−1βis∇isf(xs)eisx_{s+1}=x_s-\frac{1}{\beta_{i_s}}\nabla_{i_s}f(x_s)e_{i_s}xs+1​=xs​−βis​​1​∇is​​f(xs​)eis​​ with i1,i2,…i_1,i_2,\dotsi1​,i2​,… drawn independently from pγ(i)=βiγ/∑jβjγp_\gamma(i)=\beta_i^\gamma/\sum_j\beta_j^\gammapγ​(i)=βiγ​/∑j​βjγ​. Then for every t≥0t\ge0t≥0,

Ef(xt+1)−f(x∗)≤(1−1κγ)t(f(x1)−f(x∗)).\mathbb E f(x_{t+1})-f(x^*)\le\Big(1-\frac{1}{\kappa_\gamma}\Big)^t\big(f(x_1)-f(x^*)\big).Ef(xt+1​)−f(x∗)≤(1−κγ​1​)t(f(x1​)−f(x∗)).

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; γ=1\gamma=1γ=1 recovers sampling proportional to βi\beta_iβi​.

Formalization Note Rn\mathbb R^nRn is EuclideanSpace ℝ (Fin n) and the gradient is an explicit map ggg with HasGradientAt f (g x) x. The expectation over i1,…,iti_1,\dots,i_ti1​,…,it​ is the finite sum ∑(i1,…,it)∏spγ(is) f(xt+1)\sum_{(i_1,\dots,i_t)}\prod_s p_\gamma(i_s)\,f(x_{t+1})∑(i1​,…,it​)​∏s​pγ​(is​)f(xt+1​). The side conditions n≥1n\ge1n≥1, α>0\alpha>0α>0, βi>0\beta_i>0βi​>0 are added (they make pγp_\gammapγ​, κγ\kappa_\gammaκγ​ and the step 1/βi1/\beta_i1/βi​ meaningful); x∗x^*x∗ 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 κγ≥1\kappa_\gamma\ge1κγ​≥1 is not assumed; it follows from the two hypotheses.

Preamble
import Mathlib
import Definitions.Def_ConvexOptAlg_CoordDescent_Defs
Formal statement
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
Source
Bubeck, arXiv:1405.4980v2, Theorem 6.8, p. 341 (setting: §6.4 preamble, p. 338; §6.4.1, p. 339)
Human review
  • Endorsed by Shuze Chen · Oct 6, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 6, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me