Proof of Theorem 7 —
ProvedNesterovRCD.Adaptive.expected_decreaseLet and let be convex and differentiable with coordinate-wise Lipschitz partial derivatives (2.2) with constants . Write
for the dual norm of (2.7) with . Let and let the estimates satisfy for every . Draw the coordinate uniformly from (the counter ) and let be the point produced by one iteration of RACDM (6.1) on coordinate from the state . Then
This is the expected decrease of one RACDM iteration (p. 19), the analogue of (2.13) for the adaptive method; it is the inequality from which the rate (6.2) follows by the argument of Theorem 1.
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 uniform probabilities are the published pGamma L 0 i . The norm is the published wnormDual L 1. The hypotheses for all are what item 1 of Theorem 7 provides at the beginning of each iteration; is implicit in the paper (for there are no coordinates to draw).
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` and estimates `0 < L̂_i ≤ L_i`, one iteration of
RACDM (6.1) with the coordinate drawn uniformly (the counter `R_0`, `p_0(i) = 1/n`) satisfies
`f(x) − E_i f(x⁺) ≥ 3 (‖∇f(x)‖*_1)² / (8n)`. -/
theorem expected_decrease {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)
(x : Vec n) (Lh : Fin n → ℝ) (hLh : ∀ i, 0 < Lh i ∧ Lh i ≤ L i) :
3 / (8 * n) * wnormDual L 1 (g x) ^ 2 ≤
f x - ∑ i, pGamma L 0 i * 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.