Randomized coordinate gradient descent

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

Let $d,n\ge 1$, let $B_1,\dots ,B_n$ be a partition of $\{1,\dots ,d\}$ into nonempty blocks, and let $U_i:{\mathbb{R}}^{\mathrm{\mid }{B}_i\mathrm{\mid }}\to {\mathbb{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:{\mathbb{R}}^d\to \mathbb{R}$ be convex and continuously differentiable in the sense of Continuously differentiable maps, local inverses, and local diffeomorphisms. Its gradient $\mathrm{\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 ${\mathrm{\nabla }}_{i}f(x)$ to be the entries of $\mathrm{\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 $\mathrm{\parallel }{\mathrm{\nabla }}_{i}f(x+U_{i}h)-{\mathrm{\nabla }}_{i}f(x){\mathrm{\parallel }}_2\le L_i\mathrm{\parallel }h{\mathrm{\parallel }}_2(x\in {\mathbb{R}}^d,h\in {\mathbb{R}}^{\mathrm{\mid }{B}_i\mathrm{\mid }}),$ Choose majorizers $M_i\ge L_i$, probabilities $p_i>0$ with ${\sum }_i{p}_i=1$, an initial point $x^0$, and a finite update budget $K\in \mathbb{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}}{\mathrm{\nabla }}_{I_k}f(x^k),x_{B_j}^{k+1}=x_{B_j}^k(j\mathrm{\ne }{I}_k)\mathrm{.}$ Uniform sampling means $p_i=1\mathrm{/}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.