Random coordinate descent

Random Coordinate Descent Method is optimization technique popularized in last years. It can be seen as a generalization of Coordinate descent Method with one modification: Coorinate directions are chosen randomly. Many authors reported that randomization improve Rate of convergence (time or number of iterations needed to get solution), but there was no theoretical analysis. The first proper analysis of this method came from Yurii Nesterov (2010). In that paper author proposed a randomized coordinate descent method when first order information is used.

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.e. $|\nabla f_{i}(x)-\nabla f_{i}(x+he_{i})|\leq L_{i}|h|$) then the following algorithm converges to 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

One need to realize that this algorithm is random and hence also output after $k$ iterations is a random variable. 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}\{f(x)\}$), $\rho \in (0,1)$ is our confidence level and $\epsilon >0$ is our target accuracy, then $Prob(f(x_{k})-f^{*}>\epsilon )\leq \rho$.

Example on particular function

In next Figure we show how $x_{k}$ develops during iterations. The problem was

$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 naturaly extend this algorithm not only just to coordinates, but to blocks of coordinates. Assume that we have space $R^{5}$. This space has 5 coorinate 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. Hovewer, one can group some coordinate directions into blocks and we can have istead of those 5 coordinate directions 3 block coordinate directions (see image).

See also

• Coordinate descent
• Gradient descent
• Mathematical optimization