LemmaStatement: Literature-sourcedProof: AI-adaptedPipeline-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.

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]

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 (x), v ⟩$ .

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

Depends on

Used by

Cyclic exact block descent has globally optimal accumulation points Theorem

Dependency tree · two levels

45 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

P. Tseng, Convergence of a Block Coordinate Descent Method for Nondifferentiable Minimization, §4 (standard reference, not scraped)
Stephen J. Wright, Coordinate Descent Algorithms, §3.3 (standard reference, not scraped)