Doubly Accelerated Stochastic Variance Reduced Dual Averaging Method for Regularized Empirical Risk Minimization
We develop a new accelerated stochastic gradient method for efficiently solving the convex regularized empirical risk minimization problem in mini-batch settings. The use of mini-batches has become a golden standard in the machine learning community, because the mini-batch techniques stabilize the gradient estimate and can easily make good use of parallel computing. The core of our proposed method is the incorporation of our new "double acceleration" technique and variance reduction technique. We theoretically analyze our proposed method and show that our method much improves the mini-batch efficiencies of previous accelerated stochastic methods, and essentially only needs size √ n mini-batches for achieving the optimal iteration complexities for both non-strongly and strongly convex objectives, where n is the training set size. Further, we show that even in non-mini-batch settings, our method achieves the best known convergence rate for non-strongly convex and strongly convex objectives.
The paper proposes a novel doubly accelerated variance reduced dual averaging method for solving the convex regularized empirical risk minimization problem in mini batch settings. The method essentially can be interpreted as replacing the proximal gradient update of APG method with the inner SVRG loop and then introducing momentum updates in inner SVRG loops. Finally to allow lazy updated, primal SVRG is replaced with variance reduce dual averaging. The main difference from AccProxSVRG is the introduction of momentum term at the outer iteration level also. The method requires only O(sqrt{n}) sized mini batches to achieve optimal iteration complexities for both convex and non-convex functions when the problem is badly conditioned or require high accuracy. Experimental results show substantial improvements over state of the art under the above scenario.
Overall, given the theoretical complexity of the paper, it is very well written and explained. Relation with the previous work and differences are clear and elaborative. The reviewer thinks that the paper makes substantial theoretical and algorithmic advances. However, I am giving paper relatively lower rating due to following reasons:
a)  I would like to see more experiments on different datasets especially the effect of conditioning and regularizer.
b)  The accuracy curves are not shown in the experiments. This is important in this case because it seems that major differences between methods are visible only at lower values of the gap and it would be interesting to see if accuracy has saturated by then which will make the practical utility limited.
c) Instead of x axis as gradient evaluations, I would like to see the actual wall clock time there because the constants or O(1) computation in inner loop matters a lot. Especially, the double accelerated equations look computationally more tedious and hence I would like to see the time axis there.
d) Looking at lazy updates in supplementary, I am not sure why accelerated SVRG cannot have lazy updates. Can authors exactly point out the step in detail which will have the issues.