(6.4) — the doubling loop of RACDM terminates with
ProvedNesterovRCD.Adaptive.eq_6_4Let be differentiable with coordinate-wise Lipschitz partial derivatives (2.2): for every , and ,
Fix a point , a coordinate and an estimate with . Then the doubling loop of RACDM (6.1) started at , , terminates: some satisfies . Moreover the accepted estimate satisfies
where is the number of doublings (the least such ).
This is the bound (6.4) of the proof of Theorem 7: once the estimate exceeds the sign test is passed, so the loop never overshoots by more than a factor . It gives both that the method is well defined and the factor that enters the decrease bound .
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 states (6.4) for "the internal cycle" with the entry assumption ; we state it for an arbitrary entry point , coordinate and entry estimate (positivity is implicit in the paper: the method divides by ). Every intermediate estimate , , is at most the accepted one, so the bound on the accepted one is the bound "during the internal cycle". Convexity is not needed and not assumed.
import Mathlib import Definitions.Def_ConvexOptAlg_CoordDescent_Defs import Definitions.Def_NesterovRCD_Adaptive_RACDM
namespace NesterovRCD.Adaptive
open ConvexOptAlg.CoordDescent
/-- (6.4), p. 18: if the inner cycle of RACDM (6.1) is entered on coordinate `i` at `x` with an
estimate `0 < ℓ ≤ L_i`, the cycle terminates, and the accepted estimate `2^d ℓ` satisfies
`L̂_i ≤ 2 L_i`. -/
theorem eq_6_4 {n : ℕ} (f : Vec n → ℝ) (g : Vec n → Vec n) (L : Fin n → ℝ)
(hL : IsCoordSmooth f g L) (x : Vec n) (i : Fin n) (ℓ : ℝ) (hℓ : 0 < ℓ) (hℓL : ℓ ≤ L i) :
(∃ d : ℕ, ¬ (g x i * g (trial g x i (2 ^ d * ℓ)) i < 0)) ∧
2 ^ doublings g x i ℓ * ℓ ≤ 2 * L i := by sorry
end NesterovRCD.Adaptive
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.