Theorem 6 (5.3) — ACDM:
ProvedNesterovRCD.Accelerated.theorem6Let , with blocks, each carrying a Euclidean norm (3.4), and let be the norm (3.5), . Assume:
- has a coordinate-wise Lipschitz gradient (2.2) with constants ;
- is strongly convex (3.1) in with a known parameter , ( meaning convexity);
- is a minimizer of and ;
- is any selection of (1.8) on each block.
Let ACDM (5.1) run with independent uniform draws, , and
Then for every :
- if ,
- in all cases (),
The accelerated scheme thus improves the expected rate of the plain random coordinate descent method to , and for the first bound decreases geometrically, asymptotically by the factor per iteration.
Formalization Note The paper states (5.3) as one chain for every . At the middle expression is , which the paper reads as its limit , while Lean evaluates it to ; so the chain is stated for , and the outer bound separately for all . The standing assumptions of §2 (convexity, a nonempty optimal set, , ), the Euclidean block norms and (implicit in (5.1), whose divides by ) are explicit hypotheses; is any valid convexity parameter. Blocks are inner-product spaces E i indexed by Fin n; the draws are explicit sequences and is the finite average acdmPhi over all draw sequences with weight .
Retired 2026-10-27: a Lean-vs-paper fidelity audit found this statement weaker than, or narrower than, the cited result. A corrected statement will be resubmitted.
import Mathlib import Definitions.Def_NesterovRCD_HighProb_Basic import Definitions.Def_NesterovRCD_Accelerated_ACDM
namespace NesterovRCD.Accelerated
theorem theorem6 {n : ℕ} {E : Fin n → Type*} [∀ i, NormedAddCommGroup (E i)]
[∀ i, InnerProductSpace ℝ (E i)] [∀ i, FiniteDimensional ℝ (E i)] (hn : 0 < n)
(f : NesterovRCD.Sublinear.Blocks E → ℝ) (L : Fin n → ℝ) (hL : NesterovRCD.Sublinear.CoordLipschitz f L)
(σ : ℝ) (hσ0 : 0 ≤ σ) (hσn : σ < (n : ℝ) ^ 2) (hsc : NesterovRCD.HighProb.StronglyConvexW f L 1 σ)
(sharp : ∀ i, (E i →L[ℝ] ℝ) → E i) (hsharp : NesterovRCD.Sublinear.IsSharpSelection sharp)
(x0 xs : NesterovRCD.Sublinear.Blocks E) (hxs : NesterovRCD.Sublinear.IsMinimizer f xs) (k : ℕ) :
(0 < σ →
acdmPhi f L sharp σ x0 k - f xs
≤ σ * (2 * NesterovRCD.Sublinear.wnorm L 1 (x0 - xs) ^ 2 + 1 / (n : ℝ) ^ 2 * (f x0 - f xs))
/ ((1 + Real.sqrt σ / (2 * n)) ^ (k + 1) - (1 - Real.sqrt σ / (2 * n)) ^ (k + 1)) ^ 2 ∧
σ * (2 * NesterovRCD.Sublinear.wnorm L 1 (x0 - xs) ^ 2 + 1 / (n : ℝ) ^ 2 * (f x0 - f xs))
/ ((1 + Real.sqrt σ / (2 * n)) ^ (k + 1) - (1 - Real.sqrt σ / (2 * n)) ^ (k + 1)) ^ 2
≤ ((n : ℝ) / (k + 1)) ^ 2 * (2 * NesterovRCD.Sublinear.wnorm L 1 (x0 - xs) ^ 2 + 1 / (n : ℝ) ^ 2 * (f x0 - f xs))) ∧
acdmPhi f L sharp σ x0 k - f xs
≤ ((n : ℝ) / (k + 1)) ^ 2 * (2 * NesterovRCD.Sublinear.wnorm L 1 (x0 - xs) ^ 2 + 1 / (n : ℝ) ^ 2 * (f x0 - f xs)) := by sorry
end NesterovRCD.Accelerated
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.