Year: 2019

Abstract:
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.

heading: 1 INTRODUCTION
text: In this paper, we mainly consider the following composite convex optimization problem:
min x∈Rd
{ P (x) def = F (x) +R(x) = 1
n n∑ i=1 fi(x) +R(x)
} (1)
where F (x) : Rd→R is the average of smooth convex component functions fi(x), and R(x) is a relatively simple convex function (but may not be differentiable). In this paper, we use ‖·‖ to denote the standard Euclidean norm, and ‖·‖1 to denote the `1-norm. Moreover, we use P∗ to denote the real optimal value of P (·), and P̂∗ to denote the optimal value obtained by algorithms. This form of optimization problems often appears in machine learning, signal processing, data science, statistics and operations research, and has a wide range of applications such as regularized empirical risk minimization (ERM), sparse coding for image and video recovery, and representation learning for object recognition. Specifically, for a collection of given training examples {(a1, b1), ..., (an, bn)}, where ai ∈ Rd, bi ∈ R (i = 1, 2, ..., n) and ai is a feature vector, while bi is the desired response. When fi(x) = 12 (a T i x−bi)2, we can obtain the ridge regression problem by setting R(x) = λ2 ‖x‖ 2. We also get the Lasso or Elastic-Net problems by setting R(x) =λ‖x‖1 or R(x) = λ22 ‖x‖ 2+λ1‖x‖1, respectively. Moreover, if we set fi(x) = log(1+exp(−bixTai)), we will get the regularized logistic regression problem.

heading: 1.1 RECENT RESEARCH PROGRESS
text: The proximal gradient descent (PGD) method is a standard and effective method for Problem (1), and can achieve linear convergence for strongly convex problems. Its accelerated algorithms, e.g., accelerated proximal gradient (APG) (Tseng (2008); Beck & Teboulle (2009)), attain the convergence rate ofO(1/T 2) for non-strongly convex problems, where T denotes the number of iterations.
In recent years, stochastic gradient descent (SGD) has been successfully applied to many large-scale learning problems, such as training for deep networks and linear prediction (Tong (2004)), because of its significantly lower per-iteration complexity than deterministic methods, i.e., O(d) vs. O(nd). Besides, many tricks for SGD have also been proposed, such as Loshchilov & Hutter (2016). However, the variance of the stochastic gradient may be large due to random sampling (Johnson & Tong (2013)), which leads that the algorithm requires a gradually reduced step size, thus it will converge slow. Even under the strongly convex condition, SGD only achieves a sub-linear convergence rate O(1/T ). Recently, many SGD methods with variance reduction have been proposed. For the case of R(x) = 0, Roux et al. (2012) developed a stochastic average gradient descent (SAG) method, which is a randomized variant of the incremental aggregated gradient method proposed by Blatt et al. (2007). Then stochastic variance reduced gradient (SVRG) (Johnson & Tong (2013)) was proposed, and has been widely introduced into various subsequent optimization algorithms, due to its lower storage space (i.e., O(d)) than that of SAG (i.e., O(nd)). SVRG reduced the variance effectively by changing the estimation of stochastic gradients. The introduction of a snapshot point x̃ mainly has the effect of correcting the direction of gradient descent, and reduces the variance. Later, Konečný & Richtárik (2013) proposed the semi-stochastic gradient descent methods as well as their mini-batch version (Konečný et al. (2014)). And their asynchronous distributed variant (Ruiliang et al. (2016)) is also been proposed later. More recently, Lin & Tong (2014) proposed the Prox-SVRG method, which introduced the proximal operator, and then applied the idea of SVRG to solve the non-smooth optimization problems. However, Prox-SVRG can only be used to solve the strongly convex optimization problems. In order to solve the non-strongly convex problems, Zeyuan & Yuan (2016) proposed the SVRG++ algorithm. Besides, to accelerate the algorithm and reducing the complexity, by combining the main ideas of APG and Prox-SVRG, Nitanda (2014) proposed an accelerated variance reduction proximal stochastic gradient descent (Acc-Prox-SVRG) method, which can effectively reduce the complexity of the algorithm compared to the two basic algorithms. Very recently, Zeyuan (2017) developed a novel Katyusha algorithm which introduced the Katyusha momentum to accelerate the algorithm. With the development of parallel and distributed computing which can effectively reduce computing time and improve performance, Ryu & Wotao (2017) came up with an algorithm called Proximal Proximal Gradient, which combined the proximal gradient method and ADMM (Gabay & Mercier (1976)). Furthermore, it is easy to implement in parallel and distributed environments because of its innovative algorithm structure.

heading: 1.2 OUR MAIN CONTRIBUTIONS
text: We find that due to the introduction of proximal operator, there is a gap between P̂∗ and P∗, and its theoretical derivation can be seen in Appendix A. To address this issue, 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. Intuitively, this additional iteration allows us to examine the geometry of the problem and consider its curvature information, which is one of the most important bottlenecks for first order methods. By using the idea of extragradient, we can get a better result in each inner-iteration. Therefore, the idea of extragradient is our main motivation. In this paper, we propose a novel algorithm for solving non-smooth optimization problems. The main contributions of this paper are summarized as follows.
• In order to improve the result of the gap between P̂∗ and P∗, and achieve fast convergence, a novel algorithm, which combines the idea of extragradient, Prox-SVRG and the trick of momentum acceleration, is proposed, called accelerated variance reduced stochastic extragradient descent (AVR-SExtraGD).
•We provide the convergence analysis of our algorithm, which shows that AVR-SExtraGD achieves linear convergence for strongly convex problems, and the convergence condition in the non-strongly convex case is also given. According to the convergence rate, we can know that AVR-SExtraGD has the same excellent result as the best-known algorithms, such as Katyusha.
• Finally, we show by experiments that the performance of AVR-SExtraGD (as well as VRSExtraGD, which is the basic algorithm of AVR-SExtraGD) is obviously better than the popular algorithm, Prox-SVRG, which confirms the advantage of extragradient. For the widely used accelerated algorithm, Katyusha, the performance of our algorithm is still improved.

heading: 2 RELATED WORK

heading: 2.1 BASIC ASSUMPTIONS
text: We first make the following assumptions to solve the problem (1): Assumption 1 (Smoothness). The convex function F (·) is L-smooth, i.e., there exists a constant L>0 such that for any x, y∈Rd, ‖∇F (x)−∇F (y)‖≤L‖x−y‖. Assumption 2 (Lower Semi-continuity). The regularization function R(·) is a lower semicontinuous function, i.e., ∀x0∈Rd,
lim inf x→x0
R(x)≥R(x0).

heading: But it is not necessarily differentiable or continuous.
text: Assumption 3 (Strong Convexity). In Problem (1), the functionR(·) is µ-strongly convex, i.e., there exists a constant µ>0 such that for all x, y∈Rd, it holds that
R(x) ≥ R(y) + 〈G, x− y〉+ µ 2 ‖x− y‖2, (2)
where G∈∂R(y) which is the set of sub-gradient of R(·) at y.

heading: 2.2 PROX-SVRG AND EXTRAGRADIENT DESCENT METHODS
text: An effective method for solving Problem (1) is Prox-SVRG which improved Prox-FG (Lions & Mercier (1979)) and Prox-SG (Langford et al. (2009)) by introducing the stochastic gradient and combining the idea of SVRG, respectively. For strongly convex problems, Prox-SVRG can reach linear convergence with a constant step size, and its main update rules are
∇̃fik(xk−1) = ∇fik(xk−1)−∇fik(x̃) +∇F (x̃); xk = ProxRη (xk−1 − η∇̃fik(xk−1)), (3)
where x̃ is the snapshot point used in SVRG, ∇̃fik(xk−1) is the variance reduced stochastic gradient estimator, and ProxRη (·) is the proximal operator. Although Prox-SVRG can converge fast, because of proximal operator, the final solution has the deviation, which makes the solution inaccurate, thus Prox-SVRG still needs to be further improved, which is our important motivation.
The extragradient method was first proposed by Korpelevič (1976). It is a classical method for solving variational inequality problems, and it generates an estimation sequence by using two projection gradients in each iteration. By combining this idea with some first-order descent methods, Nguyen et al. (2017) proposed an extended extragradient method (EEG) which can effectively solve the problem (1), and can also solve relatively more general problems as follows:
min x∈Rd
{ P (x) def = F (x) +R(x) } where F (x) is not necessarily composed by multiple functions fi(x). Unlike the classical extragradient method, EEG uses proximal gradient instead of orthogonal projection in each iteration. The main update rules of EEG are
yk = ProxRsk(xk − sk∇F (xk)); xk+1 = Prox R αk (xk − αk∇F (yk)),
where sk and αk are two step sizes. From the update rules of EEG, we can see that in each iteration, EEG needs to calculate two gradients, which will definitely slow down the algorithm. Therefore, the algorithm needs to be further accelerated by an efficient technique.

heading: 2.3 MOMENTUM ACCELERATION AND MIG
text: Firstly, we introduce the momentum acceleration technique whose main update rules are
vdwt = βvdwt−1 + (1− β)dwt; wt = wt−1 − αvdwt ,
where dw is the gradient of the objective function at w, β is a parameter, and α is a step size. The update rules take not only the gradient of the current position, but also the gradient of the past position into account, which makes the final descent direction of wt after using momentum
Algorithm 1 AVR-SExtraGD Input: Initial vector x0, the number of epochs S, the number of iterations m per epoch, the step
sizes η1, η2, momentum parameter β, and the set K. Initialize: x̃0 = x10 = x0, ρ = 1+ηµ.
1: for s = 1, 2, . . . , S do 2: Compute∇F (x̃s−1); 3: βs = β (SC) or βs = 2s+4 (non-SC); 4: for k = 1, 2, . . . ,m do 5: Pick ik uniformly at random from {1, ..., n}; 6: if k ∈ K then 7: xsk−1/2 = Prox R η1 ( xsk−1 − η1∇̃fik(βsxsk−1 + (1−βs)x̃s−1) ) ;
8: xsk = Prox R η2 ( xsk−1/2 − η2∇̃fik(βsx s k−1/2 + (1−βs)x̃ s−1) )
; 9: else
10: xsk = Prox R η1(x s k−1 − η1∇̃fik(βsxsk−1 + (1−βs)x̃s−1)); 11: end if 12: end for 13: x̃s = βs( ∑m k=1 ρ k−1)−1 ∑m k=1 ρ k−1 x s k−1/2+x s k 2 +(1−βs)x̃ s−1 (SC)
or x̃s = βsm ∑m k=1 xsk−1/2+x s k 2 +(1−βs)x̃ s−1 (non-SC);
14: xs+10 = x s m; 15: end for Output: x̃S .
reduce the oscillation of descent, thus this method can effectively accelerate the convergence of the algorithm.
According to the Nesterov’s momentum, lots of accelerated algorithms were proposed, such as APG and Acc-Prox-SVRG. Later, Zeyuan (2017) proposed Katyusha to further accelerate the algorithm, and MiG (Kaiwen et al. (2018)) was proposed to simplify the structure of Katyusha, and the momentum acceleration of MiG is embodied in each iteration as follows:
ysk−1 = βsx s k−1 + (1− βs)x̃s−1.
Moreover, it is easy to get that the oracle complexity of MiG is less than that of Prox-SVRG and APG, which means that MiG can effectively accelerate the original Prox-SVRG algorithm. Therefore, we can also use this acceleration technique to accelerate our algorithm and address the issue of slow convergence due to the calculations of two different gradients.

heading: 3 OUR AVR-SEXTRAGD METHOD
text: We note that EEG requires computing two full gradients in each iteration, which will take a lot of time for large-scale machine learning problems. Therefore, we first consider and propose the stochastic variant of the algorithm, namely stochastic extragradient descent (SExtraGD), to reduce the per-iteration computational complexity, and further propose an efficient variance reduced stochastic extragradient descent (VR-SExtraGD) algorithm. Their main update rules and the detailed algorithm of VR-SExtraGD can be found in Appendix C.
On the basis of VR-SExtraGD, we refer to the momentum acceleration technique proposed in MiG, and propose an innovative accelerated variance reduced stochastic extragradient descent algorithm, called AVR-SExtraGD. It is used to solve non-smooth (both SC and non-SC) optimization problems. To further accelerate the algorithm and address the issue of slow convergence speed caused by two gradients in each inner-iteration, only part of the iterations are updated by extragradient descent. Our AVR-SExtraGD algorithm is outlined in Algorithm 1.
Firstly, we give some explanation for Algorithm 1. For our AVR-SExtraGD, we need to compute a full gradient of F (x). And Step 3 in Algorithm 1 is the selection of momentum parameter. Step 6 to Step 8 are the update rule of AVR-SExtraGD, and Step 9 is the update rule of MiG. Here we only use AVR-SExtraGD in the set K. Step 13 is the formulation of the snapshot point. Finally, we
give the set of the start point of next inner-iteration in Step 14. Moreover, our output is the snapshot point of the last outer iteration.
And for our AVR-SExtraGD algorithm, we have the following remarks.
• Following the requirement of step sizes in EEG, the step sizes in our algorithms also need to satisfy similar conditions. After combining all the conditions, we get the conditions: η1≤ 12L , η2≤ 1 L−η1. • In AVR-SExtraGD, we use one more trick to speed up the algorithm, that is, only part of the iterations (i.e., when k ∈K) are updated by extragradient descent, and the rest of the iterations are still updated by the update rules of MiG. For different problems and different data sets, we manually adjust the choice of K, and the details can be seen in Section 5.3.
• For the momentum parameter β, when P (·) is a strongly convex function, we can set β as a constant which is generally set as 0.9. And β is also set as 1− √ µη2
1+ √ µη2 in Acc-Prox-SVRG, while we set β = 0.9 in our AVR-SExtraGD. However, when P (·) is non-strongly convex, the value of β in each iteration is no longer fixed. We set βs as a decreasing sequence, which satisfies 1β2s−1 ≥ 1−βs β2s . Particularly, in AVR-SExtraGD, we set βs= 2s+4 , which satisfies the inequality defined above.
As we all know, for the general GD method, the iterate xk in each iteration eventually converges to the real optimal point of the function, so there is no error in the final optimal value. Therefore, the proximal operator will introduce a bad result in convergence.
To adress this issue, we introduce the idea of extragradient, which takes one more proximal operator than Prox-SVRG. And according to the idea of extragradient, we know that the update structure of EEG can make use of the curvature information of the objective function. Although we change the original EEG into a stochastic version, the advantage of the extragradient structure is still retained to some degree, and thus our algorithm can get a better result than the algorithm without extragradient.That is, although the method of extragradient can not directly reduce the gap of the optimal value, it can improve the bad result brought by the gap, and obtain a better result after every inner loop, Thus, AVR-SExtraGD can improve the accuracy of the algorithm.
In summary, our AVR-SExtraGD method combines the advantage of Prox-SG for solving nonsmooth optimization problems, the advantage of EEG, and the trick of SVRG to reduce the variance of stochastic gradient. And it is further accelerated by introducing the momentum acceleration used in MiG. Therefore, our algorithm has more advantages than the basic algorithms mentioned above.

heading: 4 CONVERGENCE ANALYSIS
text: In this section, we analyze the convergence properties of AVR-SExtraGD under strongly convex and non-strongly convex conditions. For convenience analysis, we use ∇̃ikF (·) to denote ∇̃fik(·), that defined in (3) in the analysis of AVR-SExtraGD. We give some key lemmas, which are important to prove the convergence of AVR-SExtraGD in Appendix B, and all the proofs of our lemmas and theorems in this section are also given in Appendix B.

heading: 4.1 FOR SC PROBLEMS
text: For strongly convex problems, the linear convergence of AVR-SExtraGD can be guaranteed by the following theorem. Theorem 1 (Strongly Convex). Suppose that Assumptions 1, 2 and 3 hold, and let x∗ = arg minx P (x). In addition, assume η1 = η2 = η > 0 and Lβ+ Lβ1−β ≤ 1 η . Then, by appropriately choosing η, β and m= Θ(n), Algorithm 1 achieves an -additive error with following oracle complexities in expectation:{
O( √ κn log P (x0)−P (x∗) ), if
m κ ≤ 3 4 ,
O(n log P (x0)−P (x∗) ), if m κ > 3 4 ,
which also means that for SC problems, the oracle complexity of Algorithm 1 is O((n +√ κn) log P (x0)−P (x∗) ).
This result means that for strongly convex problems, AVR-SExtraGD achieves linear convergence and enjoys the best-known oracle complexity of stochastic first-order algorithms, such as Katyusha.

heading: 4.2 FOR NON-SC PROBLEMS
text: The convergence of AVR-SExtraGD for solving non-SC problems can be guaranteed by the following theorem. Theorem 2 (Non-Strongly Convex). Suppose that Assumptions 1 and 2 hold, and let x∗ = arg minx P (x). In addition, assume η1 = η2 = η = 1Lα > 0 and 1−βs− 1 α−1 ≥ 0, where α is a constant. Then by setting βs= 2s+4 , we have
E[P (x̃S)−P (x∗)]≤ 4(1−β1)
(S+4)2β21 (P (x0)−P (x∗))+
Lα
(S+4)2m ‖x0−x∗‖2,
which also means that when we choose m= Θ(n), Algorithm 1 achieves the following oracle complexity in expectation: O(n √ P (x0)−P (x∗) + √ nL‖x0−x∗‖2 ).
The result shows that AVR-SExtraGD enjoys the same oracle complexity as Katyusha and MiG, which is close to the best-known complexity in this case (i.e., O(n log 1 + √ nL )). In addition, we
also analyze the convergence of VR-SExtraGD and give and prove the related lemmas and theorems to guarantee its convergence, which can be found in Appendix D.

heading: 5 EXPERIMENTS
text: In this section, we evaluate the performance of AVR-SExtraGD and compare it with its counterparts including Prox-SVRG and Katyusha on real-world data sets, whose information is shown as Table 2 in Appendix E.
Besides, for these real-world data sets, we consider the two common problem models: Lasso and Elastic-Net. We also apply our algorithm to face recognition tasks and compare it with the compared algorithms. Next, we give the setup of the related parameters as follows:
• Regularization Parameters: The regularization parameters for real-world datasets are shown in Table 2.
• The Number of Inner-Iteration: The number of inner-iterations of Katyusha and Prox-SVRG is usually set asm=2n. Our algorithm adds one more gradient calculation in each inner-iteration than Prox-SVRG, and for an equal complexity of each epoch, we set m=n in AVR-SExtraGD, so that in each epoch, all the three algorithms require calculating 3n stochastic gradients. What’s more, the reasonableness of such a setting can be found in Sebbouh et al. (2019).
• Step Sizes: We set our step sizes as: η1 = 25L , η2 = 3 5L . We note that the selected step sizes do not satisfy the conditions requested in the remark of Section 3. Nevertheless, we can see from the experimental results that our algorithm still converges well, which means that in practice experiments, we can choose larger step sizes to improve the convergence speed.
For fair comparison, we implemented all the methods in C++ with a Matlab interface, and performed all the experiments on a PC with an Intel i7-7700 CPU and 32GB RAM.

heading: 5.1 RESULTS OF LASSO, ELASTIC-NET AND LOGISTIC REGRESSION
text: In this part, we consider three common problems, including Lasso, Elastic-Net and the `1-norm regularized logistic regression, whose models can be found in Appendix E.
Figure 1 shows the performance of all the algorithms for Lasso and Elastic-Net on all the data sets. For running time, our AVR-SExtraGD obviously outperforms Prox-SVRG and Kayusha, which shows the faster convergence speed of AVR-SExtraGD than Katyusha, and justifies that the extragradient and the momentum acceleration are able to improve Prox-SVRG efficiently. Moreover, for
the two problems, we propose the asynchronous sparse variant of AVR-SExtraGD by bringing our algorithm into a sparse asynchronous framework and compare its performance with KroMagnon (Mania et al. (2015)) and ASAGA (Leblond et al. (2016)) on rcv1 and real-sim, as shown in Table 2. The results are shown in Figure 2, which verify that the asynchronous variant of AVR-SExtraGD significantly outperforms the variants of SVRG (i.e., KroMagnon) and SAGA (Defazio et al. (2014)) (i.e., ASAGA) in terms of iterations and running time. Then, for a more comprehensive comparison, we compare the performance of more algorithms for Lasso and the `1-norm regularized logistic regression on a9a and Covtype, and the results are shown as Figure 4 and Figure 5 in Appendix E.

heading: 5.2 RESULTS ON FACE RECOGNITION
text: We also apply our AVR-SExtraGD as well as Prox-SVRG and Katyusha to robust face recognition via sparse representation (John et al. (2009)) on the AR and Yale. We set the loss function
in the training process as the same function as the Lasso and Elastic-Net problems. For approximately equal time, the number of outer loops is 200 for Prox-SVRG and AVR-SExtraGD, and 50 for Katyusha. In order to compare the results reasonably, we implement all the algorithms for 20 times and get the average and standard deviation of recognition rates, as shown in Table 1.
The results in Table 1 show that the recognition rate of AVR-SExtraGD is significantly higher than other algorithms on both the AR and Yale data sets. This means that our AVR-SExtraGD can learn a more efficient representation for face recognition.

heading: 5.3 THE SELECTION OF K IN AVR-SEXTRAGD
text: For the selection of K, we do some relevant experiments as examples. We choose different K to solve Lasso problem by our algorithm, and get the results as shown in Figure 3.
where, K = n means that the extragradient is calculated every integer multiple of n (n ∈ {1, 8, 25, 75, 250}). For a9a, when the extragradient is used every time, the function value decreases faster with respect to the number of iterations, but the result is not good for running time. Thus, for a9a, we choose K=25. As for Covtype, obviously, K=1 is the best choice.

heading: 6 CONCLUSIONS AND FUTURE WORK
text: In this paper, we mainly considered the non-smooth optimization problem in large-scale and highdimensional settings. By introducing the idea of extragradient and momentum acceleration, we improved the classical Prox-SVRG and then proposed a novel algorithm, called AVR-SExtraGD. From our theoretical analysis, we can know that AVR-SExtraGD attains linear convergence for SC problems, and achieves the same oracle complexity as Katyusha, which is the best-known one of stochastic first-order algorithms in both SC and non-SC cases. Finally, the experimental results showed that AVR-SExtraGD improved the result of the gap of the optimal value introduced by proximal operator, and thus improved the accuracy of solutions and convergence speed, which confirmed the efficiency of extragradient and momentum acceleration. For future work, we can extend the ideas introduced in this paper to many existing proximal algorithms, including Prox-AFG (Beck & Teboulle (2009)), Prox-SAG (Schmidt et al. (2017)) and Prox-SDCA (Shalev-Shwartz & Tong (2012); Shalev-shwartz & Tong (2014)) which is a proximal variant of SDCA (Shalev-Shwartz & Tong (2013)), and it will certainly improve the performance of these algorithms. Moreover, we can also rewrite our algorithm into the form of mini-batch, whose computation of gradient evaluations can be parallelized (Agarwal & Duchi (2011); Dekel et al. (2012)).

heading: APPENDIX

heading: A THE ERROR OF OPTIMAL VALUE
text: In this part, we prove that Prox-FG will cause the deviation of the optimal value. Based on its update rules, we can explain why Problem (1) can be solved by proximal operators and find out the reason for the introduction of the error. According to Prox-FG, we have
xk = ProxRηk(xk−1 − ηk∇F (xk−1))
= arg min u∈Rd {R(u) + 1 2ηk ‖u− (xk−1 − ηk∇F (xk−1))‖2}
= arg min u∈Rd {R(u) + ηk 2 ‖∇F (xk−1)‖2 +∇F (xk−1)T (u− xk−1) + 1 2ηk ‖u− xk−1‖2}
= arg min u∈Rd
{R(u) + F (xk−1) +∇F (xk−1)T (u− xk−1) + 1
2ηk ‖u− xk−1‖2}
≈ arg min u∈Rd {F (u) +R(u)}.
The final approximation is obtained by the second-order Taylor expansion of F (u) at xk−1. From the above analysis, we can see that when using proximal operators to solve the problems with the `1-norm regularization, the iterate xk in each iteration is an estimation of the optimal point, not the real optimal point. Therefore, in the last iteration, the final output point is also an estimation of P∗, which results in the deviation of the optimal value.

heading: B PROOFS OF AVR-SEXTRAGD

heading: B.1 KEY LEMMAS
text: Lemma 1. If two vectors xk, xk−1∈Rd satisfy the following equality,
xk = arg min x { 1 2η ‖x−xk−1‖2+〈∇̃ikF (xk−1), x〉+R(x)}
with a constant vector ∇̃ikF (xk−1) and a convex function R(·), then for ∀u∈Rd, we have
〈∇̃ikF (xk−1), xk−u〉 ≤ − 1
2η ‖xk−1−xk‖2+
1
2η ‖xk−1−u‖2−
1
2η ‖xk−u‖2+R(u)−R(xk).
Moreover, if R(·) is µ-strongly convex, the above inequality becomes
〈∇̃ikF (xk−1), xk−u〉≤− 1
2η ‖xk−1−xk‖2+
1
2η ‖xk−1−u‖2−
1+ηµ
2η ‖xk−u‖2+R(u)−R(xk).
Lemma 2 (Variance Bound). Suppose each function fi(·) is Li-smooth, let ∇̃ikF (xk−1) =
∇ikF (xk−1)−∇ikF (x̃s−1)+∇F (x̃s−1), which is the gradient estimation operator used in Algo-
rithm 1. Then the following inequality holds
E‖∇F (xk−1)−∇̃ikF (xk−1)‖2 ≤ 2L(F (x̃s−1)−F (xk−1)−〈∇F (xk−1), x̃s−1−xk−1〉).
The detailed proof of Lemma 1 can be found in Kaiwen et al. (2018), and the proof of Lemma 2 can be seen in Zeyuan (2017), and thus we omit the proofs here. Next, we give the proofs of Theorems 1 and 2.

heading: B.2 PROOF OF THEOREM 1
text: Proof. In this part, we consider one particular epoch and omit the number of outer iteration s (except
x̃s−1 and x̃s). We assume the parameters η and β satisfy the following inequality,
Lβ + Lβ 1−β ≤ 1 η . (4)
Let x̂k−1 =βxk−1+(1−β)x̃s−1, x̂k−1/2 =βxk−1/2+(1−β)x̃s−1. Thus, we can obtain x̂k−1/2−x̂k−1 =
β(xk−1/2−xk−1). Thus, according to the L-smoothness of F (·), we can obtain
P (x̂k−1/2)≤βR(xk−1/2)+(1−β)R(x̃s−1)+F (x̂k−1)+〈∇̃ikF (x̂k−1), β(xk−1/2−xk−1)〉
+ Lβ2
2 ‖xk−1/2−xk−1‖2+〈∇F (x̂k−1)−∇̃ikF (x̂k−1), β(xk−1/2−xk−1)〉.
Then by using (4), we have
1 β P (x̂k−1/2)≤R(xk−1/2)+ 1−β β R(x̃s−1)+ 1 β F (x̂k−1)+〈∇̃ikF (x̂k−1), xk−1/2−xk−1〉
+ 1
2η ‖xk−1/2−xk−1‖2−
Lβ
2(1−β) ‖xk−1/2−xk−1‖2
+〈∇F (x̂k−1)−∇̃ikF (x̂k−1), xk−1/2−xk−1〉.
According to Lemma 1 with xk−1, xk=xk−1/2, u=x∗ and using the Young’s inequality to expand
〈∇F (x̂k−1)−∇̃ikF (x̂k−1), xk−1/2−xk−1〉 with the parameter θ > 0 and taking expectation with
respect to the sample ik, we have
1 β EP (x̂k−1/2)≤R(x∗)+ 1−β β R(x̃s−1)+ 1 β F (x̂k−1)+E〈∇̃ikF (x̂k−1), x∗−xk−1〉
+ 1
2η ‖x∗−xk−1‖2−
1+ηµ
2η E‖x∗−xk−1/2‖2−
Lβ
2(1−β) E‖xk−1/2−xk−1‖2
+ θ
2 E‖xk−1/2−xk−1‖2+
1
2θ E‖∇F (x̂k−1)−∇̃ikF (x̂k−1)‖2.
We set θ= Lβ1−β >0 and apply Lemma 2, then
1 β EP (x̂k−1/2)≤R(x∗)+ 1−β β R(x̃s−1)+ 1 β F (x̂k−1)
+ 1
2η ‖x∗−xk−1‖2−
1+ηµ
2η E‖x∗−xk−1/2‖2+ 1−β β [F (x̃s−1)−F (x̂k−1)]
+E〈∇̃ikF (x̂k−1), x∗+ 1−β β x̃s−1− 1 β x̂k−1+ 1−β β (x̂k−1−x̃s−1)〉
≤R(x∗)+ 1−β β R(x̃s−1)+ 1 β F (x̂k−1)
+ 1
2η ‖x∗−xk−1‖2−
1+ηµ
2η E‖x∗−xk−1/2‖2+ 1−β β [F (x̃s−1)−F (x̂k−1)]
+ 1
β E〈∇̃ikF (x̂k−1), βx∗+(1−β)x̂k−1−x̂k−1〉
≤R(x∗)+ 1−β β R(x̃s−1)+ 1 β F (x̂k−1)
+ 1
2η ‖x∗−xk−1‖2−
1+ηµ
2η E‖x∗−xk−1/2‖2+ 1−β β [F (x̃s−1)−F (x̂k−1)]
+ 1
β F (βx∗+(1−β)x̂k−1)−
1 β F (x̂k−1)
≤R(x∗)+ 1−β β R(x̃s−1)+ 1 β F (x̂k−1)+ 1−β β [F (x̃s−1)−F (x̂k−1)]+F (x∗)
+ 1−β β F (x̂k−1)− 1 β F (x̂k−1)+ 1 2η ‖x∗−xk−1‖2− 1+ηµ 2η E‖x∗−xk−1/2‖2
= 1−β β P (x̃s−1)+P (x∗)+ 1 2η ‖x∗−xk−1‖2− 1+ηµ 2η E‖x∗−xk−1/2‖2.
The third inequality holds due to E[∇̃ikF (x̂k−1)] =∇F (x̂k−1) and the convexity of F (·), then we
get
1 β E[P (x̂k−1/2)−P (x∗)]≤ 1−β β [P (x̃s−1)−P (x∗)]+ 1 2η ‖x∗−xk−1‖2− 1+ηµ 2η E‖x∗−xk−1/2‖2.
Moreover, because x̂k−1 =βxk−1+(1−β)x̃s−1, we can obtain x̂k=βxk+(1−β)x̃s−1. Thus, it is
not hard to know
1 β E[P (x̂k)−P (x∗)]≤ 1−β β [P (x̃s−1)−P (x∗)]+ 1 2η ‖x∗−xk−1/2‖2− 1+ηµ 2η E‖x∗−xk‖2.
We set yk=β xk−1/2+xk 2 +(1−β)x̃ s−1 and it is obvious that 12η− 1+ηµ 2η ≤0, then we have
1 β E[P (yk)−P (x∗)]≤ 1−β β [P (x̃s−1)−P (x∗)]+ 1 4η ‖x∗−xk−1‖2− 1+ηµ 4η E‖x∗−xk‖2. (5)
By setting ρ=1+ηµ and summing (5) over k=1, ...,m with increasing weight ρk−1, we have
1
β m∑ k=1 ρk−1E[P (yk)−P (x∗)]+ ρm 4η ‖xm−x∗‖2≤ 1−β β m∑ k=1 ρk−1[P (x̃s−1)−P (x∗)]+ 1 4η ‖x0−x∗‖2.
Because, for SC problems, we set x̃s=( ∑m k=1 ρk−1) −1∑m k=1 ρ k−1yk in Algorithm 1 , we have
1
β m∑ k=1 ρk−1E[P (x̃s)−P (x∗)]+ ρm 4η ‖xsm−x∗‖2≤ 1−β β m∑ k=1 ρk−1[P (x̃s−1)−P (x∗)]+ 1 4η ‖xs0−x∗‖2.
Then, according to the convergence analysis for SC problems in (Kaiwen et al. (2018)), we can get
a similar result. That is, for the case with mκ ≤ 3 4 , we set η=
√ 1 3µmL , β= √ m 3κ ≤ 1 2 , and m=Θ(n),
then we can obtain
E[P (x̃S)−P (x∗)]≤ ( O(1+ √ 1
3nκ )
)−Sm ·O(P (x̃0)−P (x∗)).
We note that x̃0 =x0, so we get
E[P (x̃S)−P (x∗)]≤ ( O(1+ √ 1
3nκ )
)−Sm ·O(P (x0)−P (x∗)),
which implies that the oracle complexity in this case to achieve an -additive error is
O( √ κn log P (x0)−P (x∗) ). However, for the case with
m κ > 3 4 , we set η= 2 3L , β= 1 2 and m= Θ(n),
then we can obtain
E[P (x̃S)−P (x∗)]≤ ( 2
3
)S ·O(P (x̃0)−P (x∗)).
We know that x̃0 =x0, so we have
E[P (x̃S)−P (x∗)]≤ ( 2
3
)S ·O(P (x0)−P (x∗)),
which implies that the oracle complexity of AVR-SExtraGD in this case is O ( n log P (x0)−P (x∗) ) .

heading: B.3 PROOF OF THEOREM 2
text: Proof. In this part, we also omit the number of outer iteration s (except x̃s−1 and x̃s). Due to
x̂k−1/2 =βxk−1/2+(1−β)x̃s−1, we can get
P (x̂k−1/2)=P (βxk−1/2+(1−β)x̃s−1)=R(βxk−1/2+(1−β)x̃s−1)+F (x̂k−1/2).
From the convexity of R(·) and L-smoothness of F (·), we obtain
P (x̂k−1/2)≤βR(xk−1/2)+(1−β)R(x̃s−1)+F (x̂k−1)+〈∇̃ikF (x̂k−1), β(xk−1/2−xk−1)〉
+ Lβ2
2 ‖xk−1/2−xk−1‖2+〈∇F (x̂k−1)−∇̃ikF (x̂k−1), β(xk−1/2−xk−1)〉
≤βR(xk−1/2)+(1−β)R(x̃s−1)+F (x̂k−1)+〈∇̃ikF (x̂k−1), β(xk−1/2−xk−1)〉
+ Lαβ2
2 ‖xk−1/2−xk−1‖2+
1
2L(α−1) ‖∇F (x̂k−1)−∇̃ikF (x̂k−1)‖2,
where the second inequality holds by using the Young’s inequality with the parameter L(α−1),
where α is a small constant. After applying Lemma 1 and taking expectation with respect to the
sample ik, we have
EP (x̂k−1/2)≤βR(x∗)+(1−β)R(x̃s−1)+F (x̂k−1)+E〈∇̃ikF (x̂k−1), β(x∗−xk−1)〉
+ Lαβ2
2 (‖x∗−xk−1‖2−E‖x∗−xk−1/2‖2)
+ 1
2L(α−1) E‖∇F (x̂k−1)−∇̃ikF (x̂k−1)‖2
≤βR(x∗)+(1−β)R(x̃s−1)+F (x̂k−1)+E〈∇̃ikF (x̂k−1), β(x∗−xk−1)〉
+ Lαβ2
2 (‖x∗−xk−1‖2−E‖x∗−xk−1/2‖2)
+ 1
α−1 [F (x̃s−1)−F (x̂k−1)+E〈∇̃ikF (x̂k−1), x̂k−1−x̃s−1〉]
≤βR(x∗)+(1−β)R(x̃s−1)+F (x̂k−1)+ 1
α−1 [F (x̃s−1)−F (x̂k−1)]
+E〈∇̃ikF (x̂k−1), βx∗+(1−β)x̃s−1−x̂k−1+ 1 α−1 (x̂k−1−x̃s−1)〉
+ Lαβ2
2 (‖x∗−xk−1‖2−E‖x∗−xk−1/2‖2)
≤βR(x∗)+(1−β)R(x̃s−1)+F (x̂k−1)+ 1
α−1 [F (x̃s−1)−F (x̂k−1)]
+F (βx∗+(1−β− 1
α−1 )x̃s−1+
1
α−1 x̂k−1)−F (x̂k−1)
+ Lαβ2
2 (‖x∗−xk−1‖2−E‖x∗−xk−1/2‖2)
≤βR(x∗)+(1−β)R(x̃s−1)+F (x̂k−1)+ 1
α−1 [F (x̃s−1)−F (x̂k−1)]
+βF (x∗)+(1−β− 1
α−1 )F (x̃s−1)+
1
α−1 F (x̂k−1)−F (x̂k−1)
+ Lαβ2
2 (‖x∗−xk−1‖2−E‖x∗−xk−1/2‖2)
=(1−β)P (x̃s−1)−βP (x∗)+ Lαβ2
2 (‖x∗−xk−1‖2−E‖x∗−xk−1/2‖2).
The second inequality holds due to Lemma 2. The reasons why the fourth inequality holds are
E[∇̃ikF (x̂k−1)]=∇F (x̂k−1) and the convexity of F (·). Besides, we need to assume 1−β− 1α−1≥0
in this step. Then, we get
E[P (x̂k−1/2)−P (x∗)]≤(1−β)[P (x̃s−1)−P (x∗)]+ Lαβ2
2 (‖x∗−xk−1‖2−E‖x∗−xk−1/2‖2).
Moreover, because x̂k−1 =βxk−1+(1−β)x̃s−1, we can obtain x̂k=βxk+(1−β)x̃s−1. Thus, it is
not hard to know
E[P (x̂k)−P (x∗)]≤(1−β)[P (x̃s−1)−P (x∗)]+ Lαβ2
2 (‖x∗−xk−1/2‖2−E‖x∗−xk‖2).
Let yk=β xk−1/2+xk 2 +(1−β)x̃ s−1, we have
E[P (yk)−P (x∗)]≤(1−β)[P (x̃s−1)−P (x∗)]+ Lαβ2
4 (‖x∗−xk−1‖2−E‖x∗−xk‖2).
That is,
1
β2 E[P (yk)− P (x∗)]≤ (1−β) β2 [P (x̃s−1)−P (x∗)]+ Lα 4 (‖x∗−xk−1‖2−E‖x∗−xk‖2).
Since we have x̃s = βm ∑m k=1 xk−1/2+xk 2 +(1−β)x̃ s−1 = 1m ∑m k=1 yk in Algorithm 1, and then by
summing the previous inequality over k=1, ...,m and according to xs+10 =x s m, we obtain
1
β2s E[P (x̃s)−P (x∗)]≤ (1−βs) β2s [P (x̃s−1)−P (x∗)]+ Lα 4m (‖x∗−xs0‖2−‖x∗−xs+10 ‖2).
We set βs= 2s+4 and can easily obtain 1 β2s−1 ≥ 1−βsβ2s . Then by summing the previous inequality over
s=1, ..., S, we can get
1
β2S E[P (x̃S)−P (x∗)]≤ (1−β1) β21 [P (x̃s−1)−P (x∗)]+ Lα 4m (‖x∗−x10‖2−‖x∗−xSm‖2).
Then we have
E[P (x̃S)−P (x∗)]≤ 4(1−β1)
(S+4)2β21 (P (x̃0)−P (x∗))+
Lα
(S+4)2m ‖x̃0−x∗‖2,
which holds because ‖x∗−xSm‖2≥0. We note that x̃0 =x10 =x0, so we get
E[P (x̃S)−P (x∗)]≤ 4(1−β1)
(S+4)2β21 (P (x0)−P (x∗))+
Lα
(S+4)2m ‖x0−x∗‖2.
In other words, by choosing m=Θ(n), the total oracle complexity is
O ( n √ P (x0)−P (x∗) + √ nL‖x0−x∗‖2 ) .
Finally, we finished the convergence analysis of AVR-SExtraGD. In our Algorithm 1, only part of the iterations are updated by extragradient descent, and the other iterations are updated with the update rules of MiG. And we know both MiG and AVR-SExtraGD can make the objective function converge to P∗. Therefore, the method in Algorithm 1 will not affect the results and can accelerate the algorithm.
Algorithm 2 VR-SExtraGD Input: Initial vector x0, the number of epochs S, the number of iterations m per epoch, and the
step sizes η1, η2. Initialize: x̃0 = x0.
1: for s=1, 2, . . . , S do 2: µ̃s−1 =∇F (x̃s−1); 3: xs0 = x̃ s−1 (SC) or xs0 =x s−1 m (non-SC); 4: for k=1, 2, . . . ,m do 5: Pick ik uniformly at random from {1, ..., n}; 6: ∇̃fik(xsk−1)=∇fik(xsk−1)−∇fik(x̃s−1)+µ̃s−1; 7: xsk−1/2 =Prox R η1(x s k−1 − η1∇̃fik(xsk−1)); 8: ∇̃fik(xsk−1/2)=∇fik(x s k−1/2)−∇fik(x̃
s−1)+µ̃s−1; 9: xsk=Prox R η2(x s k−1/2−η2∇̃fik(x s k−1/2));
10: end for 11: x̃s= 1m ∑m k=1 x s k; 12: end for

heading: Output: x̃S .

heading: C SEXTRAGD AND VR-SEXTRAGD
text: Based on the update rules of EEG, we first consider and propose the stochastic variant of the algorithm, namely the stochastic extragradient descent (SExtraGD) algorithm, and its variance reduced variant called variance reduced stochastic extragradient descent (VR-SExtraGD), whose update rules can be formulated as follows:
• The update rules of SExtraGD: xk−1/2 = ProxRη1(xk−1 − η1∇fik(xk−1)) ; xk = Prox R η2 ( xk−1/2 − η2∇fik(xk−1/2) ) . • The update rules of VR-SExtraGD:
xk−1/2 = ProxRη1 ( xk−1 − η1∇̃fik(xk−1) ) ; xk = ProxRη2 ( xk−1/2 − η2∇̃fik(xk−1/2) ) ,
where ∇̃fik(·) is the gradient estimation defined in (3). We note that one difference between these two algorithms and EEG is that we change xk−1 in Step two to xk−1/2, which will be beneficial to our theoretical analysis, but will not cause any major change to the results of the algorithms. Thus, we propose the stochastic extragradient descent algorithms, called SExtraGD and VR-SExtraGD, for solving non-smooth (both SC and non-SC) problems. In addition, the detailed process of VR-SExtraGD is shown as outlined in Algorithm 2.

heading: D CONVERGENCE ANALYSIS OF VR-SEXTRAGD
text: Firstly, we give some key lemmas which are helpful for the convergence analysis of VR-SExtraGD. Lemmas 3, 4 and 5 are used to prove Lemma 6 which is an important lemma to prove the convergence of VR-SExtraGD.
Lemma 3. Let R(·) be a convex function from Rd to R, and ηk>0. Then, for all x, y ∈ Rd,
‖ProxRηk(x)− Prox R ηk (y)‖ ≤ ‖x− y‖.
Lemma 4. Let P (x)=F (x)+R(x), and∇F (x) is Lipschitz continuous with parameter L. For any
x ∈ Rd and arbitrary v ∈ Rd, we define
x′ = ProxRη (x− ηv), g = 1
η (x− x′), 4 = v −∇F (x),
where η is a step size that satisfies 0 < η ≤ 1L . Thus, we can know that for any y ∈ R d,
P (y) ≥ P (x′) + gT (y − x) + η 2 ‖g‖2 +4T (x′ − y).
Lemma 5. Considering P (x) as defined in Problem (1) and ∇̃fik(v) as defined in (3), where v is
an arbitrary stochastic sample, and let x∗ = arg minx P (x). We have E[∇̃fik(v)]=∇F (v) and
E‖∇̃fik(v)−∇F (v)‖2 ≤ 4L[P (v)− P (x∗) + P (x̃)− P (x∗)].
Because Lemma 3 is well known and often used (e.g., see Section 3 in Rockafellar (1970)), we omit the proof of this lemma here. For Lemma 4, it is very similar to Lemma 3.7 of Lin & Tong (2014), and thus can be easily proved, so we also omit the proof here. Similarly, according to Lemma 3.4 in Lin & Tong (2014), Lemma 5 can be also easily proved, and thus we will not give the detail about it. Then we can prove the following lemma by these three lemmas.
Lemma 6. For all randomly selected sample v and h, if
v = ProxRη ( h− η∇̃fik(h) ) , (6)
we have
E‖v − x∗‖2 ≤ ‖h− x∗‖2 − 2η[EP (v)− P (x∗)] + 8Lη2[P (h)− P (x∗) + P (x̃)− P (x∗)],
where x∗ = arg minx P (x).
Proof. First, we define a stochastic gradient mapping as follows:
g = 1 η (h− v) = 1 η (h− ProxRη
( h− η∇̃fik(h) ) .
According to this definition, (6) can be expressed more succinctly as follows:
v = h− ηg.
Then we consider the distance between v and x∗.
‖v − x∗‖2 = ‖h− ηg − x∗‖2 = ‖h− x∗‖2 − 2ηgT (h− x∗) + η2‖g‖2.
Applying Lemma 4 with x = h, v = ∇̃fik(h), x+ = v and y = x∗, we have
−gT (h− x∗) + η
2 ‖g‖2 ≤ P (x∗)− P (v)−4Tk (v − x∗)
where4k = ∇̃fik(h)−∇F (h). Thus we have
‖v− x∗‖2 ≤ ‖h− x∗‖2 − 2η[P (v)− P (x∗)]− 2η4Tk (v − x∗).
Then we can give an upper bound of −2η4Tk (v − x∗). First of all, we can define the update of
Prox-FG as shown below (although it is not used in our algorithm):
h̄ = ProxRη (h− η∇F (h)).
So, we can obtain
−2η4Tk (v − x∗) = −2η4Tk (v − h̄)− 2η4Tk (h̄− x∗)
≤ 2η‖4k‖‖v − h̄‖ − 2η4Tk (h̄− x∗)
≤ 2η‖4k‖‖(h− η∇̃fik(h))− (h− η∇F (h))‖ − 2η4Tk (h̄− x∗)
= 2η2‖4k‖2 − 2η4Tk (h̄− x∗).
The first inequality follows from the Cauchy-Schwarz inequality, and the second inequality holds
due to Lemma 3. So, we have
‖h− x∗‖2 ≤ ‖v − x∗‖2 − 2η[P (h)− P (x∗)] + 2η2‖4k‖2 − 2η4Tk (h̄− x∗).
Then, we take expectation on both sides of the above inequality with respect to ik to obtain
E‖h− x∗‖ ≤ ‖v − x∗‖2 − 2η[EP (h)− P (x∗)] + 2η2E‖4k‖2 − 2ηE[4Tk (h̄− x∗)]. (7)
It can be noted that both h̄ and x∗ are independent of the random variable ik, and we can easily
know that E4k = 0. So
E[4Tk (h̄− x∗)] = (E4k)T (h̄− x∗) = 0. (8)
Substituting Lemma 5 and (8) into (7), we obtain
E‖h− x∗‖2 ≤ ‖v − x∗‖2 − 2η[EP (h)− P (x∗)] + 8Lη2[P (v)− P (x∗) + P (x̃)− P (x∗)]. (9)

heading: D.1 FOR SC PROBLEMS
text: Firstly, we can prove the convergence of VR-SExtraGD for strongly convex (SC) problems, which is showed by the following theorem.
Theorem 3 (Strongly Convex). Suppose that Assumptions 1, 2 and 3 hold, and let x∗ =
arg minx P (x). In addition, assume η1 > 0, η2 > 0, η1 ≥ 4Lη22 and η2 ≥ 4Lη21 and m is suf-
ficiently large so that
θ = 1
µm(η2 − 4Lη21) +
4L[(m+ 1)η21 +mη 2 2 ]
m(η2 − 4Lη21) ≤ 1.
Then VR-SExtraGD outlined in Algorithm 2 achieves linear convergence in the expected form, which
can be formulated as follows:
E[P (x̃S)− P (x∗)] ≤ θS [P (x0)− P (x∗)]. (10)
Proof. According to Lemma 6 and the update rules of VR-SExtraGD, we can easily get:
E‖xk−1/2 − x∗‖2 ≤ ‖xk−1 − x∗‖2 − 2η1[EP (xk−1/2)− P (x∗)]
+ 8Lη21 [P (xk−1)− P (x∗) + P (x̃)− P (x∗)]
(11)
and
E‖xk − x∗‖2 ≤ ‖xk−1/2 − x∗‖2 − 2η2[EP (xk)− P (x∗)]
+ 8Lη22 [P (xk−1/2)− P (x∗) + P (x̃)− P (x∗)].
(12)
Then, we substitute (11) into (12) to obtain
E‖xk − x∗‖2 ≤ ‖xk−1 − x∗‖2 − 2η1[EP (xk−1/2)− P (x∗)]
+ 8Lη21 [P (xk−1)− P (x∗) + P (x̃)− P (x∗)]− 2η2[EP (xk)− P (x∗)]
+ 8Lη22 [P (xk−1/2)− P (x∗) + P (x̃)− P (x∗)].
Suppose η1 ≥ 4Lη22 , i.e., −2η1 ≤ −8Lη22 , we can get
E‖xk − x∗‖2 ≤ ‖xk−1 − x∗‖2 − 8Lη22 [EP (xk− 12 )− P (x∗)]
+ 8Lη21 [P (xk−1)− P (x∗) + P (x̃)− P (x∗)]− 2η2[EP (xk)− P (x∗)]
+ 8Lη22 [P (xk− 12 )− P (x∗)] + 8Lη 2 2 [P (x̃)− P (x∗)]
= ‖xk−1 − x∗‖2 + 8Lη21 [P (xk−1)− P (x∗) + P (x̃)− P (x∗)]
− 2η2[EP (xk)− P (x∗)] + 8Lη22 [P (x̃)− P (x∗)].
By summing the previous inequality over k = 1, ...,m, we obtain
‖xm − x∗‖2 + 2η2[EP (xm)− P (x∗)] + 2(η2 − 4Lη21) m−1∑ k=1 [EP (xk)− P (x∗)]
≤ ‖x0 − x∗‖2 + 8Lη21 [P (x0)− P (x∗)] +m8L(η21 + η22)[P (x̃)− P (x∗)].
Since η2 − 4Lη21 < η2, and from the algorithm of VR-SExtraGD, we know x0 = x̃. Therefore,
2(η2 − 4Lη21) m∑ k=1 [EP (xk)− P (x∗)] ≤ ‖x̃− x∗‖2 + 8L[(m+ 1)η21 +mη22 ][P (x̃)− P (x∗)].
Because in a fixed epoch, such as the s-th epoch, there are x̃s = 1m ∑m k=1 xk and x̃ s−1 = x0, and according to the convexity of P (·), P (x̃s) ≤ 1m ∑m k=1 P (xk) can be obtained. Therefore,
2(η2−4Lη21)m[EP (x̃s)−P (x∗)] ≤ 8L[(m+1)η21+mη22 ][P (x̃s−1)−P (x∗)]+‖x̃s−1−x∗‖2. (13)
Because of the convexity of F (·) and the strong convexity of R(·), we know P (·) is also strongly
convex, then we have ‖x̃s−1 − x∗‖2 ≤ 2µ [P (x̃ s−1)− P (x∗)]. Thus,
2(η2 − 4Lη21)m[EP (x̃s)− P (x∗)] ≤ ( 2
µ + 8L((m+ 1)η21 +mη 2 2))[P (x̃ s−1)− P (x∗)],
which is equivalent to
E[P (x̃s)− P (x∗)] ≤ θ[P (x̃s−1)− P (x∗)],
where
θ = 1
µm(η2 − 4Lη21) +
4L[(m+ 1)η21 +mη 2 2 ]
m(η2 − 4Lη21) .
At last, we have
E[P (x̃S)− P (x∗)] ≤ θE[P (x̃S−1)− P (x∗)]
≤ θ2E[P (x̃S−2)− P (x∗)]
≤ ... ≤ θS [P (x̃0)− P (x∗)].
We note that x̃0 = x0, so we can obtain
E[P (x̃S)− P (x∗)] ≤ θS [P (x0)− P (x∗)]

heading: D.2 FOR NON-SC PROBLEMS
text: We can also use a theorem to give the convergence of VR-SExtraGD for solving non-SC problems, as shown below.
Theorem 4 (Non-Strongly Convex). Suppose that Assumptions 1 and 2 hold, and let x∗ =
arg minx P (x). In addition, assume η1 > 0, η2 > 0, and η1 = η2 = η = 1Lα . Then, the conver-
gence property of VR-SExtraGD, as outlined in Algorithm 2, is given as follows:
E[P (xout)− P (x∗)] ≤ 4m+ 2
m(α− 7)S [P (x0)− P (x∗)] + Lα(α− 1) 2m(α− 7)S ‖x0 − x∗‖2. (14)
where xout = 1S ∑S s=1 x̃ s.
Proof. Because we know F (·) is L-smooth, then we have
P (xk−1/2) ≤ R(xk−1/2) + F (xk−1) + 〈∇̃fik(xk−1), xk−1/2 − xk−1〉
+ L
2 ‖xk−1/2 − xk−1‖2 + 〈∇f(xk−1)− ∇̃fik(xk−1), xk−1/2 − xk−1〉
≤ R(xk−1/2) + F (xk−1) + 〈∇̃fik(xk−1), xk−1/2 − xk−1〉+ L
2 ‖xk−1/2 − xk−1‖2
+ 1
2L(α− 1) ‖∇F (xk−1)− ∇̃fik(xk−1)‖2 + L(α− 1) 2 ‖xk−1/2 − xk−1‖2.
The second inequality holds due to Young’s inequality with parameter L(α− 1), where α is a small
constant. Then after taking expectation with respect to the sample ik and using Lemma 5, we obtain
E[P (xk−1/2)] ≤ R(xk−1/2) + F (xk−1) + E〈∇̃fik(xk−1), xk−1/2 − xk−1〉
+ Lα
2 E‖xk−1/2 − xk−1‖2 +
2
α− 1 [P (xk−1)− P (x∗) + P (x̃)− P (x∗)].
Next, we apply Lemma 1 with xk−1, xk = xk−1/2, u = x∗, and have
E[P (xk−1/2)] ≤ R(x∗) + F (xk−1) + E〈∇̃fik(xk−1), x∗ − xk−1〉
+ Lα
2 (‖x∗ − xk−1‖2 − E‖x∗ − xk−1/2‖2)
+ 2
α− 1 [P (xk−1)− P (x∗) + P (x̃)− P (x∗)]
≤ R(x∗) + F (x∗) + Lα
2 (‖x∗ − xk−1‖2 − E‖x∗ − xk−1/2‖2)
+ 2
α− 1 [P (xk−1)− P (x∗) + P (x̃)− P (x∗)].
The second inequality holds because E[∇̃fik(xk−1)] = ∇F (xk−1) and F (·) is convex. Then we
know
E[P (xk−1/2)− P (x∗)] ≤ 2
α− 1 [P (xk−1)− P (x∗) + P (x̃)− P (x∗)]
+ Lα
2 (‖x∗ − xk−1‖2 − E‖x∗ − xk−1/2‖2).
(15)
And for P (xk), we can deduce by the same way, and obtain the similar result:
E[P (xk)− P (x∗)] ≤ 2
α− 1 [P (xk−1/2)− P (x∗) + P (x̃)− P (x∗)]
+ Lα
2 (‖x∗ − xk−1/2‖2 − E‖x∗ − xk‖2).
(16)
We assume that α is sufficiently large to make 2α−1 ≤ 1, and sum (15) and (16) together, then we
obtain
E[P (xk)− P (x∗)] ≤ 2
α− 1 [P (xk−1)− P (x∗)] +
4
α− 1 [P (x̃)− P (x∗)]
+ Lα
2 (‖x∗ − xk−1‖2 − E‖x∗ − xk‖2).
which is equivalent to
(1− 2 α− 1 )E[P (xk)− P (x∗)] ≤ 2 α− 1 {[P (xk−1)− P (x∗)]− E[P (xk)− P (x∗)]}
+ 4
α− 1 [P (x̃)− P (x∗)] +
Lα
2 (‖x∗ − xk−1‖2 − E‖x∗ − xk‖2).
By summing the previous inequality over k = 1, ...,m, we obtain
(1− 2 α− 1 ) m∑ k=1 E[P (xk)− P (x∗)] ≤ 2 α− 1 {[P (x0)− P (x∗)]− [P (xm)− P (x∗)]}
+ 4m
α− 1 [P (x̃)− P (x∗)] +
Lα
2 (‖x∗ − x0‖2 − ‖x∗ − xm‖2).
Since we set x̃s = 1m ∑m k=1 xk and x s+1 0 = xm, and we know F (·) is a convex function. Thus, we
have
(1− 2 α− 1 )E[P (x̃s)− P (x∗)] ≤ 2 m(α− 1) {[P (xs0)− P (x∗)]− [P (xs+10 )− P (x∗)]}
+ 4
α− 1 [P (x̃s−1)− P (x∗)] +
Lα 2m (‖x∗ − xs0‖2 − ‖x∗ − xs+10 ‖2).
By summing the previous inequality over s = 1, ..., S, we obtain
(1− 2 α− 1 ) S∑ s=1 E[P (x̃s)− P (x∗)] ≤ 4 α− 1 S−1∑ s=0 [P (x̃s)− P (x∗)] + Lα 2m (‖x∗ − x10‖2 − ‖x∗ − xSm‖2)
+ 2
m(α− 1) {[P (x10)− P (x∗)]− [P (xSm)− P (x∗)]}.
That is,
(1− 2 α− 1 − 4 α− 1 ) S∑ s=1 E[P (x̃s)− P (x∗)]
≤ 4 α− 1 [P (x̃0)− P (x∗)] + 2 m(α− 1) ([P (x10)− P (x∗)]− [P (xSm)− P (x∗)])
+ Lα
2m (‖x∗ − x10‖2 − ‖x∗ − xSm‖2)
≤ 2 m(α− 1) [P (x10)− P (x∗)] + 4 α− 1 [P (x̃0)− P (x∗)] + Lα 2m ‖x∗ − x10‖2.
The first inequality holds due to 1− 2α−1 ≥ 1− 2 α−1 − 4 α−1 and the second inequality holds because
P (xSm)− P (x∗) ≥ 0 and ‖x∗ − xSm‖2 ≥ 0. Because x10 = x̃0, we have
(1− 6 α− 1 ) S∑ s=1 E[P (x̃s)− P (x∗)] ≤ ( 2 m(α− 1) + 4 α− 1 )[P (x̃0)− P (x∗)] + Lα 2m ‖x̃0 − x∗‖2
Due to the convexity of F (·), we have
EP ( S∑ s=1 x̃s)− P (x∗) ≤ 1 S S∑ s=1 E[P (x̃s)− P (x∗)]
≤ 4m+ 2 m(α− 7)S [P (x̃0)− P (x∗)] + Lα(α− 1) 2m(α− 7)S ‖x̃0 − x∗‖2
We note that x̃0 = x0, so we have

heading: E MORE EXPERIMENTAL RESULTS

heading: E.1 THE INFORMATION OF DATA SETS
text: Data sets Sizes n Dimensions d Sparsity λ1 λ2 a9a 32,562 123 Sparse 10−6 10−4 Covtype 581,012 54 Dense 10−5 10−8
rcv1 20,242 47,236 Sparse 10−8 10−10 real-sim 72,309 20,598 Sparse 10−6 10−8

heading: E.2 THE PROBLEM MODELS
text: In this part, we introduce two common problem models. The first one is
min x∈Rd
1
2n n∑ i=1 (aTi x−bi)2+λ1‖x‖1+ λ2 2 ‖x‖2.
When λ1 ≥ 0, λ2 ≡ 0, we can obtain the Lasso problem, and when λ1, λ2 ≥ 0, we can obtain the Elastic-Net problem, which are all non-smooth optimization problems. The second problem model is
min x∈Rd
1
n n∑ i=1 log(1+exp(−bixTai))+λ‖x‖1,
which is called the `1 norm regularized logistic regression problem.

heading: E.3 MORE EXPERIMENTAL RESULTS
text: For more comprehensive comparison, we provide the performance comparison of more algorithms, including SVRG++, MiG and our VR-SExtraGD.
Figure 4 shows the experimental result of different algorithms on different data set to solve the Lasso problem. We can see that AVR-SExtraGD is superior to other algorithms in terms of the number of effective passes and running time. Besides, we note that VR-SExtraGD achieves almost the same result as AVR-SExtraGD in terms of effective passes, which may be due to the advantage of the extragradient structure. But, since VR-SExtraGD needs to calculate the stochastic gradient twice in each inner-iteration, the result in terms of running time is not as good as AVR-SExtraGD.
Moreover, in order to avoid the particularity of the problems solved by our algorithm, we also provide the performance comparison of different algorithms on different data set to solve the `1- norm regularized logistic regression problem, as shown in Figure 5.
From Figure 5, we know that our AVR-SExtraGD outperforms other compared algorithms in terms of both effective passes and running time. Although Katyusha is better than our algorithm in terms of effective passes, its result in terms of running time in not as good as ours because of the complicated structure of the algorithm.

Review summaries:
The paper proposes an optimization method for solving unconstrained convex optimization problems where the objective function consists of a sum of several smooth components f_i and a (not necessarily smooth) convex function R. The proposed method AVR-SExtraGD is a stochastic descent method building on the previous algorithms Prox-SVRG (Lin 2014) and Katyusha (Zeyuan 2017). The previous Prox-SVRG method using a proximal operator is explained to converge fast but leads to inaccurate final solutions, while the Katyusha method is an algorithm based on  momentum acceleration. The current paper builds on these two approaches and applies the momentum acceleration technique in a stochastic extragradient descent framework to achieve fast convergence.

This is an optimization algorithm paper, using the idea of "extragradient" and proposing to combine acceleration with proximal gradient descent-type algorithms (Prox-SVRG). Their proposed algorithm, i.e., accelerated variance reduced stochastic extra gradient descent, combines the advantages of Prox-SVRG and momentum acceleration techniques. The authors prove the convergence rate and oracle complexity of their algorithm for strongly convex and non-strongly convex problems. Their experiments on face recognition show improvement on top of Prox-SVRG as well Katyusha. They also propose an asynchronous variant of their algorithm and show that it outperforms other asynchronous baselines.