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: 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 ) + Ψ ( x ) , {displaystyle F(x)=f(x)+Psi (x),} where Ψ ( x ) = ∑ i = 1 n Ψ i ( x ( i ) ) , {displaystyle Psi (x)=sum _{i=1}^{n}Psi _{i}(x^{(i)}),} x ∈ R N {displaystyle xin R^{N}} is decomposed into n {displaystyle n} blocks of variables/coordinates: x = ( x ( 1 ) , … , x ( n ) ) {displaystyle x=(x^{(1)},dots ,x^{(n)})} and Ψ 1 , … , Ψ n {displaystyle Psi _{1},dots ,Psi _{n}} are (simple) convex functions. Example (block decomposition): If x = ( x 1 , x 2 , … , x 5 ) ∈ R 5 {displaystyle x=(x_{1},x_{2},dots ,x_{5})in R^{5}} and n = 3 {displaystyle n=3} , one may choose x ( 1 ) = ( x 1 , x 3 ) , x ( 2 ) = ( x 2 , x 5 ) {displaystyle x^{(1)}=(x_{1},x_{3}),x^{(2)}=(x_{2},x_{5})} and x ( 3 ) = x 4 {displaystyle x^{(3)}=x_{4}} . Example (block-separable regularizers):