CounterexampleConstruction: AI-generatedVerification: AI-generatedPipeline-generatedprecheck pass

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.

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.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

25 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 (standard reference, not scraped)