Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function (Q2452370)

The authors further improve, extend and simplify the iteration complexity results of \textit{Yu. Nesterov} [SIAM J. Optim. 22, No. 2, 341--362 (2012; Zbl 1257.90073)], considering the problem of minimizing the sum of a smooth convex and a simple nonsmooth convex block separable function. They focus exclusively on simple (as opposed to accelerated) methods because the per-iteration work of the accelerated algorithm of Nesterov [loc. cit.] on huge scale instances of problems with sparse data is excessive. A randomized block-coordinate descent method for minimizing the sum of a smooth and a simple nonsmooth convex block separable function is developed. This extends the results of Nesterov [loc. cit.], which cover the smooth case. More importantly, in contrast with the aforementioned work in which the author achieves the results by applying the method to a regularized version of the objective function with an unknown scaling factor, it is shown that this is not necessary, thus achieving first true iteration complexity bounds. For a strongly convex function the method converges linearly. Each algorithm of this paper is supported by a high probability iteration complexity result. It is numerically presented that the algorithm is able to solve huge-scale \(\ell_1\) -regularized least squares problems with a billion variables.