Pipeline-generated

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.

✓ 13 results · all verified · 11 also independently AI-judged

Every result on this page is machine-checked by a proof checker and read in full and owner-audited; the judge is an additional, independent cross-model AI review of the proofs. The 2 not AI-judged were verified by owner audit (typically over a confirmed judge false positive), not failures.

Coordinate and block descent methods

1 · Prerequisites

2 · Summary

This page defines randomized coordinate-gradient and proximal updates, cyclic exact block minimization, and the Lasso coordinate formula. It proves finite separable block penalties are proper, closed, and convex by a local neighborhood argument that does not invoke sequential closure. Its smooth-gradient branch proves a finite-horizon expected $O (n L_{\max} R^{2} / k)$ bound and importance-sampling constants; the proximal branch proves well-defined updates and error recurrences both under strong convexity of the composite and, with a sharper factor, of the smooth term. It gives no penalty-independent $R$ -only rate. Cyclic convergence is established only for convex separable composites with compact sublevels and unique continuous block-minimizer maps. A finite closed nonconvex domain shows why arbitrary tie selections need a cycling caveat. The canonical Lasso objective, minimizer existence theorem, and orthogonal-design soft-threshold example remain on the sparse-estimation page.

3 · Logical flowchart

4 · Definitions, theorems and proofs

AlgorithmAlgorithm: Literature-sourcedProof: Not applicablejudge pass (gpt-6-luna)Open item page →

Randomized coordinate gradient descent

Definition

Whenever a subscript $i$ indexes a block, $x_{i}$ is shorthand for $x_{B_{i}}$ .

Let $d, n \geq 1$ , let $B_{1}, \dots, B_{n}$ be a partition of ${1, \dots, d}$ into nonempty blocks, and let $U_{i} : R^{∣ B_{i} ∣} \to R^{d}$ insert a block vector in coordinates $B_{i}$ and put zero in the other coordinates. Coordinate label $j \in {1, \dots, d}$ here denotes standard coordinate $j - 1 \in {0, \dots, d - 1}$ . Let $f : R^{d} \to R$ be convex and continuously differentiable in the sense of Continuously differentiable maps, local inverses, and local diffeomorphisms. Its gradient $\nabla f$ is the one defined by The Jacobian matrix of partial derivatives and the gradient in the scalar-valued case; total differentiability supplies its partial derivatives by A total derivative computes every directional derivative, and its matrix is the Jacobian. Define $\nabla_{i} f (x)$ to be the entries of $\nabla f (x)$ with labels in $B_{i}$ , in increasing order. For each $i$ , an $L_{i}$ block-gradient Lipschitz bound is a number $L_{i} > 0$ such that $∥ \nabla_{i} f (x + U_{i} h) - \nabla_{i} f (x) ∥_{2} \leq L_{i} ∥ h ∥_{2} (x \in R^{d}, h \in R^{∣ B_{i} ∣}),$ Choose majorizers $M_{i} \geq L_{i}$ , probabilities $p_{i} > 0$ with $\sum_{i} p_{i} = 1$ , an initial point $x^{0}$ , and a finite update budget $K \in N$ .

At each update $k < K$ , draw $I_{k} \in {1, \dots, n}$ with probabilities $(p_{i})$ , independently of earlier draws, and set $x_{B_{I_{k}}}^{k + 1} = x_{B_{I_{k}}}^{k} - \frac{1}{M_{I_{k}}} \nabla_{I_{k}} f (x^{k}), x_{B_{j}}^{k + 1} = x_{B_{j}}^{k} (j \neq I_{k}) .$ Uniform sampling means $p_{i} = 1 / n$ . The exact coordinate update is the minimizer of its quadratic model. If the caller supplies a stopping predicate, it is checked after each accepted update; on the first true result the procedure returns the current iterate with status tolerance-met. Otherwise it returns $x^{K}$ with status budget-limit. The latter status does not certify a specified finite objective gap. Every finite horizon uses only a finite product distribution on index histories.

LemmaStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (gpt-6-luna)Open item page →

Coordinate-block smoothness descent model

Statement

Let $f : R^{d} \to R$ be continuously differentiable, let $B_{i}$ be one block of a finite coordinate partition, and let $U_{i}$ be its coordinate insertion map. Suppose $L_{i} > 0$ satisfies $∥ \nabla_{i} f (x + U_{i} h) - \nabla_{i} f (x) ∥_{2} \leq L_{i} ∥ h ∥_{2}$ for every $x, h$ . Then $f (x + U_{i} h) \leq f (x) + ⟨ \nabla_{i} f (x), h ⟩ + \frac{L_{i}}{2} ∥ h ∥_{2}^{2} .$

Facts & Assumptions

Given: The function, block and Lipschitz bound in the Statement.

[F1]

The Euclidean inner product $⟨ x, y ⟩ = \sum_{k < n} x_{k} y_{k}$ on $R^{n}$ , The Jacobian matrix of partial derivatives and the gradient in the scalar-valued case and Laws of finite sums and finite products: identify block label $j \in {1, \dots, d}$ with standard coordinate $j - 1$ and order each block increasingly; then $\nabla_{i} f (x)$ is the corresponding restriction of $\nabla f (x)$ and $⟨ \nabla f (x), U_{i} h ⟩ = ⟨ \nabla_{i} f (x), h ⟩$ by the finite-coordinate definition of the Euclidean inner product and finite-sum splitting.

[F2]

Continuously differentiable maps, local inverses, and local diffeomorphisms: continuously differentiable means totally differentiable at every point, with continuous derivative entries.

[F3]

The chain rule for total derivatives: $D (g \circ f) (a) = D g (f (a)) \circ D f (a)$ : along a differentiable curve, the derivative of the composition is the derivative of the outer function applied to the curve derivative.

[F4]

For a differentiable scalar field, $D_{v} f (a) = ⟨ \nabla f (a), v ⟩$ and the unit direction of steepest ascent is the normalized gradient: for a totally differentiable scalar function, the directional derivative in direction $v$ is $⟨ \nabla f, v ⟩$ .

[F5]

Total differentiability gives a local $O (∥ h ∥_{2})$ increment bound and therefore continuity: a totally differentiable function is continuous at each point.

[F6]

The mean value theorem, as the case $g (x) = x$ of Cauchy's: for $f$ continuous on $[a, b]$ with $a < b$ and differentiable on $(a, b)$ there is $c \in (a, b)$ with $f (b) - f (a) = f^{'} (c) (b - a)$ : if a real function is continuous on a closed interval and differentiable in its interior, its endpoint difference is its derivative at an interior point times the interval length.

[F7]

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}$ .

[F8]

The principle of mathematical induction: an identity that holds at zero and is preserved at successors holds for every natural number.

[F9]

Finite sums and finite products, by recursion and Laws of finite sums and finite products: finite sums satisfy the zero base case, successor recursion, additivity, telescoping, scaling, and the constant-sum law.

[F10]

For every $ε > 0$ in a complete ordered field there is a natural $n \geq 1$ with $1 / n < ε$ : for every $η > 0$ there is an integer $N \geq 1$ with $1 / N < η$ .

[F11]

Every natural-number-indexed list of nonempty sets has a choice function on its family of values: a finite indexed list of nonempty witness sets has a choice function in ZF.

Proof

1.1givenF1F2F3F4F5F7

If $h = 0$ the claim is equality. Otherwise set $ϕ (t) = f (x + t U_{i} h)$ on $[0, 1]$ . By [F2] and [F3], $ϕ$ is totally differentiable at every point of $[0, 1]$ , so [F5] makes it continuous there; [F3] and [F4] give $ϕ^{'} (t) = ⟨ \nabla_{i} f (x + t U_{i} h), h ⟩$ . Hence the Lipschitz hypothesis and [F7] give $∣ ϕ^{'} (t) - ϕ^{'} (0) ∣ \leq L_{i} t ∥ h ∥_{2}^{2}$ .

2.1F6F8F9F11step 1.1algebra

Fix $N \geq 1$ and apply [F6] on each interval $[j / N, (j + 1) / N]$ . Each mean-value witness set is nonempty, so [F11] selects $c_{j} \in (j / N, (j + 1) / N)$ simultaneously for the finite list $j < N$ , with $ϕ ((j + 1) / N) - ϕ (j / N) = ϕ^{'} (c_{j}) / N$ . By [F9], summing and telescoping gives $ϕ (1) - ϕ (0) - ϕ^{'} (0) = \frac{1}{N} \sum_{j < N} (ϕ^{'} (c_{j}) - ϕ^{'} (0)) \leq \frac{L_{i} ∥ h ∥_{2}^{2}}{N^{2}} \sum_{j < N} (j + 1)$ . To evaluate the last sum, set $T_{N} = \sum_{j < N} (j + 1)$ ; [F9] gives $T_{0} = 0$ and $T_{N + 1} = T_{N} + (N + 1)$ , and [F8] proves $T_{N} = N (N + 1) / 2$ by the base case and the algebraic successor identity $N (N + 1) / 2 + (N + 1) = (N + 1) (N + 2) / 2$ . Thus the upper bound is $\frac{L_{i}}{2} (1 + \frac{1}{N}) ∥ h ∥_{2}^{2}$ .

3.1F10step 2.1assume-contraalgebradischarge-contradiction∎

The left side of step 2.1 is independent of $N$ . If it exceeded $L_{i} ∥ h ∥_{2}^{2} / 2$ by $δ > 0$ and $L_{i} ∥ h ∥_{2}^{2} > 0$ , choose $N$ with $1 / N < 2 δ / (L_{i} ∥ h ∥_{2}^{2})$ by [F10]; step 2.1 would then give a strict smaller upper bound, a contradiction. If $L_{i} ∥ h ∥_{2}^{2} = 0$ , step 2.1 already gives the result. Substituting $ϕ (1) - ϕ (0) = f (x + U_{i} h) - f (x)$ and $ϕ^{'} (0) = ⟨ \nabla_{i} f (x), h ⟩$ proves the inequality.

LemmaStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (gpt-6-luna)Open item page →

The one-coordinate absolute-value quadratic minimizer

Statement

Let $a > 0$ , $b \in R$ , and $τ > 0$ . The scalar convex function $q (u) = \frac{a}{2} u^{2} - b u + τ ∣ u ∣ (u \in R)$ has the unique global minimizer $u^{*} = S_{τ} (b) / a$ , where $S_{τ}$ is the soft-threshold map of Soft-thresholding map. At $b = τ$ and $b = - τ$ , the unique minimizer is $0$ .

Facts & Assumptions

Given: The parameters in the Statement.

[F1]

Soft-thresholding map: $S_{τ} (b) = b - τ$ for $b > τ$ , $0$ for $- τ \leq b \leq τ$ , and $b + τ$ for $b < - τ$ .

[F2]

The triangle inequality and Basic properties of the absolute value: absolute value is subadditive and positively homogeneous.

Proof

1.1givenF2algebra

For $0 \leq s \leq 1$ , the square identity $((1 - s) u + s v)^{2} = (1 - s) u^{2} + s v^{2} - s (1 - s) (u - v)^{2}$ and $a > 0$ make the quadratic term convex; [F2] makes the absolute-value term convex, and the linear term is affine. Thus $q$ is convex. On $u \geq 0$ , completing the square gives $q (u) = \frac{a}{2} (u - (b - τ) / a)^{2} - \frac{(b - τ)^{2}}{2 a}$ , so the unique minimizer on that half-line is $u_{+} = \max {(b - τ) / a, 0}$ .

1.2givenalgebra

On $u \leq 0$ , $q (u) = \frac{a}{2} (u - (b + τ) / a)^{2} - \frac{(b + τ)^{2}}{2 a}$ , so the unique minimizer on that half-line is $u_{-} = \min {(b + τ) / a, 0}$ .

2.1F1step 1.1step 1.2algebra∎

If $b > τ$ , then $u_{+} = (b - τ) / a > 0$ and $q (u_{+}) = - \frac{(b - τ)^{2}}{2 a} < 0 = q (0)$ , while the negative-half-line minimum is $0$ ; hence this is the unique global minimizer. If $b < - τ$ , then $u_{-} = (b + τ) / a < 0$ and $q (u_{-}) = - \frac{(b + τ)^{2}}{2 a} < 0 = q (0)$ , while the positive-half-line minimum is $0$ ; hence this is the unique global minimizer. If $- τ \leq b \leq τ$ , then $u_{+} = u_{-} = 0$ , the unique minimizer on each half-line by steps 1.1–1.2. These cases equal $S_{τ} (b) / a$ by [F1], including the two kink values.

Remarks

For the finite sanity case $b = 3$ and $τ = 1$ , the formula gives $S_{1} (3) = 2$ and the minimizer of $\frac{1}{2} u^{2} - 3 u + ∣ u ∣$ is $u = 2$ .

AlgorithmAlgorithm: Literature-sourcedProof: Not applicablejudge pass (gpt-6-luna)Open item page →

Cyclic exact block minimization

Definition

Let $d, n \geq 1$ , let $B_{1}, \dots, B_{n}$ partition the coordinates of $R^{d}$ into nonempty blocks, let $F : R^{d} \to (- \infty, + \infty]$ , and let $x^{0}$ satisfy $F (x^{0}) < + \infty$ . A cyclic exact block-minimization run with sweep budget $K \in N$ processes blocks in the fixed order $1, \dots, n$ for at most $K$ sweeps. At the update of block $i$ , hold all other coordinates at their current values and form $M_{i} (x_{- i}) = \arg \min_{u \in R^{∣ B_{i} ∣}} F (x_{- i}, u) .$ If $M_{i} (x_{- i}) = \emptyset$ , return the last iterate and status block-minimum-failure. Otherwise replace the current block by any member of $M_{i} (x_{- i})$ . If a minimizer is nonunique, the procedure is relation-valued and every member is an admissible choice; the convergence theorem on this page assumes unique continuous block-minimizer maps. After $K$ complete sweeps, return the current iterate and status budget-limit. The finite budget does not certify a stationary point.

TheoremStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (gpt-6-luna)Open item page →

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]

[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.

LemmaStatement: AI-adaptedProof: AI-generatedprecheck passjudge pass (gpt-6-luna)Open item page →

Continuity of the cyclic block-minimum value

Statement

Fix a block $i$ and define $m_{i} (a) = \min_{u} {f (a, u) + g_{i} (u)}$ , where $a$ denotes all other blocks, $f$ is finite and continuous, and $g_{i}$ is proper closed convex. Suppose the minimizer map $T_{i} (a)$ exists, is unique, and is continuous on the parameter set in question. Then $m_{i}$ is continuous there.

Facts & Assumptions

Given: The composite block problem and minimizer map in the Statement.

[F1]

Cyclic exact block minimization: $T_{i} (a)$ is the exact global minimizer of the $i$ th block slice.

[F2]

Proper closed convex extended-real functions on $R^{n}$ : closed epigraph in finite dimensions is the lower-semicontinuity convention for $g_{i}$ .

[A1]

$f$ is continuous and $T_{i}$ is single-valued and continuous on the parameter set.

Proof

1.1A1F2givenalgebra

Fix a parameter $a$ , let $u = T_{i} (a)$ , and put $m_{i} (a) = f (a, u) + g_{i} (u)$ . For $ε > 0$ , set $c = g_{i} (u) - ε / 3$ . The weak sublevel $C_{c} = {v : g_{i} (v) \leq c}$ is closed because $v \mapsto (v, c)$ is a continuous slice of the closed epigraph in [F2]; since $u \notin C_{c}$ , its open complement contains a neighborhood of $u$ on which $g_{i} > c$ . Continuity of $T_{i}$ and $f$ gives a relative neighborhood $V$ of $a$ on which $T_{i} (a^{'})$ lies in that neighborhood and both $f (a^{'}, T_{i} (a^{'}))$ and $f (a^{'}, u)$ differ from $f (a, u)$ by less than $ε / 3$ . Hence $m_{i} (a^{'}) > m_{i} (a) - 2 ε / 3$ .

2.1A1F1step 1.1algebra∎

For each $a^{'} \in V$ , the point $u$ is a competitor, so $m_{i} (a^{'}) \leq f (a^{'}, u) + g_{i} (u) < m_{i} (a) + ε / 3$ . Together with step 1.1, this gives $∣ m_{i} (a^{'}) - m_{i} (a) ∣ < ε$ , which is continuity of $m_{i}$ at the arbitrary parameter $a$ . The argument uses neighborhoods and closed epigraphs directly; it does not infer topological continuity from a sequential criterion.

CounterexampleConstruction: AI-generatedVerification: AI-generatedprecheck passjudge pass (gpt-6-luna)Open item page →

Cyclic exact block minimization can cycle outside the convex separable hypotheses

Statement refuted

The claim that every infinite continuation of the cyclic exact block-minimization update rule for an arbitrary nonconvex, nonseparable extended-real objective converges to one point is false when block minimizers are nonunique and the allowed tie choices vary by update.

Witness

Let $C = {(0, 0), (2, 0), (2, 2), (1, 2), (1, 1), (0, 1)} \subset R^{2}$ and let $F$ be its indicator: $F = 0$ on $C$ and $F = + \infty$ off $C$ . This is a finite, closed but nonconvex, nonseparable domain. Use singleton blocks in the order $x, y$ and start at $(0, 0)$ . Any finite sweep budget follows the corresponding prefix of the periodic tie-selection rule; three sweeps complete one six-update period.

Facts & Assumptions

Given: The objective, blocks and starting point in the Counterexample.

[F1]

Cyclic exact block minimization: at each update the selected coordinate is replaced by any global minimizer of the current coordinate slice.

[F2]

The extended real line $\overline{R} = R \cup {- \infty, + \infty}$ , its order, and the arithmetic that is left undefined: the indicator values $0$ and $+ \infty$ give the extended-real objective and its finite domain.

[F3]

The Euclidean inner product $⟨ x, y ⟩ = \sum_{k < n} x_{k} y_{k}$ on $R^{n}$ and Cauchy-Schwarz $∣ ⟨ x, y ⟩ ∣ \leq ∥ x ∥_{2} ∥ y ∥_{2}$ with its equality case, the triangle inequality for $∥ \cdot ∥_{2}$ , the parallelogram law and polarisation: the Euclidean norm induces the usual metric and satisfies the triangle inequality; Every nonempty finite set of reals has a maximum and a minimum: a nonempty finite set of positive reals has a positive minimum; The metric topology: a set is open when every one of its points has a ball around it inside the set; closed means open complement and Open ball, closed ball and sphere in a metric space: open balls form neighborhoods in which closedness is tested.

Proof

1.1F1F2givenchoose

At $y = 0$ , the feasible $x$ values are $0$ and $2$ , and both minimize the slice with value $0$ ; choose $x = 2$ . At $x = 2$ , the feasible $y$ values are $0$ and $2$ , and both minimize; choose $y = 2$ .

2.1F1F2step 1.1choose

At $y = 2$ , choose $x = 1$ from the two minimizing values $1, 2$ . At $x = 1$ , choose $y = 1$ from the two minimizing values $1, 2$ . At $y = 1$ , choose $x = 0$ from the two minimizing values $0, 1$ . At $x = 0$ , choose $y = 0$ from the two minimizing values $0, 1$ . Thus one six-update cycle returns to $(0, 0)$ , and repeating the same admissible tie choices gives a period-six trajectory.

3.1F1F2F3step 1.1step 2.1algebra

Every point in the trajectory lies in $C$ and has objective $0$ , so every coordinate update described in steps 1.1 and 2.1 is an exact global block minimization. The set $C$ is closed: for any $z \notin C$ , the finitely many distances ${∥ z - c ∥_{2} : c \in C}$ are positive, so [F3] gives a positive minimum $δ$ ; if $∥ w - z ∥_{2} < δ / 2$ , the triangle inequality gives $∥ w - c ∥_{2} \geq ∥ z - c ∥_{2} - ∥ w - z ∥_{2} > δ / 2$ for every $c \in C$ . Thus the open ball of radius $δ / 2$ about $z$ misses $C$ . The set is nonconvex because $(0, 0), (2, 0) \in C$ but their midpoint $(1, 0) \notin C$ . It is not a Cartesian product of its coordinate projections: both projections are ${0, 1, 2}$ , whose product has nine points, whereas $C$ has six. If $F (x, y) = h (x) + k (y)$ for functions $h, k$ taking values in $R \cup {+ \infty}$ , its finite domain consists exactly of pairs where $h$ and $k$ are each finite, hence is a Cartesian product. Thus $F$ is nonseparable.

4.1F1step 1.1step 2.1step 3.1algebra∎

In the infinite continuation of the finite-budget prefixes, the trajectory does not converge: the subsequences at updates $6 m$ and $6 m + 1$ are constantly $(0, 0)$ and $(2, 0)$ , respectively, and those limits differ. Repeating the six admissible choices therefore gives a nonconvergent cyclic exact-minimization trajectory.

Remarks

The example has a nonconvex, nonseparable objective and nonunique block minimizers. It lies outside Cyclic exact block descent has globally optimal accumulation points; the convergence theorem does not assert convergence for this case.

LemmaStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (gpt-6-luna)Open item page →

Exact Lasso coordinate update, including a zero column

Statement

Use the Lasso objective $Q_{y}$ and notation of Lasso estimator for fixed design, with $n, d \geq 1$ and $τ > 0$ . Fix a coordinate $j$ and all other coefficients, and set $r_{j} = y - \sum_{ℓ \neq j} X_{ℓ} θ_{ℓ}$ . If $X_{j} \neq 0$ , the unique minimizing coordinate is $θ_{j}^{+} = \frac{S_{n τ} (X_{j}^{T} r_{j})}{∥ X_{j} ∥_{2}^{2}} .$ If $X_{j} = 0$ , the unique minimizing coordinate is $θ_{j}^{+} = 0$ .

Facts & Assumptions

Given: The fixed-design Lasso objective, a coordinate $j$ , and the other coordinates.

[F1]

Lasso estimator for fixed design: $Q_{y} (θ) = n^{- 1} ∥ y - X θ ∥_{2}^{2} + 2 τ ∥ θ ∥_{1}$ , with $τ > 0$ .

[F2]

The one-coordinate absolute-value quadratic minimizer: for $a > 0$ and $λ > 0$ , $\frac{a}{2} u^{2} - b u + λ ∣ u ∣$ has unique minimizer $S_{λ} (b) / a$ .

[F3]

Soft-thresholding map: $S_{λ} (b) = b - λ$ for $b > λ$ , equals $0$ for $∣ b ∣ \leq λ$ , and equals $b + λ$ for $b < - λ$ .

[F4]

The Euclidean inner product $⟨ x, y ⟩ = \sum_{k < n} x_{k} y_{k}$ on $R^{n}$ : $∥ v ∥_{2}^{2} = ⟨ v, v ⟩$ and the inner product is bilinear; Cauchy-Schwarz $∣ ⟨ x, y ⟩ ∣ \leq ∥ x ∥_{2} ∥ y ∥_{2}$ with its equality case, the triangle inequality for $∥ \cdot ∥_{2}$ , the parallelogram law and polarisation: $∥ v ∥_{2} = 0$ only for $v = 0$ .

[A1]

The residual excluding coordinate $j$ is $r_{j} = y - \sum_{ℓ \neq j} X_{ℓ} θ_{ℓ}$ .

Proof

1.1F1F4A1algebra

For a candidate value $u$ in coordinate $j$ , $y - X θ = r_{j} - X_{j} u$ . By bilinearity in [F4], expanding the square in [F1] shows that the terms depending on $u$ are $n^{- 1} ∥ X_{j} ∥_{2}^{2} u^{2} - 2 n^{- 1} (X_{j}^{T} r_{j}) u + 2 τ ∣ u ∣$ .

2.1F2F3F4step 1.1algebra

If $X_{j} \neq 0$ , [F4] gives $∥ X_{j} ∥_{2}^{2} > 0$ . Multiply these terms by the positive constant $n / 2$ . The result is $\frac{1}{2} ∥ X_{j} ∥_{2}^{2} u^{2} - (X_{j}^{T} r_{j}) u + n τ ∣ u ∣$ . Apply [F2] with $a = ∥ X_{j} ∥_{2}^{2}$ , $b = X_{j}^{T} r_{j}$ , and $λ = n τ > 0$ to obtain the stated unique minimizer; [F3] fixes its threshold convention at both kink values.

3.1F1A1givenalgebra∎

If $X_{j} = 0$ , the squared-residual term in [F1] is independent of $u$ , while the only varying term is $2 τ ∣ u ∣$ . Since $τ > 0$ , this term has the unique minimum at $u = 0$ .

LemmaStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (gpt-6-luna)Open item page →

Finite separable block penalties are proper, closed, and convex

Statement

Let $n \geq 1$ be finite, let $d_{i} \geq 1$ , and let each $g_{i} : R^{d_{i}} \to (- \infty, + \infty]$ be proper, closed, and convex in the epigraph convention of Proper closed convex extended-real functions on $R^{n}$ . On the product $R^{d_{1}} \times \dots \times R^{d_{n}}$ define $g (x) = \sum_{i = 1}^{n} g_{i} (x_{i})$ . Then $g$ is proper, closed, and convex. The proof below uses only finite construction and the closed epigraphs of the separate terms.

Facts & Assumptions

Given: A finite nonempty block list and the functions in the Statement.

[F1]

Proper closed convex extended-real functions on $R^{n}$ : each $g_{i}$ has nonempty effective domain, satisfies the extended-real convexity inequality, and has closed epigraph.

[F2]

The principle of mathematical induction: a property true at the base index and preserved at each successor holds for every natural index in the finite block list.

[A1]

Each block dimension $d_{i}$ is finite and positive, and the index set has size $n \geq 1$ .

Proof

1.1A1F1F2construct

For each $i$ , [F1] gives a point in $dom g_{i}$ . The empty tuple is a choice for the first zero blocks; if a tuple has been constructed for the first $k < n$ blocks, append one point from the nonempty $dom g_{k + 1}$ . Induction [F2] gives a tuple $x$ in all $n$ domains, so $g (x) < + \infty$ and $g$ is proper. Only finitely many choices are made.

1.2F1givenalgebra

If $g (x), g (y) < + \infty$ and $0 \leq θ \leq 1$ , apply the convexity inequality in [F1] to each pair $(x_{i}, y_{i})$ and add the finitely many inequalities. If either endpoint has infinite $g$ value, the extended-real inequality is automatic under the endpoint convention. Thus $g$ is convex.

1.3F1givenalgebra

Fix a block $i$ and a real $c$ . Its weak sublevel $C_{i, c} = {u_{i} : g_{i} (u_{i}) \leq c}$ is closed: the map $u_{i} \mapsto (u_{i}, c)$ preserves Euclidean distances and is continuous, so $C_{i, c}$ is its preimage of the closed set $epi g_{i}$ from [F1]. Therefore, whenever $g_{i} (x_{i}) > c$ , the open complement of $C_{i, c}$ is a neighborhood of $x_{i}$ throughout which $g_{i} > c$ .

2.1A1step 1.3givenalgebra

Take any $(x, t) \notin epi g$ . If all $g_{i} (x_{i})$ are finite, put $s = \sum_{i} g_{i} (x_{i}) > t$ and $c_{i} = g_{i} (x_{i}) - (s - t) / (2 n)$ . By step 1.3, each $x_{i}$ has an open neighborhood on which $g_{i} > c_{i}$ , so their product is a neighborhood of $x$ on which $g (u) > \sum_{i} c_{i} = (s + t) / 2$ . With $η = (s - t) / 4 > 0$ , the product of these neighborhoods and $(t - η, t + η)$ misses $epi g$ , because its height coordinate is below $t + η < (s + t) / 2$ .

2.2A1step 1.3givenalgebra

If some $g_{i} (x_{i}) = + \infty$ , choose such an index $i$ . For each $j \neq i$ , put $c_{j} = g_{j} (x_{j}) - 1$ when that value is finite, and $c_{j} = 0$ when it is infinite. Choose $B = t + 1 - \sum_{j \neq i} c_{j}$ . Since $g_{i} (x_{i}) > B$ and $g_{j} (x_{j}) > c_{j}$ , step 1.3 supplies an open neighborhood of each block on which the corresponding strict lower bound holds. Throughout their product, $g (u) > B + \sum_{j \neq i} c_{j} = t + 1$ . Restrict the epigraph-height coordinate to $(t - 1 / 2, t + 1 / 2)$ ; this neighborhood also misses $epi g$ .

3.1step 1.1step 1.2step 2.1step 2.2algebra∎

Every point outside $epi g$ is covered by one of steps 2.1 or 2.2, so its complement is open and $epi g$ is closed. Together with properness from step 1.1 and convexity from step 1.2, this proves the Statement without converting an arbitrary sequential-closure claim into topological closedness.

AlgorithmAlgorithm: Literature-sourcedProof: Not applicablejudge pass (gpt-6-luna)Open item page →

Randomized proximal coordinate descent with certified inner solves

Definition

Whenever a subscript $i$ indexes a block, $x_{i}$ is shorthand for $x_{B_{i}}$ .

Let $F (x) = f (x) + \sum_{i = 1}^{n} g_{i} (x_{B_{i}})$ on $R^{d}$ , where $B_{1}, \dots, B_{n}$ is a disjoint nonempty partition of coordinate labels ${1, \dots, d}$ , with label $j$ denoting standard coordinate $j - 1$ . Let $f : R^{d} \to R$ be convex and continuously differentiable in the sense of Continuously differentiable maps, local inverses, and local diffeomorphisms, and let each $g_{i} : R^{∣ B_{i} ∣} \to (- \infty, + \infty]$ be proper, closed and convex. Define $\nabla_{i} f (x)$ from The Jacobian matrix of partial derivatives and the gradient in the scalar-valued case as the entries of $\nabla f (x)$ on the labels in $B_{i}$ , in increasing order; their existence follows from total differentiability and A total derivative computes every directional derivative, and its matrix is the Jacobian. Let $L_{i} > 0$ satisfy the block-gradient Lipschitz bound of Coordinate-block smoothness descent model, choose majorizers $M_{i} \geq L_{i}$ , probabilities $p_{i} > 0$ with $\sum_{i} p_{i} = 1$ , a feasible initial point $x^{0}$ , an update budget $K \in N$ , and nonnegative inner tolerances $ϵ_{0}, \dots, ϵ_{K - 1}$ .

At update $k$ , draw $I_{k}$ with probabilities $(p_{i})$ independently of previous draws. For the selected block $i = I_{k}$ , form $q_{i}^{k} (u) = ⟨ \nabla_{i} f (x^{k}), u - x_{B_{i}}^{k} ⟩ + \frac{M_{i}}{2} ∥ u - x_{B_{i}}^{k} ∥_{2}^{2} + g_{i} (u) .$ In exact mode, set $x_{B_{i}}^{k + 1}$ to the global minimizer of $q_{i}^{k}$ ; leave every other block unchanged. In certified-inexact mode, an inner oracle returns $(u_{k}, δ_{k})$ with a certificate $0 \leq q_{i}^{k} (u_{k}) - \inf_{u} q_{i}^{k} (u) \leq δ_{k} \leq ϵ_{k};$ accept $u_{k}$ only when that certificate is available and valid. Otherwise return the last accepted point with status inner-solve-failure. The output is the current point, its objective value, the last certified inner gap when available, and status tolerance-met, budget-limit, or inner-solve-failure.

If a proximal-gradient stopping tolerance $η \geq 0$ is requested, after each accepted update compute the block mapping $G_{M} (x) = (M_{i} [x_{B_{i}} - {prox}_{g_{i} / M_{i}} (x_{B_{i}} - M_{i}^{- 1} \nabla_{i} f (x))])_{i = 1}^{n} .$ Here ${prox}_{g_{i} / M_{i}}$ abbreviates ${prox}_{(1 / M_{i}) g_{i}}$ , a singleton by Proximal mapping and Existence, resolvent characterization, and firm nonexpansiveness of the proximal map; $M_{i} > 0$ by the input conditions. Stop with tolerance-met when $∥ G_{M} (x) ∥_{2} \leq η$ ; otherwise stop after at most $K$ accepted updates with budget-limit. A finite budget or tolerance status is not an uncomputed objective-gap guarantee. Uniform sampling is $p_{i} = 1 / n$ ; nonuniform choices require the separate probability/step relation proved for the smooth gradient branch on this page.

LemmaStatement: Literature-sourcedProof: AI-adaptedprecheck passOpen item page →

Coordinatewise minima of a separable convex composite are global minima

Statement

Let $f : R^{d} \to R$ be differentiable and convex, and let $B_{1}, \dots, B_{n}$ be a partition of the coordinate labels ${1, \dots, d}$ into nonempty blocks, with $n \geq 1$ . Let $g (x) = \sum_{i = 1}^{n} g_{i} (x_{B_{i}})$ be proper, closed and convex, with each $g_{i}$ proper, closed and convex on its block. Set $F = f + g$ . If $F (x) < + \infty$ and $x$ globally minimizes every block slice $u \mapsto F (x_{- i}, u)$ , where $(x_{- i}, u)$ means replace block $B_{i}$ of $x$ by $u$ and keep all other blocks fixed, then $- \nabla_{i} f (x) \in \partial g_{i} (x_{B_{i}}) (1 \leq i \leq n), - \nabla f (x) \in \partial g (x),$ and $x$ is a global minimizer of $F$ . For an extended-real convex $h$ , $p \in \partial h (a)$ means $h (z) \geq h (a) + ⟨ p, z - a ⟩$ for every $z$ .

Facts & Assumptions

Given: The finite block partition, the functions and the coordinatewise minimizing point in the Statement.

[F1]

Subdifferentials of proper extended-real convex functions: $p \in \partial h (a)$ exactly when $h (z) \geq h (a) + ⟨ p, z - a ⟩$ for every $z$ in the full Euclidean space.

[F2]

Proper closed convex extended-real functions on $R^{n}$ : each $g_{i}$ is convex and has nonempty effective domain; closed epigraph is lower semicontinuity in this convention.

[F3]

[F4]

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

[F5]

Identify block label $j \in {1, \dots, d}$ with standard coordinate $j - 1$ ; let $U_{i}$ insert a block displacement into those coordinates, and define $\nabla_{i} f (x)$ as the entries of $\nabla f (x)$ on $B_{i}$ , in increasing order. By Laws of finite sums and finite products and The Euclidean inner product $⟨ x, y ⟩ = \sum_{k < n} x_{k} y_{k}$ on $R^{n}$ , finite block sums add and the full inner product is the sum of the block inner products, so $⟨ \nabla f (x), U_{i} h ⟩ = ⟨ \nabla_{i} f (x), h ⟩$ .

[A1]

$f$ is differentiable and convex, $g = \sum_{i} g_{i}$ is proper closed convex, $F (x) < + \infty$ , and $x$ minimizes each exact one-block slice.

Proof

1.1A1F1F2F3F5givenalgebra

Fix a block $i$ , a point $z_{i}$ with $g_{i} (z_{i}) < + \infty$ , and put $h = z_{i} - x_{B_{i}}$ . For $0 < t < 1$ , block minimality and convexity of $g_{i}$ give $0 \leq f (x + U_{i} (t h)) - f (x) + g_{i} (x_{B_{i}} + t h) - g_{i} (x_{B_{i}}) \leq f (x + U_{i} (t h)) - f (x) + t [g_{i} (z_{i}) - g_{i} (x_{B_{i}})]$ . Rearranging, dividing by $t > 0$ , and taking $t ↓ 0$ , [F3] and [F5] give $g_{i} (z_{i}) - g_{i} (x_{B_{i}}) \geq - ⟨ \nabla f (x), U_{i} h ⟩ = - ⟨ \nabla_{i} f (x), z_{i} - x_{B_{i}} ⟩$ . For $g_{i} (z_{i}) = + \infty$ the same subgradient inequality is automatic. Thus $- \nabla_{i} f (x) \in \partial g_{i} (x_{B_{i}})$ by [F1].

2.1F1F5step 1.1algebra

Fix any $z = (z_{B_{i}})_{i}$ . If $g (z) = + \infty$ , the subgradient inequality at $z$ is automatic. Otherwise each $g_{i} (z_{B_{i}})$ is finite, so summing the block inequalities from step 1.1 and using [F5] gives $g (z) \geq g (x) - \sum_{i} ⟨ \nabla_{i} f (x), z_{B_{i}} - x_{B_{i}} ⟩ = g (x) - ⟨ \nabla f (x), z - x ⟩$ . Thus the subgradient inequality holds for every $z$ , and [F1] gives $- \nabla f (x) \in \partial g (x)$ .

3.1A1F4step 2.1algebra∎

By [F4], $f (z) \geq f (x) + ⟨ \nabla f (x), z - x ⟩$ . Adding the inequality in step 2.1 gives $F (z) \geq F (x)$ for every $z$ , so $x$ is globally minimizing and all the stated stationarity inclusions hold.

LemmaStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (gpt-6-luna)Open item page →

Coordinate proximal subproblems are attained uniquely and descend

Statement

For the model and inputs of Randomized proximal coordinate descent with certified inner solves, every selected exact block subproblem has a unique minimizer. If the update is exact, the objective does not increase. If its accepted inner point has certified model gap at most $ϵ_{k}$ , then the new objective is at most the old objective plus $ϵ_{k}$ .

Facts & Assumptions

Given: A feasible iterate $x$ , a selected block $i$ , positive majorizer $M_{i}$ , and proper closed convex block penalty $g_{i}$ .

[F1]

Randomized proximal coordinate descent with certified inner solves: the block model is $q_{i} (u) = ⟨ \nabla_{i} f (x), u - x_{i} ⟩ + (M_{i} / 2) ∥ u - x_{i} ∥_{2}^{2} + g_{i} (u)$ , and an accepted inexact point satisfies $q_{i} (u) - \inf q_{i} \leq ϵ_{k}$ .

[F2]

Existence, resolvent characterization, and firm nonexpansiveness of the proximal map: for proper closed convex $g$ , positive $t$ , and any $v$ , the proximal set ${prox}_{t g} (v)$ is a singleton.

[F3]

Proximal mapping: ${prox}_{t g} (v)$ is the set of global minimizers of $g (u) + ∥ u - v ∥_{2}^{2} / (2 t)$ .

[F4]

Proper closed convex extended-real functions on $R^{n}$ : each $g_{i}$ is proper, closed and convex on its Euclidean block space.

[F5]

Coordinate-block smoothness descent model: changing one block by $h$ raises $f$ by at most $⟨ \nabla_{i} f (x), h ⟩ + (L_{i} / 2) ∥ h ∥_{2}^{2}$ .

Proof

1.1F2F3F4givenalgebra

Complete the square in $q_{i}$ : with $v_{i} = x_{i} - M_{i}^{- 1} \nabla_{i} f (x)$ , its $u$ -dependent terms are $g_{i} (u) + (M_{i} / 2) ∥ u - v_{i} ∥_{2}^{2}$ . Taking $t = 1 / M_{i} > 0$ in [F2]–[F4] proves the exact block minimizer exists and is unique.

2.1F1F5step 1.1algebra∎

For an exact update, $q_{i} (u^{*}) \leq q_{i} (x_{i}) = g_{i} (x_{i})$ . For an accepted inexact update, [F1] gives $q_{i} (u) \leq q_{i} (u^{*}) + ϵ_{k} \leq q_{i} (x_{i}) + ϵ_{k}$ . Apply [F5] with $h = u - x_{i}$ and cancel the unchanged penalties on the other blocks; the resulting objective is at most $F (x)$ in the exact case and at most $F (x) + ϵ_{k}$ in the inexact case.

CounterexampleConstruction: AI-generatedVerification: AI-generatedprecheck passjudge pass (gpt-6-luna)Open item page →

An R-only proximal coordinate rate fails for nonsmooth penalties

Statement refuted

The claim that the uniform randomized proximal update for every proper closed convex separable penalty satisfies $E [F (x^{k}) - F^{*}] \leq \frac{2 n L_{\max} R^{2}}{k + 4}$ under only a bounded initial sublevel radius $R$ and positive coordinate majorizers $L_{i}$ is false without an error term or other dependence on the penalty.

Witness

Let $n = 2$ , $f (x) = 0$ , $g_{1} (u) = g_{2} (u) = 4 ∣ u ∣$ , $L_{1} = L_{2} = L_{\max} = 1$ , and $x^{0} = (1, 1)$ . The objective is $F (x) = 4 (∣ x_{1} ∣ + ∣ x_{2} ∣)$ and $F^{*} = 0$ at $x^{*} = (0, 0)$ . The initial sublevel is the closed diamond $∣ x_{1} ∣ + ∣ x_{2} ∣ \leq 2$ , whose radius about $x^{*}$ is $R = 2$ .

Facts & Assumptions

Given: The proximal update in Randomized proximal coordinate descent with certified inner solves and the scalar minimizer in The one-coordinate absolute-value quadratic minimizer.

[F1]

Randomized proximal coordinate descent with certified inner solves: for selected block $i$ the exact update minimizes $⟨ \nabla_{i} f (x), u - x_{i} ⟩ + (M_{i} / 2) ∣ u - x_{i} ∣^{2} + g_{i} (u)$ .

[F2]

The one-coordinate absolute-value quadratic minimizer: $\frac{a}{2} u^{2} - b u + τ ∣ u ∣$ has unique minimizer $S_{τ} (b) / a$ when $a, τ > 0$ .

[F3]

Proper closed convex extended-real functions on $R^{n}$ : a block penalty is proper, closed and convex when its effective domain is nonempty, its epigraph is closed, and it satisfies the segment inequality.

[F4]

Absolute value in an ordered field, Basic properties of the absolute value and The triangle inequality: absolute value is nonnegative, positively homogeneous, and subadditive.

[F5]

The Euclidean inner product $⟨ x, y ⟩ = \sum_{k < n} x_{k} y_{k}$ on $R^{n}$ and Cauchy-Schwarz $∣ ⟨ x, y ⟩ ∣ \leq ∥ x ∥_{2} ∥ y ∥_{2}$ with its equality case, the triangle inequality for $∥ \cdot ∥_{2}$ , the parallelogram law and polarisation: the two-coordinate Euclidean norm is a norm and its triangle inequality gives $∥ (x_{1}, x_{2}) ∥_{2} \leq ∣ x_{1} ∣ + ∣ x_{2} ∣$ by decomposing into coordinate vectors.

[A1]

The proximal coordinate algorithm uses common model majorizers $M_{1} = M_{2} = 1$ , samples uniformly, and runs at least one update with no stopping tolerance.

Proof

1.1A1F1F3F4F5givenalgebra

The assumptions hold: $f = 0$ is convex and continuously differentiable and has zero gradient, so $L_{i} = M_{i} = 1$ is a valid positive block-gradient bound and majorizer. Each $g_{i} (u) = 4 ∣ u ∣$ is finite everywhere and hence proper; [F4] gives convexity; and $epi g_{i} = {(u, t) : t \geq 4 u, t \geq - 4 u}$ is an intersection of closed half-planes, so it is closed in the epigraph convention [F3]. Thus $F (x) = 4 (∣ x_{1} ∣ + ∣ x_{2} ∣)$ and its minimum is $F^{*} = 0$ at $x^{*} = (0, 0)$ . The initial value is $F (x^{0}) = 8$ and its sublevel is $∣ x_{1} ∣ + ∣ x_{2} ∣ \leq 2$ . There $∥ x - x^{*} ∥_{2} = \sqrt{x_{1}^{2} + x_{2}^{2}} \leq ∣ x_{1} ∣ + ∣ x_{2} ∣ \leq 2$ by [F4]--[F5], with equality at $(2, 0)$ ; hence $R = 2$ .

2.1F1F2step 1.1algebra

For either selected coordinate the subproblem at its current value $1$ is $4 ∣ u ∣ + \frac{1}{2} (u - 1)^{2}$ , which differs by a constant from $\frac{1}{2} u^{2} - u + 4 ∣ u ∣$ . By [F2] its unique minimizer is $S_{4} (1) = 0$ . The other coordinate remains $1$ , so after one update $F (x^{1}) = 4$ for either draw and $E [F (x^{1}) - F^{*}] = 4$ .

3.1step 1.1step 2.1algebra∎

The proposed upper bound at $k = 1$ is $2 \cdot 2 \cdot 1 \cdot 2^{2} / (1 + 4) = 16 / 5 < 4$ , contradicting step 2.1. Therefore the claimed penalty-independent composite bound is false.

Remarks

The controlling plan's $O (1 / k)$ rate is for the smooth coordinate-gradient branch $g_{i} = 0$ . This witness does not refute that branch.

CounterexampleConstruction: AI-generatedVerification: AI-generatedprecheck passOpen item page →

Strong convexity of the composite alone does not give the stated coordinate factor

Statement refuted

The claim that $F = f + \sum_{i} g_{i}$ being $μ$ -strongly convex by itself implies the contraction factor $1 - μ / (n L_{\max})$ for the randomized proximal coordinate update is false when the curvature comes only from the nonsmooth-separable term.

Witness

Take $n = 2$ , $f = 0$ , $g_{1} (u) = g_{2} (u) = \frac{1}{2} u^{2}$ , common positive majorizers $L_{1} = L_{2} = L_{\max} = 1$ , and $x^{0} = (1, 1)$ . Then $F (x) = \frac{1}{2} (x_{1}^{2} + x_{2}^{2})$ is globally $μ = 1$ strongly convex and has minimum $F^{*} = 0$ .

Facts & Assumptions

Given: The update rule of Randomized proximal coordinate descent with certified inner solves for the stated two-block objective.

[F1]

Randomized proximal coordinate descent with certified inner solves: in exact mode, with $f = 0$ and $M_{i} = 1$ , the selected block minimizes $g_{i} (u) + \frac{1}{2} (u - x_{i})^{2}$ .

[F2]

Proper closed convex extended-real functions on $R^{n}$ : each block penalty must have nonempty finite domain, closed epigraph, and satisfy the convexity inequality.

[A1]

The run uses exact mode, the common model majorizers are $M_{1} = M_{2} = 1$ , the two coordinates are sampled uniformly, and the run executes at least one update with no stopping tolerance.

Proof

1.1A1F1F2givenalgebra

Each $g_{i} (u) = u^{2} / 2$ is finite and its epigraph ${(u, t) : u^{2} / 2 \leq t}$ is closed; hence it is proper under [F2]. The identity $g_{i} ((1 - s) u + s v) = (1 - s) g_{i} (u) + s g_{i} (v) - s (1 - s) (u - v)^{2} / 2$ proves convexity. The same identity summed over coordinates shows $F (x) = \frac{1}{2} ∥ x ∥_{2}^{2}$ is globally $μ = 1$ strongly convex, with unique minimum at $x^{*} = (0, 0)$ . Since $f = 0$ has zero gradient, $L_{i} = 1$ are valid positive block-gradient bounds and $M_{i} = L_{\max} = 1$ . For either selected coordinate the model is $q (u) = \frac{1}{2} u^{2} + \frac{1}{2} (u - 1)^{2} = (u - \frac{1}{2})^{2} + \frac{1}{4}$ , so its unique minimizer is $u = 1 / 2$ . The other coordinate remains $1$ . Thus every one-step outcome has objective gap $\frac{1}{2} ((1 / 2)^{2} + 1) = 5 / 8$ , and the expected gap is also $5 / 8$ .

2.1step 1.1givenalgebra∎

The claimed factor would give $(1 - μ / (n L_{\max})) (F (x^{0}) - F^{*}) = (1 - 1 / 2) \cdot 1 = 1 / 2$ , which is strictly smaller than $5 / 8$ . Hence composite strong convexity alone does not imply that factor. The positive-rate theorem on this page assumes the smooth term $f$ itself is $μ$ -strongly convex.

TheoremStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (gpt-6-luna)Open item page →

Cyclic exact block descent has globally optimal accumulation points

Statement

Let $F (x) = f (x) + g (x)$ on $R^{d}$ , where $f : R^{d} \to R$ is convex and continuously differentiable, and $g (x) = \sum_{i} g_{i} (x_{B_{i}})$ is proper closed convex with each $g_{i}$ proper closed convex. Assume $F (x^{0}) < + \infty$ and the initial sublevel set $S = {x : F (x) \leq F (x^{0})}$ is compact. Suppose every exact block minimizer on the visited sublevel exists uniquely and the resulting block-minimizer maps are continuous. Then every accumulation point of any indefinitely continued cyclic full-sweep run of Cyclic exact block minimization is coordinatewise minimizing, satisfies $0 \in \nabla f (x) + \partial g (x)$ , and is a global minimizer of $F$ . If the global minimizer is unique, the full sequence, including within-sweep iterates, converges to it. The theorem uses the unique-continuous-minimizer branch of the pair design; it makes no claim for arbitrary nonconvex or nonseparable nonsmooth updates.

Facts & Assumptions

Given: The objective, compact sublevel and block-minimizer hypotheses in the Statement.

[F1]

Cyclic exact block minimization: a sweep minimizes each block in order and leaves the other blocks unchanged.

[F2]

Continuity of the cyclic block-minimum value: with continuous unique block-minimizer maps, the value of each block minimum is continuous in the other coordinates.

[F3]

Coordinatewise minima of a separable convex composite are global minima: a coordinatewise minimum of this convex separable composite is stationary and globally minimizing.

[F4]

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

[F5]

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

[F6]

In any metric space compactness implies countable compactness and limit point compactness, and each of countable compactness and limit point compactness implies sequential compactness; every implication here is proved without a choice principle: every sequence in a compact metric space has a convergent subsequence; the theorem proves this implication without a choice principle.

[F7]

Every nonempty set bounded below has an infimum and Epsilon characterisation of the infimum: a nonempty real set bounded below has an infimum, and elements lie arbitrarily close above it.

[F8]

A compact subset of a metric space is closed and bounded: a compact subset of a metric space is closed, so ambient limits of iterates in $S$ remain in $S$ .

[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}$ hypothesis makes $f$ continuous, as required by [F4].

[F10]

The well-ordering principle and The recursion theorem: a recursively defined subsequence can choose the least next natural index in any nonempty set of admissible indices.

[F11]

Cauchy-Schwarz $∣ ⟨ x, y ⟩ ∣ \leq ∥ x ∥_{2} ∥ y ∥_{2}$ with its equality case, the triangle inequality for $∥ \cdot ∥_{2}$ , the parallelogram law and polarisation: the Euclidean norm is continuous, so a limit of points outside a fixed open ball remains outside that ball's interior.

[A1]

The maps for the exact block minimizers are single-valued and continuous on the states in $S$ ; every finite update is exact.

Proof

1.1A1F1F4F5F7F9givenalgebra

By [F1], $F$ is nonincreasing at every block update, so all cycle and within-cycle iterates remain in $S$ . By [F9], $f$ is continuous, so [F4] makes $F$ lower semicontinuous; it is real-valued on $S$ because $F \leq F (x^{0}) < + \infty$ . Thus [F5] bounds it below on $S$ . By [F7], $L = \inf_{k} F (x^{k})$ is real; for each $ε > 0$ , [F7] gives $j$ with $F (x^{j}) < L + ε$ , and monotonicity then gives $L \leq F (x^{k}) \leq F (x^{j}) < L + ε$ for all $k \geq j$ . Hence the full-sweep values tend to $L$ .

2.1A1F1F8step 1.1given

Fix any accumulation point $\overset{ˉ}{x}$ of the full-sweep iterates and a subsequence $x^{k_{j}} \to \overset{ˉ}{x}$ . Since $S$ is compact, [F8] makes it closed and therefore $\overset{ˉ}{x} \in S$ . The intermediate states $y_{j}^{0} = x^{k_{j}}, y_{j}^{1}, \dots, y_{j}^{n} = x^{k_{j} + 1}$ satisfy $F (x^{k_{j}}) \geq F (y_{j}^{i}) \geq F (x^{k_{j} + 1})$ . Both endpoint values tend to $L$ , so every intermediate value tends to $L$ . By [A1] and continuity of the finitely many block maps, each $y_{j}^{i}$ converges to a limit ${\overset{ˉ}{y}}^{i}$ , with ${\overset{ˉ}{y}}^{0} = \overset{ˉ}{x}$ .

3.1A1F1F2step 2.1algebra

Fix $i$ . Let $a_{j}$ be the coordinates other than block $i$ in $y_{j}^{i - 1}$ , and let $u_{j}^{-}$ and $u_{j}^{+}$ be its block- $i$ coordinates before and after the update. Then $a_{j} \to \overset{ˉ}{a}$ , $u_{j}^{-} \to {\overset{ˉ}{u}}^{-}$ , and $u_{j}^{+} \to {\overset{ˉ}{u}}^{+}$ by step 2.1; exactness gives $u_{j}^{+} = T_{i} (a_{j})$ . Write $m_{i} (a) = \min_{u} {f (a, u) + g_{i} (u)}$ . Since the other penalties cancel, the objective decrease is $d_{j} = f (a_{j}, u_{j}^{-}) + g_{i} (u_{j}^{-}) - m_{i} (a_{j})$ , and $d_{j} \to 0$ because the two intermediate objective values both tend to $L$ . By [F2], $m_{i} (a_{j}) \to m_{i} (\overset{ˉ}{a})$ ; continuity of $f$ and lower semicontinuity of $g_{i}$ imply $f (\overset{ˉ}{a}, {\overset{ˉ}{u}}^{-}) + g_{i} ({\overset{ˉ}{u}}^{-}) \leq m_{i} (\overset{ˉ}{a})$ . The reverse inequality follows from the minimum definition, so $u^{-} = T_{i} (\overset{ˉ}{a})$ by uniqueness. Continuity of $T_{i}$ gives ${\overset{ˉ}{u}}^{+} = T_{i} (\overset{ˉ}{a}) = {\overset{ˉ}{u}}^{-}$ , hence ${\overset{ˉ}{y}}^{i} = {\overset{ˉ}{y}}^{i - 1}$ .

4.1A1F3step 3.1algebra

Applying step 3.1 for $i = 1, \dots, n$ shows every within-sweep limit equals $\overset{ˉ}{x}$ and that $\overset{ˉ}{x}$ minimizes every block slice. Since $\overset{ˉ}{x} \in S$ and $F (x^{0}) < + \infty$ , $F (\overset{ˉ}{x}) < + \infty$ . By [F3], $\overset{ˉ}{x}$ satisfies the composite stationarity condition and is globally minimizing. Since $\overset{ˉ}{x}$ was arbitrary, every accumulation point is global.

5.1F6F10F11step 2.1step 3.1step 4.1algebra∎

The sequence lies in compact $S$ , so [F6] supplies an accumulation point. If the global minimizer is unique, step 4.1 makes it the only possible accumulation point. Fix $ε > 0$ . If infinitely many full-sweep indices lay outside the open $ε$ -ball about that minimizer, start with the least such index and recursively choose the least later such index; infinitude makes each candidate set nonempty, while [F10] supplies the least indices and constructs the sequence. By [F6] it has a convergent subsequence with limit in $S$ , and [F11] keeps that limit outside the ball, producing a different accumulation point. Thus all sufficiently late full-sweep iterates lie in the ball. For a fixed within-sweep position, suppose a subsequence of those states converges to $y$ . Its cycle-start subsequence lies in compact $S$ , so [F6] supplies a further subsequence converging to some $x \in S$ ; steps 2.1 and 3.1 show that the corresponding within-sweep states also converge to $x$ , hence $y = x$ and is a full-sweep accumulation point. Therefore every convergent subsequence of within-sweep states has the unique minimizer as its limit. If infinitely many states at that position lay outside the ball, the least-index recursion and [F6] would give a convergent subsequence whose limit remains outside by [F11], a contradiction. Hence each within-sweep sequence converges to the unique minimizer as well.

TheoremStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (gpt-6-luna)Open item page →

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]

[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.

TheoremStatement: AI-adaptedProof: AI-generatedOpen item page →

Proximal coordinate contraction from strong convexity of the composite

Statement

For a finite horizon $k$ , use an algorithm budget $K \geq k$ and do not request a proximal-gradient stopping tolerance before that horizon.

Let $B_{1}, \dots, B_{n}$ be a partition of $R^{d}$ into nonempty coordinate blocks, with $n, d \geq 1$ . Let $f : R^{d} \to R$ be convex and continuously differentiable, with positive block-gradient Lipschitz constants $L_{i}$ , and let $g (x) = \sum_{i = 1}^{n} g_{i} (x_{B_{i}})$ , where each $g_{i}$ is proper, closed and convex in the closed-epigraph convention. Set $F = f + g$ and $L_{\max} = \max_{i} L_{i} > 0$ . Assume $F$ itself is $μ$ -strongly convex for some $μ > 0$ : for finite-domain $x, y$ and $s \in [0, 1]$ , $F ((1 - s) x + s y) \leq (1 - s) F (x) + s F (y) - \frac{μ}{2} s (1 - s) ∥ x - y ∥_{2}^{2} .$ No strong convexity of $f$ alone is required, and no inequality $μ \leq L_{\max}$ is assumed.

Run Randomized proximal coordinate descent with certified inner solves from $F (x^{0}) < + \infty$ , with common majorizer $M_{i} = L_{\max}$ and uniform independent block draws. Fix a finite horizon $k$ and deterministic bounds $ϵ_{0}, \dots, ϵ_{k - 1} \geq 0$ . Assume the first $k$ updates are executed with accepted inner-model gap certificates at most $ϵ_{j}$ at every history in the finite block-history distribution; a stopping or failed call supplies no unexecuted later iterate. Then $F$ has a unique minimizer $x^{*}$ and, with $q_{c} = 1 - \frac{μ}{n (L_{\max} + μ)} \in (0, 1),$ $E [F (x^{k}) - F (x^{*})] \leq q_{c}^{k} (F (x^{0}) - F (x^{*})) + \sum_{j = 0}^{k - 1} q_{c}^{k - 1 - j} ϵ_{j} .$ The expectation is the finite weighted sum over the uniformly sampled block histories, not a distribution conditioned on successful calls. At $k = 0$ the sum is empty and the bound is equality. Exact updates have $ϵ_{j} = 0$ . This includes curvature contributed by the separable penalties; it does not assert the sharper factor $1 - μ / (n L_{\max})$ without additional smooth-part curvature.

Facts & Assumptions

Given: The functions, constants, strong-convexity segment inequality, finite initial point, sampling rule and accepted per-history updates in the Statement.

[F1]

[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]

[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]

[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]

Proper closed convex extended-real functions on $R^{n}$ : properness is nonempty finite domain, convexity is the extended-real segment inequality, and closedness is closedness of the epigraph.

[F10]

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

[F11]

[F12]

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

[F13]

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

[A1]

The segment strong-convexity inequality in the Statement holds for $F$ , with $μ > 0$ ; $f$ is convex and $L_{\max} > 0$ .

[A2]

Every executed history through the horizon has accepted certificates, with deterministic errors $ϵ_{j}$ ; block sampling remains independent and uniform, without conditioning on successful histories. Finite-sum laws [F13] justify averaging the conditional bounds over these histories.

Proof

1.1A1F4F5F6F7F8F9F11givenconstructalgebra

By [F4], $g$ is proper closed convex, and by [F11], $f$ is continuous. Applying [F6] makes $F$ proper closed convex. Define $H (x) = F (x) - μ ∥ x ∥_{2}^{2} / 2$ , keeping $+ \infty$ off the finite domain. It is proper. The identity $∥ (1 - s) x + s y ∥_{2}^{2} = (1 - s) ∥ x ∥_{2}^{2} + s ∥ y ∥_{2}^{2} - s (1 - s) ∥ x - y ∥_{2}^{2}$ and [A1] show $H$ is convex, including the extended-real endpoint convention. The epigraph of $H$ is the preimage of the closed epigraph of $F$ under the continuous map $(x, a) \mapsto (x, a + μ ∥ x ∥_{2}^{2} / 2)$ ; hence $H$ is closed. By [F5] applied to $H$ , $F (x) \geq μ ∥ x ∥_{2}^{2} / 2 + ⟨ a, x ⟩ + b$ for some $a, b$ , so $F$ is coercive. For a finite-domain $\overset{ˉ}{x}$ , the nonempty sublevel $S = {x : F (x) \leq F (\overset{ˉ}{x})}$ is closed by the closed epigraph and bounded by coercivity, hence compact by [F7]. The restriction $F ∣_{S}$ is real-valued and lower semicontinuous, so [F8] attains its minimum. Points outside $S$ cannot improve it. The midpoint inequality [A1] forbids distinct minimizers, giving a unique $x^{*}$ .

1.2A2F1F2F3F13givenalgebra

Fix a finite current point $x$ . For block $i$ let $z_{i}$ be the exact minimizer of $Q_{i} (u) = ⟨ \nabla_{i} f (x), u - x_{B_{i}} ⟩ + \frac{L_{\max}}{2} ∥ u - x_{B_{i}} ∥_{2}^{2} + g_{i} (u) .$ Existence and uniqueness follow from [F2]. Define $M_{x} (w) = f (x) + ⟨ \nabla f (x), w - x ⟩ + \frac{L_{\max}}{2} ∥ w - x ∥_{2}^{2} + g (w) .$ Separation of the finite block sum shows $z = (z_{i})_{i}$ minimizes $M_{x}$ , and $\sum_{i} [Q_{i} (z_{i}) - Q_{i} (x_{B_{i}})] = M_{x} (z) - F (x)$ . By [F3] and $L_{i} \leq L_{\max}$ , the actual update in a sampled block satisfies $F (x^{+}) \leq F (x) + Q_{i} (z_{i}) - Q_{i} (x_{B_{i}}) + ϵ_{j} .$ By [F13], averaging over the uniform block choice at this fixed history therefore gives $E [F (x^{+}) ∣ history] \leq F (x) + \frac{M_{x} (z) - F (x)}{n} + ϵ_{j} .$ All quantities are finite at these points because accepted model gaps and exact block minima are finite.

2.1A1F9F10step 1.1step 1.2givenalgebra

By [F10], convex differentiability of $f$ gives $f (x) + ⟨ \nabla f (x), w - x ⟩ \leq f (w)$ . Thus, for $w_{s} = (1 - s) x + s x^{*}$ , $M_{x} (w_{s}) - F (x) \leq F (w_{s}) - F (x) + \frac{L_{\max} s^{2}}{2} ∥ x^{*} - x ∥_{2}^{2} .$ These segment values are finite by convexity of the effective domain. Apply [A1] to obtain $M_{x} (z) - F (x) \leq - s (F (x) - F (x^{*})) + \frac{L_{\max} s^{2} - μ s (1 - s)}{2} ∥ x^{*} - x ∥_{2}^{2} .$ Choose $s = μ / (L_{\max} + μ) \in (0, 1)$ . The squared-distance coefficient vanishes, so $M_{x} (z) - F (x) \leq - s (F (x) - F (x^{*}))$ . This does not require $μ \leq L_{\max}$ .

3.1A2step 1.2step 2.1algebra

Substitute step 2.1 in step 1.2 to get $E [F (x^{j + 1}) - F (x^{*}) ∣ history] \leq q_{c} (F (x^{j}) - F (x^{*})) + ϵ_{j} .$ By [A2] all histories in the finite product distribution are present; summing the inequality with their weights gives $ϕ_{j + 1} \leq q_{c} ϕ_{j} + ϵ_{j}$ , where $ϕ_{j} = E [F (x^{j}) - F (x^{*})]$ . No conditioning on the event of a successful inner solve is used.

4.1F12step 2.1step 3.1algebra∎

The proposed bound at $k = 0$ is $ϕ_{0} = ϕ_{0}$ . If $ϕ_{j} \leq q_{c}^{j} ϕ_{0} + \sum_{ℓ < j} q_{c}^{j - 1 - ℓ} ϵ_{ℓ}$ , multiply by $q_{c} > 0$ and use step 3.1 to obtain the bound at $j + 1$ . By [F12], finite induction proves the displayed convolution. It specializes to exact-update contraction when every $ϵ_{j} = 0$ .

5 · Examples, counterexamples and false statements

None yet.

Coordinate and block descent methods

1 · Prerequisites

2 · Summary

3 · Logical flowchart

4 · Definitions, theorems and proofs

Randomized coordinate gradient descent

Definition

Coordinate-block smoothness descent model

Statement

Facts & Assumptions

Proof

The one-coordinate absolute-value quadratic minimizer

Statement

Facts & Assumptions

Proof

Remarks

Cyclic exact block minimization

Definition

Rates for randomized coordinate gradient descent and importance sampling

Statement

Facts & Assumptions

Proof

Continuity of the cyclic block-minimum value

Statement

Facts & Assumptions

Proof

Cyclic exact block minimization can cycle outside the convex separable hypotheses

Statement refuted

Witness

Facts & Assumptions

Proof

Remarks

Exact Lasso coordinate update, including a zero column

Statement

Facts & Assumptions

Proof

Finite separable block penalties are proper, closed, and convex

Statement

Facts & Assumptions

Proof

Randomized proximal coordinate descent with certified inner solves

Definition

Coordinatewise minima of a separable convex composite are global minima

Statement

Facts & Assumptions

Proof

Coordinate proximal subproblems are attained uniquely and descend

Statement

Facts & Assumptions

Proof

An R-only proximal coordinate rate fails for nonsmooth penalties

Statement refuted

Witness

Facts & Assumptions

Proof

Remarks

Strong convexity of the composite alone does not give the stated coordinate factor

Statement refuted

Witness

Facts & Assumptions

Proof

Cyclic exact block descent has globally optimal accumulation points

Statement

Facts & Assumptions

Proof

Strongly convex smooth-part proximal coordinate contraction

Statement

Facts & Assumptions

Proof

Proximal coordinate contraction from strong convexity of the composite

Statement

Facts & Assumptions

Proof

5 · Examples, counterexamples and false statements

Sources