TheoremStatement: Literature-sourcedProof: AI-adaptedPipeline-generatedprecheck passjudge pass (gpt-6-luna)

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Rates for randomized coordinate gradient descent and importance sampling

Statement

Let $f : R^{d} \to R$ be convex and continuously differentiable, with a partition into $n \geq 1$ nonempty blocks and block-gradient Lipschitz constants $L_{i} > 0$ as in Coordinate-block smoothness descent model. Let $M_{i} \geq L_{i}$ , choose probabilities $p_{i} > 0$ with $\sum_{i} p_{i} = 1$ , and set $ρ = \min_{i} p_{i} / M_{i}$ . Assume $f^{*} = \min_{x} f (x)$ is attained at $x^{*}$ and the initial sublevel set has finite radius $R = \sup {∥ x - x^{*} ∥_{2} : f (x) \leq f (x^{0})} < + \infty .$ Run Randomized coordinate gradient descent from the initial point $x^{0}$ with exact updates, no stopping predicate, and finite budget $K \in N$ . For every integer $k$ with $1 \leq k \leq K$ , $E [f (x^{k}) - f^{*}] \leq \frac{2 R^{2}}{ρ k} .$ If, in addition, $f$ is globally $μ$ -strongly convex in the sense that $f (y) \geq f (x) + ⟨ \nabla f (x), y - x ⟩ + \frac{μ}{2} ∥ y - x ∥_{2}^{2} (x, y \in R^{d})$ for some $μ > 0$ , then $E [f (x^{k}) - f^{*}] \leq (1 - μ ρ)^{k} (f (x^{0}) - f^{*}) .$ The strong-convexity factor is in $[0, 1]$ . Uniform sampling with $M_{i} = L_{\max} : = \max_{i} L_{i}$ gives the factor $1 - μ / (n L_{\max})$ and the bound $2 n L_{\max} R^{2} / k$ . For nonuniform sampling, choosing $M_{i} = L_{i}$ and $p_{i} = L_{i} / \sum_{j} L_{j}$ maximizes $\min_{i} p_{i} / M_{i}$ , giving $ρ = 1 / \sum_{i} L_{i}$ ; its constants are not the uniform constants.

Facts & Assumptions

Given: The objective, block partition, smoothness constants, sampling probabilities, and finite-history expectation in the Statement.

[F1]

Randomized coordinate gradient descent: at a selected block $i$ , the update is $x_{i}^{+} = x_{i} - M_{i}^{- 1} \nabla_{i} f (x)$ and the block draw has probability $p_{i}$ .

[F2]

Coordinate-block smoothness descent model: $f (x + U_{i} h) \leq f (x) + ⟨ \nabla_{i} f (x), h ⟩ + (L_{i} / 2) ∥ h ∥_{2}^{2}$ .

[F3]

The Euclidean inner product $⟨ x, y ⟩ = \sum_{k < n} x_{k} y_{k}$ on $R^{n}$ : the product Euclidean norm satisfies $∥ x ∥_{2}^{2} = \sum_{i} ∥ x_{B_{i}} ∥_{2}^{2}$ .

[F4]

Cauchy-Schwarz $∣ ⟨ x, y ⟩ ∣ \leq ∥ x ∥_{2} ∥ y ∥_{2}$ with its equality case, the triangle inequality for $∥ \cdot ∥_{2}$ , the parallelogram law and polarisation: $∣ ⟨ u, v ⟩ ∣ \leq ∥ u ∥_{2} ∥ v ∥_{2}$ .

[F5]

Differentiable convex functions are characterized by the gradient inequality: convex differentiability gives $f (y) \geq f (x) + ⟨ \nabla f (x), y - x ⟩$ .

[F6]

Fermat's theorem: an interior differentiable local extremum has zero gradient: an unconstrained differentiable local minimizer has zero gradient.

[F7]

Laws of finite sums and finite products: finite weighted sums preserve nonnegativity and obey the ordinary algebraic sum laws.

[F8]

The principle of mathematical induction: a base case and successor implication prove a claim for every natural number.

[A1]

$f$ is convex, continuously differentiable, and satisfies the block-gradient Lipschitz hypotheses stated above.

[A2]

The initial sublevel radius $R$ is finite, the algorithm has no stopping predicate and $k \leq K$ , and every expectation at a fixed $k$ is the finite weighted sum over the $k$ -step index histories, so no infinite product probability space is needed.

[A3]

For the linear rate only, $f$ satisfies the displayed global $μ$ -strong-convexity inequality and has a minimizer.

Proof

1.1A1F1F2algebra

Fix $x$ and a block $i$ . With $h = - \nabla_{i} f (x) / M_{i}$ , [F2] gives $f (x + U_{i} h) \leq f (x) - \frac{1}{M_{i}} ∥ \nabla_{i} f (x) ∥_{2}^{2} + \frac{L_{i}}{2 M_{i}^{2}} ∥ \nabla_{i} f (x) ∥_{2}^{2} \leq f (x) - \frac{1}{2 M_{i}} ∥ \nabla_{i} f (x) ∥_{2}^{2}$ , because $M_{i} \geq L_{i}$ .

1.2A3F2algebra

Under [A3], strong convexity at $x$ and $x^{*}$ gives, for $e = x - x^{*}$ , $f (x) - f^{*} \leq ⟨ \nabla f (x), e ⟩ - (μ / 2) ∥ e ∥_{2}^{2} \leq ∥ \nabla f (x) ∥_{2}^{2} / (2 μ)$ ; the last inequality follows by expanding $0 \leq ∥ \nabla f (x) - μ e ∥_{2}^{2}$ . Hence $∥ \nabla f (x) ∥_{2}^{2} \geq 2 μ δ (x)$ . Also $μ \leq L_{i} \leq M_{i}$ for each block, since the strong-convexity lower model and [F2]'s upper model applied to any nonzero displacement in block $i$ bound the same function difference.

2.1A2F1F7step 1.1algebra

Conditional on the first $k$ draws, the next draw has probabilities $p_{i}$ . By the finite-sum laws [F7], averaging step 1.1 over those finitely many outcomes yields $E [f (x^{k + 1}) ∣ x^{k}] \leq f (x^{k}) - \frac{1}{2} \sum_{i} \frac{p_{i}}{M_{i}} ∥ \nabla_{i} f (x^{k}) ∥_{2}^{2} \leq f (x^{k}) - \frac{ρ}{2} ∥ \nabla f (x^{k}) ∥_{2}^{2}$ . Taking the finite-history expectation gives the same inequality with all terms averaged.

3.1A1A2F3F4F5F7F8step 2.1algebra

Put $δ (x) = f (x) - f^{*}$ . If $R = 0$ , then $x^{0} = x^{*}$ because $x^{0}$ belongs to the initial sublevel set, and [F6] gives $\nabla f (x^{*}) = 0$ ; all later updates leave $x^{*}$ fixed and all gaps vanish. Now suppose $R > 0$ . By [F5], $δ (x) \leq ⟨ \nabla f (x), x - x^{*} ⟩$ . Since every exact step decreases $f$ , each iterate lies in the initial sublevel set; thus [F4] and the definition of $R$ give $δ (x^{k}) \leq R ∥ \nabla f (x^{k}) ∥_{2}$ . For each finite $k$ -step history $ω$ , write $w_{ω}$ for its probability and $z_{ω} = ∥ \nabla f (x_{ω}^{k}) ∥_{2}$ ; the weights are nonnegative and sum to $1$ . With $\overset{ˉ}{z} = \sum_{ω} w_{ω} z_{ω}$ , [F7] gives $0 \leq \sum_{ω} w_{ω} (z_{ω} - \overset{ˉ}{z})^{2} = \sum_{ω} w_{ω} z_{ω}^{2} - {\overset{ˉ}{z}}^{2}$ . Hence $E ∥ \nabla f (x^{k}) ∥_{2}^{2} \geq (E ∥ \nabla f (x^{k}) ∥_{2})^{2} \geq ϕ_{k}^{2} / R^{2}$ . Step 2.1 therefore implies $ϕ_{k + 1} \leq ϕ_{k} - ρ ϕ_{k}^{2} / (2 R^{2})$ .

4.1F6F7step 3.1algebra

If some $ϕ_{j} = 0$ , then $f (x^{j}) = f^{*}$ for every history of positive probability, [F6] gives zero gradient at each such unconstrained minimizer, and all later gaps are zero. Otherwise all $ϕ_{j} > 0$ , and $ϕ_{j + 1} \leq ϕ_{j}$ gives $\frac{1}{ϕ_{j + 1}} - \frac{1}{ϕ_{j}} = \frac{ϕ_{j} - ϕ_{j + 1}}{ϕ_{j} ϕ_{j + 1}} \geq \frac{ϕ_{j} - ϕ_{j + 1}}{ϕ_{j}^{2}} \geq \frac{ρ}{2 R^{2}}$ . Summing for $j = 0, \dots, k - 1$ telescopes by [F7] to $1 / ϕ_{k} \geq k ρ / (2 R^{2})$ , which is the stated $O (1 / k)$ bound.

5.1A2A3F7F8step 2.1step 1.2algebra∎

Substituting step 1.2 in step 2.1 gives $E [δ (x^{k + 1}) ∣ x^{k}] \leq (1 - μ ρ) δ (x^{k})$ . Because $0 < μ \leq M_{i}$ and $p_{i} \leq 1$ , $0 \leq μ ρ \leq 1$ . Taking expectations and using induction [F8] proves the linear bound. For any probabilities, [F7] gives $1 = \sum_{i} p_{i} \geq ρ \sum_{i} M_{i}$ , so $ρ \leq 1 / \sum_{i} M_{i}$ ; equality holds for $p_{i} = M_{i} / \sum_{j} M_{j}$ . Since $M_{i} \geq L_{i}$ , this is at most $1 / \sum_{i} L_{i}$ , attained by $M_{i} = L_{i}$ and $p_{i} = L_{i} / \sum_{j} L_{j}$ . The uniform and importance-sampling specializations follow by substitution.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

52 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Stephen J. Wright, Coordinate Descent Algorithms, Theorem 3.1 and proof (standard reference, not scraped)
Clément Royer, Regularized, Large-Scale and Distributed Optimization, Theorem 3.2.1 (standard reference, not scraped)