Accelerated Mini-Batch Stochastic Dual Coordinate Ascent
Stochastic dual coordinate ascent (SDCA) is an effective technique for solving regularized loss minimization problems in machine learning. This paper considers an extension of SDCA under the mini-batch setting that is often used in practice. Our main contribution is to introduce an accelerated mini-batch version of SDCA and prove a fast convergence rate for this method. We discuss an implementation of our method over a parallel computing system, and compare the results to both the vanilla stochastic dual coordinate ascent and to the accelerated deterministic gradient descent method of Nesterov [2007].
This paper extends stochastic dual coordinate ascent 
      (SDCA) to the mini-batch setting, with a proposed algorithm accelerated 
      mini-batch SDCA (ASDCA). Its rate of convergence interpolates between SDCA 
      and accelerated gradient descent (AGD). In addition, a parallel 
      implementation is also proposed where SDCA again interpolates between SDCA 
      and AGD. This interpolation is also demonstrated in experiment. 
      Although the rates of convergence for ASDCA are interesting, a 
      careful look at Table 2 and Figure 1 reveals that ASDCA is nowhere 
      superior to SDCA. I am wondering why it is useful to have such an 
      algorithm. In addition, Section 3 showed much promise of ASDCA on parallel 
      architecture. However, no experiment was done in this setting. Therefore 
      more experimental studies (especially on parallel architecture) are 
      necessary before we can confirm the empirical usefulness/superiority of 
      ASDCA (as indicated by the word ‘Accelerated’ in the title). In 
      response to author's rebuttal: I stick to my position that the paper 
      should show empirical evidence of the advantage of the new algorithm. I 
      think this is an important issue, because in practice the acceleration 
      proffered by parallelization can be highly tricky. The theory part of the 
      paper is surely good. So I won't mind if the paper is 
      accepted.