Random coordinate descent

Consider the optimization problem

${\displaystyle \min _{x\in R^{n}}f(x),}$

where ${\displaystyle f}$ is a convex and smooth function.

Smoothness: By smoothness we mean the following: we assume the gradient of ${\displaystyle f}$ is coordinate-wise Lipschitz continuous with constants ${\displaystyle L_{1},L_{2},\dots ,L_{n}}$. That is, we assume that

${\displaystyle |\nabla _{i}f(x+he_{i})-\nabla _{i}f(x)|\leq L_{i}|h|,}$

for all ${\displaystyle x\in R^{n}}$ and ${\displaystyle h\in R}$, where ${\displaystyle \nabla _{i}}$ denotes the partial derivative with respect to variable ${\displaystyle x^{(i)}}$.

Nesterov, and Richtarik and Takac showed that the following algorithm converges to the optimal point:

Algorithm Random Coordinate Descent Method
    Input: ${\displaystyle x_{0}\in R^{n}}$ //starting point
    Output: ${\displaystyle x}$

    set x := x_0

    for k := 1, ... do
        choose coordinate ${\displaystyle i\in \{1,2,\dots ,n\}}$, uniformly at random
        update ${\displaystyle x^{(i)}=x^{(i)}-{\frac {1}{L_{i}}}\nabla f_{i}(x)}$ 
    end for

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 [2] that if ${\displaystyle k\geq {\frac {2nR_{L}(x_{0})}{\epsilon }}\log \left({\frac {f(x_{0})-f^{*}}{\epsilon \rho }}\right)}$, where ${\displaystyle R_{L}(x)=\max _{y}\max _{x^{*}\in X^{*}}\{\|y-x^{*}\|_{L}:f(y)\leq f(x)\}}$, ${\displaystyle f^{*}}$ is an optimal solution (${\displaystyle f^{*}=\min _{x\in R^{n}}\{f(x)\}}$), ${\displaystyle \rho \in (0,1)}$ is a confidence level and ${\displaystyle \epsilon >0}$ is target accuracy, then ${\displaystyle Prob(f(x_{k})-f^{*}>\epsilon )\leq \rho }$.

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

${\displaystyle 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}}$

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 ${\displaystyle R^{5}}$. This space has 5 coordinate directions, concretely ${\displaystyle 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).

• Coordinate descent
• Gradient descent
• Mathematical optimization