Block-coordinate descent (BCD) is a popular method for large-scale regularized optimization problems with block-separable structure. However, existing analyses require either a fixed second-order approximation of the smooth part, or restrictions on the subproblem solutions, such as exactness or termination conditions that are difficult to verify except in simple cases. These assumptions essentially confine the quadratic term in the approximation of the smooth part to being diagonal, so the benefits of second-order approximation are mostly lost. Moreover, in contrast to the smooth case, non-uniform sampling has not yet been shown to improve the convergence rate for regularized problems. In this work, we propose an inexact randomized BCD method based on a regularized quadratic subproblem, in which the quadratic term can vary from iteration to iteration (and is thus known as a variable metric'). We provide a detailed convergence analysis. When specialized to the non-regularized case, Nesterov's proposal to improve convergence rate by sampling proportional to the blockwise Lipschitz constants is covered in our framework. Empirical results also show that significant benefits are attainable when a variable quadratic term is used in the subproblem, rather than a fixed term.
In this paper we propose new methods for solving huge-scale optimization problems. For problems of this size, even the simplest full-dimensional vector operations are very expensive. Hence, we propose to apply an optimization technique based on random partial update of decision variables. For these methods, we prove the global estimates for the rate of convergence. Surprisingly enough, for certain classes of objective functions, our results are better than the standard worst-case bounds for deterministic algorithms. We present constrained and unconstrained versions of the method, and its accelerated variant. Our numerical test confirms a high efficiency of this technique on problems of very big size. We present a novel randomized block coordinate descent method for the minimization of a convex composite objective function. The method uses (approximate) partial second-order (curvature) information, so that the algorithm performance is more robust when applied to highly nonseparable or ill conditioned problems. We call the method Flexible Coordinate Descent (FCD). At each iteration of FCD, a block of coordinates is sampled randomly, a quadratic model is formed about that block and the model is minimized approximately inexactly to determine the search direction. An inexpensive line search is then employed to ensure a monotonic decrease in the objective function and acceptance of large step sizes. We present several high probability iteration complexity results to show that convergence of FCD is guaranteed theoretically. Finally, we present numerical results on large-scale problems to demonstrate the practical performance of the method. One of the key steps at each iteration of a randomized block coordinate descent method consists in determining the update to a block of variables. Existing algorithms assume that in order to compute the update, a particular subproblem is solved exactly. In this work, we relax this requirement and allow for the subproblem to be solved inexactly, leading to an inexact block coordinate descent method. Our approach incorporates the best known results for exact updates as a special case. Moreover, these theoretical guarantees are complemented by practical considerations: the use of iterative techniques to determine the update and the use of preconditioning for further acceleration.