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.

Strongly convex smooth-part proximal coordinate contraction

Statement

For a finite horizon $k$ , choose an algorithm budget $K \geq k$ and do not request a proximal-gradient stopping tolerance, so all $k$ updates are executed.

Let $F (x) = f (x) + g (x)$ on a finite-dimensional block product $R^{d}$ , where $f$ is convex, continuously differentiable, and globally $μ$ -strongly convex for some $μ > 0$ , and $g (x) = \sum_{i = 1}^{n} g_{i} (x_{B_{i}})$ with each $g_{i}$ proper, closed and convex. Let $B_{1}, \dots, B_{n}$ partition the coordinates into nonempty blocks. Suppose each block gradient is $L_{i}$ -Lipschitz and set $L_{\max} = \max_{i} L_{i}$ . Start from a finite point $x^{0}$ with $F (x^{0}) < + \infty$ . Run Randomized proximal coordinate descent with certified inner solves with uniform independent block sampling and common majorizer $M_{i} = L_{\max}$ . For any finite horizon $k$ , assume each of its first $k$ subproblem calls returns an accepted certificate with model error at most $ϵ_{j} \geq 0$ at update $j$ ; exact updates have $ϵ_{j} = 0$ . Then $F$ has a unique minimizer $x^{*}$ , $μ \leq L_{\max}$ , and for $q = 1 - μ / (n L_{\max})$ , $E [F (x^{k}) - F (x^{*})] \leq q^{k} (F (x^{0}) - F (x^{*})) + \sum_{j = 0}^{k - 1} q^{k - 1 - j} ϵ_{j} .$ The expectation is the finite weighted sum over the $k$ -step block histories, with the power convention $q^{0} = 1$ . In particular, exact updates contract the expected gap by the factor $q$ . Curvature of $F$ supplied only by the nonsmooth penalties is not covered.

Facts & Assumptions

Given: The finite block product, $f, g_{i}, L_{i}, μ$ , a finite-valued initial point, uniform independent sampling, and certified model errors from the Statement.

[F1]

Randomized proximal coordinate descent with certified inner solves: the selected block minimizes its quadratic model, or is accepted with certified model gap at most $ϵ_{k}$ ; other blocks stay fixed.

[F2]

Coordinate proximal subproblems are attained uniquely and descend: every exact block model has a unique minimizer and an accepted error- $ϵ_{k}$ update raises $F$ by at most $ϵ_{k}$ .

[F3]

Coordinate-block smoothness descent model: the smooth term obeys the block quadratic upper model with constant $L_{i} \leq L_{\max}$ .

[F4]

Finite separable block penalties are proper, closed, and convex: the finite separable sum $g$ is proper, closed and convex; its proof uses only closed sublevels of the block epigraphs and finite products of neighborhoods.

[F5]

A proper closed convex function has an affine minorant: a proper closed convex function on a finite-dimensional Euclidean space has an affine minorant.

[F6]

A finite continuous convex summand preserves proper closed convexity: adding finite continuous convex $f$ to $g$ preserves properness, closedness and convexity.

[F7]

Heine-Borel in $R^{n}$ : with the Euclidean metric a subset of $R^{n}$ is compact if and only if it is closed and bounded, and the proof by bisection uses no choice principle; the same holds on the real line: closed bounded subsets of finite-dimensional Euclidean space are compact.

[F8]

Semicontinuous extreme value theorem on compact Euclidean sets: a real-valued lower-semicontinuous function on a nonempty compact Euclidean set attains its minimum.

[F9]

Continuously differentiable maps, local inverses, and local diffeomorphisms and Total differentiability gives a local $O (∥ h ∥_{2})$ increment bound and therefore continuity: the $C^{1}$ smooth term is continuous, as required by [F6].

[F10]

The principle of mathematical induction: a recurrence bound holding at zero and preserved at successors holds for every finite horizon.

[F11]

Laws of finite sums and finite products: finite weighted sums obey additivity and scaling for averaging over block choices and histories.

[A1]

$f (y) \geq f (x) + ⟨ \nabla f (x), y - x ⟩ + \frac{μ}{2} ∥ y - x ∥_{2}^{2}$ for all $x, y$ .

[A2]

$M_{i} = L_{\max}$ for every block, $L_{i} \leq L_{\max}$ , and each block is drawn independently and uniformly at every accepted update.

[A3]

Each finite-horizon expectation is the sum over the finite product distribution on block histories.

[A4]

All update calls through the stated horizon return accepted certificates; if an inner call fails, the conclusion is asserted only for the accepted prefix before failure.

Proof

1.1A1F4F5F6F7F8F9givenalgebrachoose

By [F4], $g$ is proper closed convex, so choose $\overset{ˉ}{x} \in dom g$ . By [F5], $g (x) \geq ⟨ a, x ⟩ + b$ for some $a, b$ . Strong convexity at $0$ yields $f (x) \geq f (0) + ⟨ \nabla f (0), x ⟩ + \frac{μ}{2} ∥ x ∥_{2}^{2}$ , so $F$ is coercive. By [F9], $f$ is continuous, so [F6] gives the closed epigraph of $F$ ; the map $x \mapsto (x, F (\overset{ˉ}{x}))$ is continuous, so $S = {x : F (x) \leq F (\overset{ˉ}{x})}$ is its closed preimage. Coercivity makes $S$ bounded, and [F7] makes it compact. It is nonempty and finite-valued, so [F8] gives a global minimizer. If two distinct minimizers existed, strong convexity of $f$ at their midpoint and convexity of $g$ would make $F$ there strictly less than the minimum, a contradiction; thus the minimizer is unique.

1.2A1F3givenalgebra

For any block $i$ and nonzero block displacement $h$ , the strong-convexity lower model at $x$ and [F3]'s upper model for $x + U_{i} h$ share the same linear term. Comparing them gives $μ ∥ h ∥_{2}^{2} / 2 \leq L_{i} ∥ h ∥_{2}^{2} / 2$ , so $μ \leq L_{i} \leq L_{\max}$ . Therefore $α = μ / L_{\max}$ lies in $(0, 1]$ and $q = 1 - α / n$ lies in $[0, 1)$ .

1.3A2F1F2F3F11givenalgebra

Fix a current finite point $x$ and let $z_{i}$ minimize $u \mapsto ⟨ \nabla_{i} f (x), u - x_{i} ⟩ + (L_{\max} / 2) ∥ u - x_{i} ∥_{2}^{2} + g_{i} (u)$ ; [F1]--[F2] give existence. Let $z = (z_{i})_{i}$ and $H_{x} (w) = f (x) + ⟨ \nabla f (x), w - x ⟩ + (L_{\max} / 2) ∥ w - x ∥_{2}^{2} + g (w)$ . This separates over blocks, so $z$ minimizes $H_{x}$ . For any block candidate $v$ , [F3] and $L_{i} \leq L_{\max}$ give $F (x + U_{i} (v - x_{i})) \leq F (x) + q_{i}^{k} (v) - q_{i}^{k} (x_{i})$ . The accepted certificate [F1] gives $q_{i}^{k} (x_{i}^{k + 1}) \leq q_{i}^{k} (z_{i}) + ϵ_{k}$ and $q_{i}^{k} (x_{i}) = g_{i} (x_{i})$ , so $F (x^{k + 1}) \leq F (x) + Δ_{i} + ϵ_{k}$ , where $Δ_{i} = q_{i}^{k} (z_{i}) - q_{i}^{k} (x_{i})$ . Summing $Δ_{i}$ over $i$ gives $H_{x} (z) - F (x)$ . By [F11], uniform averaging yields $E [F (x^{k + 1}) ∣ x^{k} = x] \leq (1 - 1 / n) F (x) + H_{x} (z) / n + ϵ_{k}$ .

2.1A1F4step 1.1step 1.2step 1.3algebra

Let $x^{*}$ be the minimizer from step 1.1 and $w = (1 - α) x + α x^{*}$ . Convexity of $g$ gives $g (w) \leq (1 - α) g (x) + α g (x^{*})$ . Strong convexity in [A1] gives $f (x) + α ⟨ \nabla f (x), x^{*} - x ⟩ \leq (1 - α) f (x) + α f (x^{*}) - (α μ / 2) ∥ x - x^{*} ∥_{2}^{2}$ . The quadratic term in $H_{x} (w)$ is $L_{\max} α^{2} ∥ x - x^{*} ∥_{2}^{2} / 2$ ; since $α = μ / L_{\max}$ , it cancels the negative term. Hence $H_{x} (z) \leq H_{x} (w) \leq (1 - α) F (x) + α F (x^{*})$ .

3.1A3A4F11step 1.3step 2.1algebra

By [A4], substitution of step 2.1 into step 1.3 gives, conditionally on the history, $E [F (x^{k + 1}) - F (x^{*}) ∣ x^{k}] \leq q (F (x^{k}) - F (x^{*})) + ϵ_{k}$ . By [F11] and [A3], taking the finite-history expectation yields $ϕ_{k + 1} \leq q ϕ_{k} + ϵ_{k}$ , where $ϕ_{k} = E [F (x^{k}) - F (x^{*})]$ .

4.1F10step 1.2step 3.1algebra∎

Iterating the scalar recurrence gives $ϕ_{1} \leq q ϕ_{0} + ϵ_{0}$ ; if $ϕ_{k} \leq q^{k} ϕ_{0} + \sum_{j < k} q^{k - 1 - j} ϵ_{j}$ , then multiplying by $q \geq 0$ and adding $ϵ_{k}$ proves the formula at $k + 1$ . [F10] induction over $k$ establishes the displayed bound.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

78 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, §3.7, Theorem 3.4 and complete proof (standard reference, not scraped)
P. Tseng, Convergence of a Block Coordinate Descent Method for Nondifferentiable Minimization, §5 (standard reference, not scraped)