Recently, many stochastic gradient descent algorithms with variance reduction have been proposed. Moreover, their proximal variants such as Prox-SVRG can effectively solve non-smooth problems, which makes that they are widely applied in many machine learning problems. However, the introduction of proximal operator will result in the error of the optimal value. In order to address this issue, we introduce the idea of extragradient and propose a novel accelerated variance reduced stochastic extragradient descent (AVR-SExtraGD) algorithm, which inherits the advantages of Prox-SVRG and momentum acceleration techniques. Moreover, our theoretical analysis shows that AVR-SExtraGD enjoys the best-known convergence rates and oracle complexities of stochastic first-order algorithms such as Katyusha for both strongly convex and non-strongly convex problems. Finally, our experimental results show that for ERM problems and robust face recognition via sparse representation, our AVR-SExtraGD can yield better performance than state-of-the-art algorithms such as Prox-SVRG and Katyusha. The asynchronous variant of AVR-SExtraGD outperforms KroMagnon and ASAGA, which are the asynchronous variants of SVRG and SAGA, respectively.
This paper proposed a new stochastic algorithm: AVR-ExtraGD. AVR-ExtraGD combines the extended extragradient method proposed in [3] and the accelerated SVRG method in [1][2]. In their experiments, AVR-ExtraGD outperforms [2] in running time for sparse linear regression.
This paper presents their convergence analysis using results in [1][2]. They showed that the proposed algorithm can achieve O(sqrt{kappa n} log (1 / \epsilon)) complexity for strongly convex problem and O(1/sqrt{epsilon}) for convex problem, which are the best results for both cases.
The idea of an accelerated version of variance reduced stochastic extragradient method is novel. However, there are some issues that the authors should address in order for the paper to match the quality of ICLR.
Each step of extragradient approximates the proximal operator x_{k+1} = argmin_x P(x) + 1/(2 eta_k)\|x – x_k\|_2^2, therefore we would expect a faster and more stable convergence from this method. This paper claims that extragradient reduces the gap between the obtained optimal value and the real optimal value, which is confusing. The update of extragradient is actually biased towards x_k. The claim is then discussed in section 3.1 and 3.2 but is not clearly explained. Besides, how this claim is reflected in the convergence result is not discussed. I encourage the authors to clearly elaborate this claim and make relevant remarks after the main theorems.
To better understand the convergence result, it is important to know how extragradient affects the complexity and choice of hyperparameters such as K, eta_1, eta_2, and beta. Such discussion is not in this paper. I suggest the authors to make these aspects clear.
The experiments compare the proposed algorithm with other algorithms by their running time for lasso and elastic-net. The comparisons show the efficiency of the proposed algorithm. However, a more careful experimental design is required to better demonstrate the performance:
1.	For the choice of inner iterations, choosing m=2n for Katyusha actually requires calculating 5n stochastic gradient because each iteration of Katyusha does gradient updates twice.
2.	This paper only presents comparisons of running time. I encourage the authors to also plots comparisons on number of iterations, which will help revealing where the speed up of AVR-ExtraG comes from.
3.	It is also preferable that the author compare with MiG [1], since the proposed algorithm is an extragradient version of [1].
4.	Please at least solve two different optimization programs (e.g. logistic regression, neural network) so any conclusions are not specific to the oddities of a particular program.
The presentation and structure of this paper need to be improved. Here are some suggestions:
1.	 In Section 1, only provide a high-level literature review and then motivate the work. A comprehensive review can come after the introduction.
2.	In Section 4, put all the lemmas into the appendix while giving more intuitions and remarks. 
3.	Issues including notions without pre-definition or reference, typos, and incorrect gramma need to be fixed.
Detailed comments:
1.	From the title, the main application of this work is sparse learning problem. However, how the proposed algorithm benefits sparsity is not discussed. Besides, I suggest the authors to move the asynchronous algorithm in the appendix to the main paper.
2.	The paragraph before section 1.1: lasso and elastic-net are used without citation.
3.	Section 1.1: PGD and SGD are used without citation.
4.	Beginning of page 2: “And” should be “Besides”
5.	“Besides, for accelerating the algorithm and …”: “for accelerating” should be “to accelerate”
6.	Section 1.2: “Nguyen et al. (2017) proposed the idea of extragradient which can be seen as a guide during the process, and introduced it into the optimization problems.” What does “the process” and “it” refers to is unclear.
7.	Section 1.2: the claim extragradient examines the geometry and curvature of the problem is confusing. The geometry of the problem is inspected through a line search step in [3]. However, line search is not discussed in this paper.
8.	Section 1.2: “reduce the gap between the optimal value we get and the real optimal value”, these two kinds optimal values are important notions of this paper but they are not defined.
9.	In Assumption 2, you can refer to Part 2, Section 7 of [5] for the definition of semi-continuity.
10.	“dw is the gradient of the function at w”, what does “the function” refers to?
11.	“APG and Acc-Prox-SVRG” needs citation.
12.	“was proposed to simply the structure of Katyusha”, “simply” should be “simplify”
13.	Section 3.1: “updated with the update rules of MiG”: “with” should be “by”
14.	In the equations of Section 3.2, the equivalent of gradient norm square and function f is incorrect, and the purpose of this equation is unclear.
15.	Section 4.1 Theorem 1: The inequality in theorem 1 is not intuitively related to the convergence rate. I suggest the author to simplify the inequality (For example, Theorem 2.1 in [2]).
16.	The references are not in a uniform format. Conference/Journal names are missing for some references.
17.	One useful reference for this paper is [4], it discussed extragradient for online convex learning.
Additional question:
[5] update the extragradient step by sampling a new stochastic gradient while in this paper the same sample is used twice. How you compare these two approaches in terms of their performance and convergence?
[1] A simple stochastic variance reduced algorithm with fast convergence rates, Zhou et al., 2018.
[2] Katyusha: the first direct acceleration of stochastic gradient methods, Z. Allen-Zhu, 2017
[3] Extragradient method in optimization: Convergence and complexity, T. Nguyen et al., 2017
[4] Online Optimization with Gradual Variations, Chiang et al., 2012
[5] Convex Analysis, R. Rockafella, 1970
[6] Reducing Noise in GAN Training with Variance Reduced Extragradient, Chavdarova et al.  2019