Coordinate Descent Converges Faster with the Gauss-Southwell Rule Than Random Selection

There has been significant recent work on the theory and application of randomized coordinate descent algorithms, beginning with the work of~ Nesterov [SIAM J. Optim., 22(2), 2012], who showed that a