Randomized proximal coordinate descent with certified inner solves

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 ${\mathbb{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:{\mathbb{R}}^d\to \mathbb{R}$ be convex and continuously differentiable in the sense of Continuously differentiable maps, local inverses, and local diffeomorphisms, and let each $g_i:{\mathbb{R}}^{\mathrm{\mid }{B}_i\mathrm{\mid }}\to (-\mathrm{\infty },+\mathrm{\infty }]$ be proper, closed and convex. Define ${\mathrm{\nabla }}_{i}f(x)$ from The Jacobian matrix of partial derivatives and the gradient in the scalar-valued case as the entries of $\mathrm{\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\ge L_i$, probabilities $p_i>0$ with ${\sum }_i{p}_i=1$, a feasible initial point $x^0$, an update budget $K\in \mathbb{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)=⟨{\mathrm{\nabla }}_{i}f(x^k),u-x_{B_i}^k⟩+\frac{M_i}{2}\mathrm{\parallel }u-x_{B_i}^k{\mathrm{\parallel }}_2^2+g_i(u)\mathrm{.}$ 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,{\delta }_k)$ with a certificate $0\le q_i^k(u_k)-{\inf }_u{q}_i^k(u)\le {\delta }_k\le {ϵ}_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 $\eta \ge 0$ is requested, after each accepted update compute the block mapping $G_M(x)=(M_i[x_{B_i}-{\mathrm{prox}}_{g_i\mathrm{/}{M}_i}(x_{B_i}-M_i^{-1}{\mathrm{\nabla }}_{i}f(x))]{)}_{i=1}^n\mathrm{.}$ Here ${\mathrm{prox}}_{g_i\mathrm{/}{M}_i}$ abbreviates ${\mathrm{prox}}_{(1\mathrm{/}{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 $\mathrm{\parallel }{G}_M(x){\mathrm{\parallel }}_2\le \eta$; 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\mathrm{/}n$; nonuniform choices require the separate probability/step relation proved for the smooth gradient branch on this page.