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: formula_1 where formula_2 formula_3 is decomposed into formula_4 blocks of variables/coordinates: formula_5 and formula_6 are (simple) convex functions. Example (block decomposition): If formula_7 and formula_8, one may choose formula_9 and formula_10. Example (block-separable regularizers): Algorithm. Consider the optimization problem where formula_16 is a convex and smooth function. Smoothness: By smoothness we mean the following: we assume the gradient of formula_16 is coordinate-wise Lipschitz continuous with constants formula_18. That is, we assume that for all formula_20 and formula_21, where formula_22 denotes the  partial derivative with respect to variable formula_23. Nesterov, and Richtarik and Takac showed that the following algorithm converges to the optimal point: 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 formula_28, where formula_29, formula_30 is an optimal solution (formula_31), formula_32 is a confidence level and formula_33 is target accuracy, then formula_34. Example on particular function. The following Figure shows how formula_35 develops during iterations, in principle. The  problem is Extension to block coordinate setting. One can naturally extend this algorithm not only just to coordinates, but to blocks of coordinates. Assume that we have space formula_37. This space has 5 coordinate directions, concretely formula_38 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).