Theorem 7, item 1 — at the beginning of each iteration of RACDM
ProvedNesterovRCD.Adaptive.theorem7_boundLet be differentiable with coordinate-wise Lipschitz partial derivatives (2.2) with constants , and let the initial estimates satisfy for every . Run RACDM (6.1) from any along any sequence of drawn coordinates . Then at the beginning of iteration every estimate satisfies
This is item 1 of Theorem 7. It says that the halving in step 3 restores the invariant " is a lower bound of ", so the doubling loop is always entered under the hypothesis of (6.4); it also supplies the bound used to count the derivative evaluations in item 3.
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 statement holds for every sequence of draws, hence at every iteration of every realization. Positivity of is implicit in the paper (the method divides by ) and is part of the conclusion. Step 3 is read as (the printed is a typo; see the definition). The standing convexity of and the existence of a minimizer are not used and not assumed.
import Mathlib import Definitions.Def_ConvexOptAlg_CoordDescent_Defs import Definitions.Def_NesterovRCD_Adaptive_RACDM
namespace NesterovRCD.Adaptive
open ConvexOptAlg.CoordDescent
/-- Theorem 7, item 1, p. 18: at the beginning of each iteration of RACDM (6.1), every estimate
satisfies `0 < L̂_i ≤ L_i`. -/
theorem theorem7_bound {n : ℕ} (f : Vec n → ℝ) (g : Vec n → Vec n) (L : Fin n → ℝ)
(hL : IsCoordSmooth f g L) (L0 : Fin n → ℝ) (hL0 : ∀ i, 0 < L0 i ∧ L0 i ≤ L i)
(x0 : Vec n) (k : ℕ) (idx : Fin k → Fin n) (i : Fin n) :
0 < (racdm g L0 x0 k idx).2 i ∧ (racdm g L0 x0 k idx).2 i ≤ L i := by sorry
end NesterovRCD.Adaptive
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.