Theorem 7, item 2, (6.2) — RACDM satisfies
ProvedNesterovRCD.Adaptive.theorem7_rateLet and let be convex and differentiable with coordinate-wise Lipschitz partial derivatives (2.2) with constants :
Assume attains its minimum . Let be the norm (2.7) with , and let , that is, for every with and every minimizer of . Run RACDM (6.1) with initial estimates and coordinates drawn independently and uniformly from , and let be the expectation over the first draws. Then for every ,
This is item 2 of Theorem 7, the main result of §6.1: a coordinate descent method that only has lower bounds on the coordinate Lipschitz constants, and adjusts them by doubling and halving without computing function values, keeps the rate of RCDM (compare (2.14), ) at the cost of a constant factor.
Formalization Note is EuclideanSpace ℝ (Fin n) (scalar coordinates: the paper sets in §6.1), coordinates are indexed for the paper's , and the gradient is an explicit map with , as in the published definition ConvexOptAlg_CoordDescent_Defs that this mission reuses (its IsCoordSmooth f g L is (2.2) with one-dimensional blocks and as block norm; it includes differentiability). The expectation is the published rcdExpect L 0 k, a finite sum over all draws weighted by , ; no measure theory is involved. The paper's is not computed: the theorem takes any upper bound of it (when the maximum is finite it is the least such , so the statement is the paper's). The paper's standing assumption " nonempty" is the hypothesis that minimizes ; " bounded" is implied by the existence of . The initial estimates are positive and at most as in the setup of (6.1); is implicit in the paper. Step 3 of (6.1) is read as (a typo in the paper; see the definition).
import Mathlib import Definitions.Def_ConvexOptAlg_CoordDescent_Defs import Definitions.Def_NesterovRCD_Adaptive_RACDM
namespace NesterovRCD.Adaptive
open ConvexOptAlg.CoordDescent
/-- Theorem 7, item 2, (6.2), p. 18: for convex, coordinate-wise smooth `f` with a minimizer
`x*`, initial estimates `L⁰_i ∈ (0, L_i]`, and `R ≥ R_1(x₀)` (every point of the level set
`{f ≤ f(x₀)}` is within `‖·‖_1`-distance `R` of every minimizer), RACDM(x₀) with uniform draws
satisfies `φ_k − f* ≤ 8 n R² / (16 + 3k)` for every `k ≥ 0`, where `φ_k = E f(x_k)`. -/
theorem theorem7_rate {n : ℕ} (hn : 0 < n) (f : Vec n → ℝ) (g : Vec n → Vec n)
(hconv : ConvexOn ℝ Set.univ f) (L : Fin n → ℝ) (hL : IsCoordSmooth f g L)
(L0 : Fin n → ℝ) (hL0 : ∀ i, 0 < L0 i ∧ L0 i ≤ L i) (x0 xs : Vec n)
(hxs : ∀ y, f xs ≤ f y) (R : ℝ)
(hR : ∀ x, f x ≤ f x0 → ∀ ys, (∀ y, f ys ≤ f y) → wnorm L 1 (x - ys) ≤ R) (k : ℕ) :
rcdExpect L 0 k (fun idx => f (racdm g L0 x0 k idx).1) - f xs ≤
8 * n * R ^ 2 / (16 + 3 * k) := by sorry
end NesterovRCD.Adaptive
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.