Theorem 7, item 3, (6.3) —
ProvedNesterovRCD.Adaptive.theorem7_countLet be differentiable with coordinate-wise Lipschitz partial derivatives (2.2) with constants , and let the initial estimates satisfy . Run RACDM (6.1) from any along any sequence of drawn coordinates , and let be the total number of computations of directional derivatives in iterations : iteration , which performs doublings in its loop, computes at trial points. Then
This is item 3 of Theorem 7: on average the adaptive method costs about two directional derivatives per iteration, plus a one-time overhead logarithmic in the ratio of the true constants to the initial guesses.
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 count per iteration, , is the one fixed by the paper's proof (", in other words "): it counts the evaluations of at the trial points and not the evaluation of ; counting that one too would give . The statement holds for every sequence of draws. The standing convexity of and the existence of a minimizer are not used and not assumed. is Real.logb 2, applied to .
import Mathlib import Definitions.Def_ConvexOptAlg_CoordDescent_Defs import Definitions.Def_NesterovRCD_Adaptive_RACDM
namespace NesterovRCD.Adaptive
open ConvexOptAlg.CoordDescent
/-- Theorem 7, item 3, (6.3), p. 18: after iteration `k` (iterations `0, …, k`, draws `idx`),
the total number `N_k` of computations of directional derivatives in RACDM (6.1) satisfies
`N_k ≤ 2(k + 1) + Σ_i log₂(L_i / L⁰_i)`. -/
theorem theorem7_count {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 + 1) → Fin n) :
(numDerivs g L0 x0 k idx : ℝ) ≤ 2 * (k + 1) + ∑ i, Real.logb 2 (L i / L0 i) := by sorry
end NesterovRCD.Adaptive
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.