  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
\emph{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.
