Theorem 1 — RCDM:
ProvedNesterovRCD.Sublinear.theorem1Let with blocks, each carrying a norm . Let be convex and differentiable, with coordinate-wise Lipschitz continuous gradient (2.2) with constants , and let be a minimizer of , . Fix and a starting point , and let , where
Run the random coordinate descent method RCDM: at step draw independently with and set , where is any vector of . Then the expected value satisfies, for every ,
This is the paper's first global efficiency estimate: random coordinate descent converges in expectation at the rate , with a constant governed by the sum of powers of the coordinate Lipschitz constants rather than by the global Lipschitz constant. For (uniform sampling) it gives , and for it gives .
Formalization Note The paper states the bound with itself; we state it for every upper bound of , which is equivalent whenever the max is finite (the paper assumes bounded) and avoids a junk value of a supremum. The standing assumptions of §2 (p. 4: convex and differentiable, nonempty) are hypotheses; and are implicit in the paper (the method divides by and samples from ) and stated explicitly. ranges over all of as in (2.5). The blocks are Fin n with 0-based indices, each a finite-dimensional real normed space; the dual norm is the operator norm; the choice of is arbitrary (IsSharpSelection); is the finite sum over all index sequences of length weighted by the product of their probabilities.
import Mathlib import Definitions.Def_NesterovRCD_Sublinear_Basic
namespace NesterovRCD.Sublinear
variable {n : ℕ} {E : Fin n → Type*} [∀ i, NormedAddCommGroup (E i)] [∀ i, NormedSpace ℝ (E i)]
[∀ i, FiniteDimensional ℝ (E i)]
theorem theorem1 (hn : 0 < n) (f : Blocks E → ℝ) (hconv : ConvexOn ℝ Set.univ f)
(L : Fin n → ℝ) (hL : CoordLipschitz f L)
(sharp : ∀ i, (E i →L[ℝ] ℝ) → E i) (hsharp : IsSharpSelection sharp)
(α : ℝ) (x0 xs : Blocks E) (hxs : IsMinimizer f xs)
(R : ℝ) (hR : LevelRadiusLE f L (1 - α) x0 R) (k : ℕ) :
expect (prob L α) k (fun idx => f (rcdm f L sharp x0 k idx)) - f xs
≤ 2 / ((k : ℝ) + 4) * S L α * R ^ 2 := by sorry
end NesterovRCD.Sublinear
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.