Random coordinate descent

Randomized (Block) Coordinate Descent Method is an optimization algorithm popularized by Nesterov (2010) and Richtárik and Takáč (2011). The first analysis of this method, when applied to the problem of minimizing a smooth convex function, was performed by Nesterov (2010). In Nesterov's analysis the method needs to be applied to a quadratic perturbation of the original function with an unknown scaling factor. Richtárik and Takáč (2011) give iteration complexity bounds which do not require this, i.e., the method is applied to the objective function directly. Furthermore, they generalize the setting to the problem of minimizing a composite function, i.e., sum of a smooth convex and a (possibly nonsmooth) convex block-separable function:

$F(x)=f(x)+\Psi (x),$

where $\Psi (x)=\sum _{i=1}^{n}\Psi _{i}(x^{(i)}),$ $x\in R^{N}$ is decomposed into $n$ blocks of variables/coordinates: $x=(x^{(1)},\dots ,x^{(n)})$ and $\Psi _{1},\dots ,\Psi _{n}$ are (simple) convex functions.

Example (block decomposition): If $x=(x_{1},x_{2},\dots ,x_{5})\in R^{5}$ and $n=3$, one may choose $x^{(1)}=(x_{1},x_{3}),x^{(2)}=(x_{2},x_{5})$ and $x^{(3)}=x_{4}$.

Example (block-separable regularizers):

1. $n=N;\Psi (x)=\|x\|_{1}=\sum _{i=1}^{n}|x_{i}|$
2. $n<N;\Psi (x)=\sum _{i=1}^{n}|x^{(i)}|_{2}$, where $\|t\|_{2}=(\sum _{j}t_{j}^{2})^{1/2}$.

Algorithm

Imagine that one wants to solve problem $\min _{x\in R^{n}}\{f(x)\},$ where $f$ is a Smooth function. Nesterov showed that if the gradient of $f$ is coordinate-wise Lipschitz continuous, with constants $L_{i},i=1,2,\dots ,n$ (i.e. $|\nabla f_{i}(x+he_{i})-\nabla f_{i}(x)|\leq L_{i}|h|$) then the following algorithm converges to the optimal value:

Algorithm Random Coordinate Descent Method
  Input: $x_{0}\in R^{n}$ //starting point
  Output: $x$
  set x=x_0
  for k=1,... do
     choose random coordinate $i\in \{1,2,\dots ,n\}$
     update $x^{(i)}=x^{(i)}-{\frac {1}{L_{i}}}\nabla f_{i}(x)$ 
  endfor;

• "←" denotes assignment. For instance, "largest ← item" means that the value of largest changes to the value of item.
• "return" terminates the algorithm and outputs the following value.

Convergence rate

Since the iterates of this algorithm are random vectors, a complexity result would give a bound on the number of iterations needed for the method to output an approximate solution with high probability. It was shown in that if $k\geq {\frac {2nR_{L}(x_{0})}{\epsilon }}\log \left({\frac {f(x_{0})-f^{*}}{\epsilon \rho }}\right)$, where $R_{L}(x)=\max _{y}\max _{x^{*}\in X^{*}}\{\|y-x^{*}\|_{L}:f(y)\leq f(x)\}$, $f^{*}$ is an optimal solution ($f^{*}=\min _{x\in R^{n}}\{f(x)\}$), $\rho \in (0,1)$ is a confidence level and $\epsilon >0$ is target accuracy, then $Prob(f(x_{k})-f^{*}>\epsilon )\leq \rho$.

Example on particular function

The following Figure shows how $x_{k}$ develops during iterations, in principle. The problem is

$f(x)={\tfrac {1}{2}}x^{T}\left({\begin{array}{cc}1&0.5\\0.5&1\end{array}}\right)x-\left({\begin{array}{cc}1.5&1.5\end{array}}\right)x,\quad x_{0}=\left({\begin{array}{cc}0&0\end{array}}\right)^{T}$

Extension to Block Coordinate Setting

Blocking coordinate directions into Block coordinate directions

One can naturally extend this algorithm not only just to coordinates, but to blocks of coordinates. Assume that we have space $R^{5}$. This space has 5 coordinate directions, concretely $e_{1}=(1,0,0,0,0)^{T},e_{2}=(0,1,0,0,0)^{T},e_{3}=(0,0,1,0,0)^{T},e_{4}=(0,0,0,1,0)^{T},e_{5}=(0,0,0,0,1)^{T}$ in which Random Coordinate Descent Method can move. However, one can group some coordinate directions into blocks and we can have instead of those 5 coordinate directions 3 block coordinate directions (see image).

See also

• Coordinate descent
• Gradient descent
• Mathematical optimization