Theorem 4, (3.11) — RCDM on , :
ProvedNesterovRCD.HighProb.theorem4Let with blocks carrying Euclidean norms (3.4), and (3.9). Let be convex with coordinate-wise Lipschitz gradient, constants (2.2), and . Let be a minimizer, , and let bound the size of the initial level set in :
that is, . Fix the accuracy and the confidence level , define and the regularized objective , and choose with
Let be generated by RCDM as applied to : block is drawn with probability , independently at each step, and , with any choice of the vectors of (1.8). Then
A single run of randomized coordinate descent on the regularized problem therefore returns an -solution of the original problem with high probability, after a number of iterations that depends only logarithmically on the confidence level.
Formalization Note The paper takes ; here is any positive upper bound of and is defined from it. The proof uses only through on the level set, so the paper's statement is the case ; excludes , where the paper's is undefined. Explicit hypotheses: , , convex, existence of a minimizer (standing assumptions of §2). The event concerns and of the original problem, while comes from the run on with 's constants (step and sampling). The probability is the finite sum over draw sequences; blocks are Fin n, 0-based; Euclidean blocks are inner-product spaces .
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 open Classical
namespace NesterovRCD.HighProb
variable {n : ℕ} {E : Fin n → Type*} [∀ i, NormedAddCommGroup (E i)] [∀ i, InnerProductSpace ℝ (E i)]
[∀ i, FiniteDimensional ℝ (E i)]
theorem theorem4 (hn : 0 < n) (f : NesterovRCD.Sublinear.Blocks E → ℝ) (hconv : ConvexOn ℝ Set.univ f)
(L : Fin n → ℝ) (hL : NesterovRCD.Sublinear.CoordLipschitz f L)
(sharp : ∀ i, (E i →L[ℝ] ℝ) → E i) (hsharp : NesterovRCD.Sublinear.IsSharpSelection sharp)
(x0 xs : NesterovRCD.Sublinear.Blocks E) (hxs : NesterovRCD.Sublinear.IsMinimizer f xs)
(R : ℝ) (hRpos : 0 < R) (hR : NesterovRCD.Sublinear.LevelRadiusLE f L 0 x0 R)
(ε β : ℝ) (hε : 0 < ε) (hβ0 : 0 < β) (hβ1 : β < 1)
(μ : ℝ) (hμ : μ = ε / (4 * R ^ 2)) (k : ℕ)
(hk : 2 * ((n : ℝ) + 4 * NesterovRCD.Sublinear.S L 1 * R ^ 2 / ε) *
(Real.log (1 / (1 - β)) + Real.log (1 / 2 + 2 * NesterovRCD.Sublinear.S L 1 * R ^ 2 / ε)) ≤ k) :
β ≤ NesterovRCD.Sublinear.expect (NesterovRCD.Sublinear.prob (fun i => L i + μ) 1) k
(fun idx => if f (NesterovRCD.Sublinear.rcdm (fReg f L μ x0) (fun i => L i + μ) sharp x0 k idx) - f xs ≤ ε
then 1 else 0) := by sorry
end NesterovRCD.HighProb
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.