Proof of Theorem 7 — one RACDM iteration decreases by at least
ProvedNesterovRCD.Adaptive.step_decreaseLet be convex and differentiable with coordinate-wise Lipschitz partial derivatives (2.2) with constants . Let , let be a vector of estimates, and let be a coordinate with . If is the point produced by one iteration of RACDM (6.1) on coordinate from the state (doubling loop, then the step with the accepted estimate), then
This is the one-step decrease in the proof of Theorem 7 (p. 19). It replaces the bound of (2.4) for the step with the known constant ; the factor instead of is the price of not knowing .
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 paper derives the bound from inequality (2.1.17) of Nesterov's Introductory Lectures, which needs the convexity of along the coordinate line; convexity of is the paper's standing assumption (2.1) and is a hypothesis here. In the paper the entry condition comes from item 1; here it is a hypothesis on an arbitrary state, together with (implicit in the paper).
import Mathlib import Definitions.Def_ConvexOptAlg_CoordDescent_Defs import Definitions.Def_NesterovRCD_Adaptive_RACDM
namespace NesterovRCD.Adaptive
open ConvexOptAlg.CoordDescent
/-- Proof of Theorem 7, p. 19: for convex `f`, one iteration of RACDM (6.1) on coordinate `i`
from `(x, L̂)` with `0 < L̂_i ≤ L_i` decreases `f` by at least `3 (∇_i f(x))² / (8 L_i)`. -/
theorem step_decrease {n : ℕ} (f : Vec n → ℝ) (g : Vec n → Vec n)
(hconv : ConvexOn ℝ Set.univ f) (L : Fin n → ℝ) (hL : IsCoordSmooth f g L)
(x : Vec n) (Lh : Fin n → ℝ) (i : Fin n) (hpos : 0 < Lh i) (hle : Lh i ≤ L i) :
3 / (8 * L i) * g x i ^ 2 ≤ f x - f (racdmStep g (x, Lh) i).1 := by sorry
end NesterovRCD.Adaptive
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.