An Accelerated Proximal Coordinate Gradient Method
We develop an accelerated randomized proximal coordinate gradient (APCG) method, for solving a broad class of composite convex optimization problems. In particular, our method achieves faster linear convergence rates for minimizing strongly convex functions than existing randomized proximal coordinate gradient methods. We show how to apply the APCG method to solve the dual of the regularized empirical risk minimization (ERM) problem, and devise efficient implementations that avoid full-dimensional vector operations. For ill-conditioned ERM problems, our method obtains improved convergence rates than the state-ofthe-art stochastic dual coordinate ascent (SDCA) method.
The authors propose an accelerated proximal block coordinate descent      algorithm, describe its application to standard regularized loss      minimization problems, and conclude with experiments on a smoothed SVM.      On the question of clarity: I found the paper on the whole difficult to      follow, with the authors showing a marked preference for writing      equations in lieu of explanations. There are also numerous small      grammatical errors.      I'm not aware of other algorithms that are designed to work on      block-coordinate problems (although single-coordinate algorithms are      common enough), and have to question the advantage of this formulation,      aside from being slightly more general. Given that the application      considered in section 4 is single-coordinate (am I correct about this?),      it might simplify the presentation to work from a single-coordinate      formulation, and merely mention that block-coordinate updates are also      possible.      On originality: I'm not familiar enough with the literature to judge. The      stated improvement over the best-known convergence rates is small (not      including the arxiv paper cited as [18]), and I think the authors      shouldn't minimize the difference between converging quickly in the      primal (as the other algorithms mentioned on the bottom of page 6 do) and      in the dual (as APCG, at least for the regularized ERM application). At      least for SVMs, with which I am most familiar, the two objectives are      very different, and fast convergence in the dual does not necessarily      imply fast convergence in the primal.      The experiments appear to show a clear win for APCG over SDCA, and I      agree with the authors that SDCA is a natural baseline. However, I do      have a question about a potential issue: in some of the plots,      particularly on the news20 dataset with small lambda, it appears that      SDCA "levels out" at a higher suboptimality than that found by APCG. This      indicates to me that perhaps at that point SDCA has converged, and has      done so to a slightly higher objective function value due to numerical      issues or implementation differences (the log scale exaggerating such      small discrepancies). Do you have any evidence that this is not the case?      For example, if you can show that your algorithm converges faster than      SDCA in terms of testing classification accuracy, it would simultaneously      assuage fears about a potential numerical issue, and demonstrate that the      use of APCG has practical benefits.      Also did you forget a square root in the equation on lines 190-191?