(2.13) —
ProvedNesterovRCD.Sublinear.expected_decreasecoordinate-descentp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1randomized-algorithms
Let , let satisfy (2.2) with constants on finite-dimensional normed blocks, let , and let be the probabilities (2.5). For an arbitrary choice of the vectors , every point satisfies
The left side is the expected decrease of one iteration of RCDM at ; the right side expresses it through the full gradient in the dual weighted norm.
Formalization Note The statement is pointwise in , which is how the paper uses it for the random iterate . is explicit (for the probabilities are ). Convexity is not needed.
Preamble
import Mathlib import Definitions.Def_NesterovRCD_Sublinear_Basic
Formal statement
namespace NesterovRCD.Sublinear
variable {n : ℕ} {E : Fin n → Type*} [∀ i, NormedAddCommGroup (E i)] [∀ i, NormedSpace ℝ (E i)]
[∀ i, FiniteDimensional ℝ (E i)]
theorem expected_decrease (hn : 0 < n) (f : Blocks E → ℝ) (L : Fin n → ℝ) (hL : CoordLipschitz f L)
(sharp : ∀ i, (E i →L[ℝ] ℝ) → E i) (hsharp : IsSharpSelection sharp)
(α : ℝ) (x : Blocks E) :
wdual L (1 - α) (gradBlocks f x) ^ 2 / (2 * S L α)
≤ f x - ∑ i, prob L α i * f (coordStep f L sharp i x) := by sorry
end NesterovRCD.Sublinear
Source
Nesterov, Efficiency of coordinate descent methods on huge-scale optimization problems, CORE Discussion Paper 2010/2, p. 7, proof of Theorem 1, (2.13)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.