Title: ACCELERATED VARIANCE REDUCED STOCHASTIC EXTRAGRADIENT METHOD FOR SPARSE MACHINE LEARNING PROBLEMS

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.

1. INTRODUCTION:

In this paper, we mainly consider the following composite convex optimization problem:

EQUATION

where F (x) : R d → R is the average of smooth convex component functions f i (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 {(a 1 , b 1 ), ..., (a n , b n )}, where a i ∈ R d , b i ∈ R (i = 1, 2, ..., n) and a i is a feature vector, while b i is the desired response. When f i (x) = 1 2 (a T i x-b i ) 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) = λ2 2 x 2 +λ 1 x 1 , respectively. Moreover, if we set f i (x) = log(1+exp(-b i x T a i )), we will get the regularized logistic regression problem.

1.1. RECENT RESEARCH PROGRESS:

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 of O(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, Konečný & Richtárik (2013) proposed the semi-stochastic gradient descent methods as well as their mini-batch version (Konečný 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.

1.2. OUR MAIN CONTRIBUTIONS:

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 VR-SExtraGD, 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.

2. RELATED WORK:



2.1. BASIC ASSUMPTIONS:

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 ∈ R d , ∇F (x)-∇F (y) ≤ L x-y . Assumption 2 (Lower Semi-continuity). The regularization function R(•) is a lower semicontinuous function, i.e., ∀x

0 ∈ R d , lim inf x→x0 R(x) ≥ R(x 0 ).

But it is not necessarily differentiable or continuous. Assumption 3 (Strong Convexity). In Problem (1), the function R(•) is µ-strongly convex, i.e., there exists a constant µ > 0 such that for all x, y ∈ R d , it holds that

EQUATION

)

where G ∈ ∂R(y) which is the set of sub-gradient of R(•) at y.

2.2. PROX-SVRG AND EXTRAGRADIENT DESCENT METHODS:

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

EQUATION

where x is the snapshot point used in SVRG, ∇f i k (x k-1 ) is the variance reduced stochastic gradient estimator, and Prox R η (•) 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 Korpelevič (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∈R d P (x) def = F (x) + R(x)

where F (x) is not necessarily composed by multiple functions f i (x). Unlike the classical extragradient method, EEG uses proximal gradient instead of orthogonal projection in each iteration. The main update rules of EEG are

y k = Prox R s k (x k -s k ∇F (x k )); x k+1 = Prox R α k (x k -α k ∇F (y k ))

, where s k 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.

2.3. MOMENTUM ACCELERATION AND MIG:

Firstly, we introduce the momentum acceleration technique whose main update rules are

v dwt = βv dwt-1 + (1 -β)dw t ; w t = w t-1 -αv dwt ,

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 w t after using momentum Algorithm 1 AVR-SExtraGD Input: Initial vector x 0 , the number of epochs S, the number of iterations m per epoch, the step sizes η 1 , η 2 , momentum parameter β, and the set K. Initialize: x0 = x 1 0 = x 0 , ρ = 1+ηµ. 1: for s = 1, 2, . . . , S do 2:

Compute ∇F (x s-1 ); 3:

β s = β (SC) or β s = 2 s+4 (non-SC); 4:

for k = 1, 2, . . . , m do 5:

Pick i k uniformly at random from {1, ..., n};

6:

if k ∈ K then 7:

x s k-1/2 = Prox R η1 x s k-1 -η 1 ∇f i k (β s x s k-1 + (1-β s )x s-1 ) ; 8: x s k = Prox R η2 x s k-1/2 -η 2 ∇f i k (β s x s k-1/2 + (1-β s )x s-1 ) ; 9:

else 10:

x s k = Prox R η1 (x s k-1 -η 1 ∇f i k (β s x s k-1 + (1-β s )x s-1 )); 11: end if 12:

end for 13:

xs = β 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 xs = βs m m k=1 x s k-1/2 +x s k 2

+(1-β s )x s-1 (non-SC);

14:

x s+1 0 = x s m ; 15: end for Output: xS . 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:

y s k-1 = β s x 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.

3. OUR AVR-SEXTRAGD METHOD:

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 ≤ 1 2L , η 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

β 2 s-1 ≥ 1-βs β 2 s .

Particularly, in AVR-SExtraGD, we set β s = 2 s+4 , which satisfies the inequality defined above. As we all know, for the general GD method, the iterate x k 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.

4. CONVERGENCE ANALYSIS:

In this section, we analyze the convergence properties of AVR-SExtraGD under strongly convex and non-strongly convex conditions. For convenience analysis, we use ∇i k F (•) to denote ∇f i k (•), 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.

4.1. FOR SC PROBLEMS:

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 min x 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.

4.2. FOR NON-SC PROBLEMS:

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 min x P (x). In addition, assume

η 1 = η 2 = η = 1 Lα > 0 and 1 -β s -1 α-1 ≥ 0,

where α is a constant. Then by setting β s = 2 s+4 , we have

E[P (x S )-P (x * )] ≤ 4(1-β 1 ) (S +4) 2 β 2 1 (P (x 0 )-P (x * ))+ Lα (S +4) 2 m x 0 -x * 2 ,

which also means that when we choose m = Θ(n), Algorithm 1 achieves the following oracle complexity in expectation:

O(n P (x 0 )-P (x * ) + nL x 0 -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.

5. EXPERIMENTS:

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 as m = 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 = 2 5L , η 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.

5.1. RESULTS OF LASSO, ELASTIC-NET AND LOGISTIC REGRESSION:

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. 

5.2. RESULTS ON FACE RECOGNITION:

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.

5.3. THE SELECTION OF K IN AVR-SEXTRAGD:

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.

6. CONCLUSIONS AND FUTURE WORK:

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) ).

APPENDIX A THE ERROR OF OPTIMAL VALUE:

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

x k = Prox R η k (x k-1 -η k ∇F (x k-1 )) = arg min u∈R d {R(u) + 1 2η k u -(x k-1 -η k ∇F (x k-1 )) 2 } = arg min u∈R d {R(u) + η k 2 ∇F (x k-1 ) 2 + ∇F (x k-1 ) T (u -x k-1 ) + 1 2η k u -x k-1 2 } = arg min u∈R d {R(u) + F (x k-1 ) + ∇F (x k-1 ) T (u -x k-1 ) + 1 2η k u -x k-1 2 } ≈ arg min u∈R d {F (u) + R(u)}.

The final approximation is obtained by the second-order Taylor expansion of F (u) at x k-1 . From the above analysis, we can see that when using proximal operators to solve the problems with the 1 -norm regularization, the iterate x k 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.

B PROOFS OF AVR-SEXTRAGD B.1 KEY LEMMAS:

Lemma 1. If two vectors x k , x k-1 ∈ R d satisfy the following equality,

x k = arg min x { 1 2η x-x k-1 2 + ∇i k F (x k-1 ), x +R(x)}

with a constant vector ∇i k F (x k-1 ) and a convex function R(•), then for ∀u ∈ R d , we have

∇i k F (x k-1 ), x k -u ≤ - 1 2η x k-1 -x k 2 + 1 2η x k-1 -u 2 - 1 2η x k -u 2 +R(u)-R(x k ).

Moreover, if R(•) is µ-strongly convex, the above inequality becomes

∇i k F (x k-1 ), x k -u ≤ - 1 2η x k-1 -x k 2 + 1 2η x k-1 -u 2 - 1+ηµ 2η x k -u 2 +R(u)-R(x k ). Lemma 2 (Variance Bound). Suppose each function f i (•) is L i -smooth, let ∇i k F (x k-1 ) = ∇ i k F (x k-1 ) -∇ i k F (x s-1 ) + ∇F (x s-1

), which is the gradient estimation operator used in Algorithm 1. Then the following inequality holds

E ∇F (x k-1 )-∇i k F (x k-1 ) 2 ≤ 2L(F (x s-1 )-F (x k-1 )-∇F (x k-1 ), xs-1 -x k-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.

B.2 PROOF OF THEOREM 1:

Proof. In this part, we consider one particular epoch and omit the number of outer iteration s (except xs-1 and xs ). We assume the parameters η and β satisfy the following inequality,

EQUATION

) Let xk-1 = βx k-1 +(1-β)x s-1 , xk-1/2 = βx k-1/2 +(1-β)x s-1 . Thus, we can obtain xk-1/2 -x k-1 = β(x k-1/2 -x k-1

). Thus, according to the L-smoothness of F (•), we can obtain

P (x k-1/2 ) ≤ βR(x k-1/2 )+(1-β)R(x s-1 )+F (x k-1 )+ ∇i k F (x k-1 ), β(x k-1/2 -x k-1 ) + Lβ 2 2 x k-1/2 -x k-1 2 + ∇F (x k-1 )-∇i k F (x k-1 ), β(x k-1/2 -x k-1 ) .

Then by using (4), we have

1 β P (x k-1/2 ) ≤ R(x k-1/2 )+ 1-β β R(x s-1 )+ 1 β F (x k-1 )+ ∇i k F (x k-1 ), x k-1/2 -x k-1 + 1 2η x k-1/2 -x k-1 2 - Lβ 2(1-β) x k-1/2 -x k-1 2 + ∇F (x k-1 )-∇i k F (x k-1 ), x k-1/2 -x k-1 .

According to Lemma 1 with x k-1 , x k = x k-1/2 , u = x * and using the Young's inequality to expand

∇F (x k-1 ) -∇i k F (x k-1 ), x k-1/2 -x k-1

with the parameter θ > 0 and taking expectation with respect to the sample i k , we have

1 β EP (x k-1/2 ) ≤ R(x * )+ 1-β β R(x s-1 )+ 1 β F (x k-1 )+E ∇i k F (x k-1 ), x * -x k-1 + 1 2η x * -x k-1 2 - 1+ηµ 2η E x * -x k-1/2 2 - Lβ 2(1-β) E x k-1/2 -x k-1 2 + θ 2 E x k-1/2 -x k-1 2 + 1 2θ E ∇F (x k-1 )-∇i k F (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 * -x k-1 2 - 1+ηµ 2η E x * -x k-1/2 2 + 1-β β [F (x s-1 )-F (x k-1 )] +E ∇i k F (x k-1 ), x * + 1-β β xs-1 - 1 β xk-1 + 1-β β (x k-1 -xs-1 ) ≤ R(x * )+ 1-β β R(x s-1 )+ 1 β F (x k-1 ) + 1 2η x * -x k-1 2 - 1+ηµ 2η E x * -x k-1/2 2 + 1-β β [F (x s-1 )-F (x k-1 )] + 1 β E ∇i F (x k-1 ), βx * +(1-β)x k-1 -xk-1 ≤ R(x * )+ 1-β β R(x s-1 )+ 1 β F (x k-1 ) + 1 2η x * -x k-1 2 - 1+ηµ 2η E x * -x k-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 * -x k-1 2 - 1+ηµ 2η E x * -x k-1/2 2 = 1-β β P (x s-1 )+P (x * )+ 1 2η x * -x k-1 2 - 1+ηµ 2η E x * -x k-1/2 2 .

The third inequality holds due to E[ ∇i k F (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 * -x k-1 2 - 1+ηµ 2η E x * -x k-1/2 2 . Moreover, because xk-1 = βx k-1 +(1-β)x s-1 , we can obtain xk = βx k +(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 * -x k-1/2 2 - 1+ηµ 2η E x * -x k 2 .

We set

y k = β x k-1/2 +x k 2

+(1-β)x s-1 and it is obvious that 1 2η -1+ηµ 2η ≤ 0, then we have

EQUATION

)

By setting ρ = 1+ηµ and summing (5) over k = 1, ..., m with increasing weight ρ k-1 , we have

1 β m k=1 ρ k-1 E[P (y k )-P (x * )]+ ρ m 4η x m -x * 2 ≤ 1-β β m k=1 ρ k-1 [P (x s-1 )-P (x * )]+ 1 4η x 0 -x * 2 .

Because, for SC problems, we set xs = (

m k=1 ρ k-1 ) -1 m k=1 ρ k-1 y k in Algorithm 1 , we have 1 β m k=1 ρ k-1 E[P (x s )-P (x * )]+ ρ m 4η x s m -x * 2 ≤ 1-β β m k=1 ρ k-1 [P (x s-1 )-P (x * )]+ 1 4η x s 0 -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

EQUATION

)

-Sm

• O(P (x 0 )-P (x * )).

We note that x0 = x 0 , so we get

E[P (x S )-P (x * )] ≤ O(1+ 1 3nκ ) -Sm • O(P (x 0 )-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 x0 = x 0 , so we have

E[P (x S )-P (x * )] ≤ 2 3 S • O(P (x 0 )-P (x * )),

which implies that the oracle complexity of AVR-SExtraGD in this case is O n log P (x0)-P (x * ) .

B.3 PROOF OF THEOREM 2:

Proof. In this part, we also omit the number of outer iteration s (except xs-1 and xs ). Due to

xk-1/2 = βx k-1/2 +(1-β)x s-1 , we can get P (x k-1/2 ) = P (βx k-1/2 +(1-β)x s-1 ) = R(βx k-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(x k-1/2 )+(1-β)R(x s-1 )+F (x k-1 )+ ∇i k F (x k-1 ), β(x k-1/2 -x k-1 ) + Lβ 2 2 x k-1/2 -x k-1 2 + ∇F (x k-1 )-∇i k F (x k-1 ), β(x k-1/2 -x k-1 ) ≤ βR(x k-1/2 )+(1-β)R(x s-1 )+F (x k-1 )+ ∇i k F (x k-1 ), β(x k-1/2 -x k-1 ) + Lαβ 2 2 x k-1/2 -x k-1 2 + 1 2L(α-1) ∇F (x k-1 )-∇i k F (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 i k , we have

EP (x k-1/2 ) ≤ βR(x * )+(1 -β)R(x s-1 )+F (x k-1 )+E ∇i k F (x k-1 ), β(x * -x k-1 ) + Lαβ 2 2 ( x * -x k-1 2 -E x * -x k-1/2 2 ) + 1 2L(α-1) E ∇F (x k-1 )-∇i k F (x k-1 ) 2 ≤ βR(x * )+(1-β)R(x s-1 )+F (x k-1 )+E ∇i k F (x k-1 ), β(x * -x k-1 ) + Lαβ 2 2 ( x * -x k-1 2 -E x * -x k-1/2 2 ) + 1 α-1 [F (x s-1 )-F (x k-1 )+E ∇i k F (x k-1 ), xk-1 -xs-1 ] ≤ βR(x * )+(1-β)R(x s-1 )+F (x k-1 )+ 1 α-1 [F (x s-1 )-F (x k-1 )] +E ∇i k F (x k-1 ), βx * +(1-β)x s-1 -xk-1 + 1 α-1 (x k-1 -xs-1 ) + Lαβ 2 2 ( x * -x k-1 2 -E x * -x k-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 xk-1 )-F (x k-1 ) + Lαβ 2 2 ( x * -x k-1 2 -E x * -x k-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 * -x k-1 2 -E x * -x k-1/2 2 ) = (1-β)P (x s-1 )-βP (x * )+ Lαβ 2 2 ( x * -x k-1 2 -E x * -x k-1/2 2 ).

The second inequality holds due to Lemma 2. The reasons why the fourth inequality holds are

E[ ∇i k F (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 * -x k-1 2 -E x * -x k-1/2 2 ).

Moreover, because xk-1 = βx k-1 +(1-β)x s-1 , we can obtain xk = βx k +(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 * -x k-1/2 2 -E x * -x k 2 ).

Let

y k = β x k-1/2 +x k 2

+(1-β)x s-1 , we have

E[P (y k )-P (x * )] ≤ (1-β)[P (x s-1 )-P (x * )]+ Lαβ 2 4 ( x * -x k-1 2 -E x * -x k 2 ).

That is,

1 β 2 E[P (y k ) -P (x * )] ≤ (1-β) β 2 [P (x s-1 )-P (x * )]+ Lα 4 ( x * -x k-1 2 -E x * -x k 2 ). Since we have xs = β m m k=1 x k-1/2 +x k 2 +(1-β)x s-1 = 1 m m k=1 y k in Algorithm 1

, and then by summing the previous inequality over k = 1, ..., m and according to x s+1 0 = x s m , we obtain

1 β 2 s E[P (x s )-P (x * )] ≤ (1-β s ) β 2 s [P (x s-1 )-P (x * )]+ Lα 4m ( x * -x s 0 2 -x * -x s+1 0 2 ).

We set β s = 2 s+4 and can easily obtain 1

β 2 s-1 ≥ 1-βs β 2 s .

Then by summing the previous inequality over s = 1, ..., S, we can get

1 β 2 S E[P (x S )-P (x * )] ≤ (1-β 1 ) β 2 1 [P (x s-1 )-P (x * )]+ Lα 4m ( x * -x 1 0 2 -x * -x S m 2 ).

Then we have

E[P (x S )-P (x * )] ≤ 4(1-β 1 ) (S +4) 2 β 2 1 (P (x 0 )-P (x * ))+ Lα (S +4) 2 m x0 -x * 2 ,

which holds because x * -x S m 2 ≥ 0. We note that x0 = x 1 0 = x 0 , so we get

E[P (x S )-P (x * )] ≤ 4(1-β 1 ) (S +4) 2 β 2 1 (P (x 0 )-P (x * ))+ Lα (S +4) 2 m x 0 -x * 2 .

In other words, by choosing m = Θ(n), the total oracle complexity is

O n P (x 0 )-P (x * ) + nL x 0 -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 x 0 , the number of epochs S, the number of iterations m per epoch, and the step sizes η 1 , η 2 . Initialize: x0 = x 0 . 1: for s = 1, 2, . . . , S do 2:

μs-1 = ∇F (x s-1 ); 3:

x s 0 = xs-1 (SC) or x s 0 = x s-1 m (non-SC); 4:

for k = 1, 2, . . . , m do 5:

Pick i k uniformly at random from {1, ..., n};

6: 

∇f i k (x s k-1 ) = ∇f i k (x s k-1 )-∇f i k (x s-1 )+ μs-1 ; 7: x s k-1/2 = Prox R η1 (x s k-1 -η 1 ∇f i k (x s k-1 )); 8: ∇f i k (x s k-1/2 ) = ∇f i k (x s k-1/2 )-∇f i k (x s-1 )+ μs-1 ; 9: x s k = Prox R η2 (x s k-1/2 -η 2 ∇f i k (x s k-1/2 ));

C SEXTRAGD AND VR-SEXTRAGD:

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:

x k-1/2 = Prox R η1 (x k-1 -η 1 ∇f i k (x k-1 )) ; x k = Prox R η2 x k-1/2 -η 2 ∇f i k (x k-1/2 ) .

• The update rules of VR-SExtraGD:

x k-1/2 = Prox R η1 x k-1 -η 1 ∇f i k (x k-1 ) ; x k = Prox R η2 x k-1/2 -η 2 ∇f i k (x k-1/2 ) ,

where ∇f i k (•) is the gradient estimation defined in (3).

We note that one difference between these two algorithms and EEG is that we change x k-1 in

Step two to x k-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.

D CONVERGENCE ANALYSIS OF VR-SEXTRAGD:

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 R d to R, and η k > 0. Then, for all x, y ∈ R d ,

Prox R η 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 ∈ R d and arbitrary v ∈ R d , we define

x = Prox R η (x -ηv), g = 1 η (x -x ), = v -∇F (x),

where η is a step size that satisfies 0 < η ≤ 1 L . Thus, we can know that for any y ∈ R d ,

P (y) ≥ P (x ) + g T (y -x) + η 2 g 2 + T (x -y).

Lemma 5. Considering P (x) as defined in Problem (1) and ∇f i k (v) as defined in (3), where v is an arbitrary stochastic sample, and let x * = arg min x P (x). We have

E[ ∇f i k (v)] = ∇F (v)

and

E ∇f i k (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

EQUATION

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 min x P (x).

Proof. First, we define a stochastic gradient mapping as follows:

g = 1 η (h -v) = 1 η (h -Prox R η h -η ∇f i k (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ηg T (h -x * ) + η 2 g 2 .

Applying Lemma 4 with x = h, v = ∇f i k (h), x + = v and y = x * , we have

-g T (h -x * ) + η 2 g 2 ≤ P (x * ) -P (v) -T k (v -x * )

where k = ∇f i k (h) -∇F (h). Thus we have

v-x * 2 ≤ h-x * 2 -2η[P (v)-P (x * )] -2η T k (v -x * ).

Then we can give an upper bound of -2η T k (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 = Prox R η (h -η∇F (h)).

So, we can obtain

-2η T k (v -x * ) = -2η T k (v -h) -2η T k ( h -x * ) ≤ 2η k v -h -2η T k ( h -x * ) ≤ 2η k (h -η ∇f i k (h)) -(h -η∇F (h)) -2η T k ( h -x * ) = 2η 2 k 2 -2η T k ( 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 k 2 -2η T k ( h -x * ).

Then, we take expectation on both sides of the above inequality with respect to i k to obtain

EQUATION

It can be noted that both h and x * are independent of the random variable i k , and we can easily

EQUATION

Substituting Lemma 5 and ( 8) into (7), we obtain

EQUATION

D.1 FOR SC PROBLEMS 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 min x P (x). In addition, assume η 1 > 0, η 2 > 0, η 1 ≥ 4Lη 2 2 and η 2 ≥ 4Lη 2 1 and m is sufficiently large so that

θ = 1 µm(η 2 -4Lη 2 1 ) + 4L[(m + 1)η 2 1 + mη 2 2 ] m(η 2 -4Lη 2 1 ) ≤ 1.

Then VR-SExtraGD outlined in Algorithm 2 achieves linear convergence in the expected form, which can be formulated as follows:

EQUATION

Proof. According to Lemma 6 and the update rules of VR-SExtraGD, we can easily get:

EQUATION

and

EQUATION

Then, we substitute (11) into (12) to obtain

E x k -x * 2 ≤ x k-1 -x * 2 -2η 1 [EP (x k-1/2 ) -P (x * )] + 8Lη 2 1 [P (x k-1 ) -P (x * ) + P (x) -P (x * )] -2η 2 [EP (x k ) -P (x * )] + 8Lη 2 2 [P (x k-1/2 ) -P (x * ) + P (x) -P (x * )]. Suppose η 1 ≥ 4Lη 2 2 , i.e., -2η 1 ≤ -8Lη 2 2 , we can get E x k -x * 2 ≤ x k-1 -x * 2 -8Lη 2 2 [EP (x k-1 2 ) -P (x * )] + 8Lη 2 1 [P (x k-1 ) -P (x * ) + P (x) -P (x * )] -2η 2 [EP (x k ) -P (x * )] + 8Lη 2 2 [P (x k-1 2 ) -P (x * )] + 8Lη 2 2 [P (x) -P (x * )] = x k-1 -x * 2 + 8Lη 2 1 [P (x k-1 ) -P (x * ) + P (x) -P (x * )] -2η 2 [EP (x k ) -P (x * )] + 8Lη 2 2 [P (x) -P (x * )].

By summing the previous inequality over k = 1, ..., m, we obtain

x m -x * 2 + 2η 2 [EP (x m ) -P (x * )] + 2(η 2 -4Lη 2 1 ) m-1 k=1 [EP (x k ) -P (x * )] ≤ x 0 -x * 2 + 8Lη 2 1 [P (x 0 ) -P (x * )] + m8L(η 2 1 + η 2 2 )[P (x) -P (x * )].

Since η 2 -4Lη 2 1 < η 2 , and from the algorithm of VR-SExtraGD, we know x 0 = x. Therefore,

2(η 2 -4Lη 2 1 ) m k=1 [EP (x k ) -P (x * )] ≤ x -x * 2 + 8L[(m + 1)η 2 1 + mη 2 2 ][P (x) -P (x * )].

Because 

EQUATION

)

Because of the convexity of F (•) and the strong convexity of R(•), we know P (•) is also strongly convex, then we have xs

-1 -x * 2 ≤ 2 µ [P (x s-1 ) -P (x * )]. Thus, 2(η 2 -4Lη 2 1 )m[EP (x s ) -P (x * )] ≤ ( 2 µ + 8L((m + 1)η 2 1 + 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η 2 1 ) + 4L[(m + 1)η 2 1 + mη 2 2 ] m(η 2 -4Lη 2 1 )

.

At last, we have

E[P (x S ) -P (x * )] ≤ θE[P (x S-1 ) -P (x * )] ≤ θ 2 E[P (x S-2 ) -P (x * )] ≤ ... ≤ θ S [P (x 0 ) -P (x * )].

We note that x0 = x 0 , so we can obtain

E[P (x S ) -P (x * )] ≤ θ S [P (x 0 ) -P (x * )] D.2 FOR NON-SC PROBLEMS

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 min x P (x). In addition, assume η 1 > 0, η 2 > 0, and η 1 = η 2 = η = 1 Lα . Then, the convergence property of VR-SExtraGD, as outlined in Algorithm 2, is given as follows:

EQUATION

)

where

x out = 1 S S s=1

xs .

Proof. Because we know F (•) is L-smooth, then we have

P (x k-1/2 ) ≤ R(x k-1/2 ) + F (x k-1 ) + ∇f i k (x k-1 ), x k-1/2 -x k-1 + L 2 x k-1/2 -x k-1 2 + ∇f (x k-1 ) -∇f i k (x k-1 ), x k-1/2 -x k-1 ≤ R(x k-1/2 ) + F (x k-1 ) + ∇f i k (x k-1 ), x k-1/2 -x k-1 + L 2 x k-1/2 -x k-1 2 + 1 2L(α -1) ∇F (x k-1 ) -∇f i k (x k-1 ) 2 + L(α -1) 2 x k-1/2 -x k-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 i k and using Lemma 5, we obtain

E[P (x k-1/2 )] ≤ R(x k-1/2 ) + F (x k-1 ) + E ∇f i k (x k-1 ), x k-1/2 -x k-1 + Lα 2 E x k-1/2 -x k-1 2 + 2 α -1 [P (x k-1 ) -P (x * ) + P (x) -P (x * )].

Next, we apply Lemma 1 with x k-1 , x k = x k-1/2 , u = x * , and have

E[P (x k-1/2 )] ≤ R(x * ) + F (x k-1 ) + E ∇f i k (x k-1 ), x * -x k-1 + Lα 2 ( x * -x k-1 2 -E x * -x k-1/2 2 ) + 2 α -1 [P (x k-1 ) -P (x * ) + P (x) -P (x * )] ≤ R(x * ) + F (x * ) + Lα 2 ( x * -x k-1 2 -E x * -x k-1/2 2 ) + 2 α -1 [P (x k-1 ) -P (x * ) + P (x) -P (x * )].

The second inequality holds because E[ ∇f i k (x k-1 )] = ∇F (x k-1 ) and F (•) is convex. Then we know

EQUATION

And for P (x k ), we can deduce by the same way, and obtain the similar result:

EQUATION

We assume that α is sufficiently large to make 2 α-1 ≤ 1, and sum ( 15) and ( 16) together, then we obtain

E[P (x k ) -P (x * )] ≤ 2 α -1 [P (x k-1 ) -P (x * )] + 4 α -1 [P (x) -P (x * )] + Lα 2 ( x * -x k-1 2 -E x * -x k 2 ).

which is equivalent to

(1 - 2 α -1 )E[P (x k ) -P (x * )] ≤ 2 α -1 {[P (x k-1 ) -P (x * )] -E[P (x k ) -P (x * )]} + 4 α -1 [P (x) -P (x * )] + Lα 2 ( x * -x k-1 2 -E x * -x k 2 ).

By summing the previous inequality over k = 1, ..., m, we obtain

(1 - 2 α -1 ) m k=1 E[P (x k ) -P (x * )] ≤ 2 α -1 {[P (x 0 ) -P (x * )] -[P (x m ) -P (x * )]} + 4m α -1 [P (x) -P (x * )] + Lα 2 ( x * -x 0 2 -x * -x m 2 ).

Since we set xs = 1 m m k=1

x k and x s+1 0 = x m , and we know F (•) is a convex function. Thus, we have

EQUATION

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 * -x 1 0 2 -x * -x S m 2 ) + 2 m(α -1) {[P (x 1 0 ) -P (x * )] -[P (x S m ) -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 (x 1 0 ) -P (x * )] -[P (x S m ) -P (x * )]) + Lα 2m ( x * -x 1 0 2 -x * -x S m 2 ) ≤ 2 m(α -1) [P (x 1 0 ) -P (x * )] + 4 α -1 [P (x 0 ) -P (x * )] + Lα 2m x * -x 1 0 2 .

The first inequality holds due to 1 - 

2 α-1 ≥ 1 -2 α-1 -4 α-

(a T i x-b i ) 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∈R d 1 n n i=1 log(1+exp(-b i x T a i ))+λ x 1 ,

which is called the 1 norm regularized logistic regression problem.

E.3 MORE EXPERIMENTAL RESULTS:

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 1norm 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. 

:



Figures and Tables:

Figure 1: Comparison of experimental results of different algorithms for Lasso (top) and Elastic-Net (bottom) problems on different data sets. The y-axis represents the gap between the objective value and the minimum, and the x-axis corresponds to running time.

Figure 2: Comparison of experimental results of different algorithms for Lasso (the first two columns) and Elastic-Net (the latter two columns) problems on different data sets. The y-axis represents the gap of objective value, and the x-axis corresponds to the number of effective passes (top) or running time (bottom).

Figure 3: Comparison of experimental results about different choices of K in AVR-SExtraGD for Lasso on different data sets. The y-axis represents the gap of objective value, and the x-axis corresponds to the number of effective passes ((a.1) and (b.1)) or running time ((a.2) and (b.2)).

in a fixed epoch, such as the s-th epoch, there are xs = 1 m m k=1 x k and xs-1 = x 0 , and according to the convexity of P (•), P (x s ) ≤ 1 m m k=1 P (x k ) can be obtained. Therefore,

1 and the second inequality holds becauseP (x S m ) -P (x * ) ≥ 0 and x * -(x s ) -P (x * )] ≤ ( 2 m(α -1) + 4 α -1 )[P (x 0 ) -P (x * )] + Lα 2m x0 -x * 2Due to the convexity of F (•), we have EP (

Figure 4: Comparison of experimental results of different algorithms for Lasso on different data sets. The y-axis represents the gap between the objective value and the minimum, and the x-axis corresponds to the number of effective passes (top) or running time (bottom).

Figure 5: Comparison of experimental results of different algorithms for the 1 -norm regularized logistic regression problem. on different data sets. The y-axis represents the gap between the objective value and the minimum, and the x-axis corresponds to the number of effective passes (top) or running time (bottom).

Comparison of Recognition Rates on the AR and Yale Datasets.

Table content: <table><tr><td>Problems</td><td>Algorithms</td><td>AR</td><td>Yale</td></tr><tr><td/><td>Prox-SVRG</td><td>0.6000 ± 0.0648</td><td>0.6200 ± 0.0447</td></tr><tr><td>Lasso</td><td>Katyusha</td><td>0.5880 ± 0.0832</td><td>0.7480 ± 0.0415</td></tr><tr><td/><td>AVR-SExtraGD</td><td>0.6200 ± 0.0756</td><td>0.8100 ± 0.0265</td></tr><tr><td/><td>Prox-SVRG</td><td>0.5630 ± 0.0580</td><td>0.6400 ± 0.0394</td></tr><tr><td>Elastic-Net</td><td>Katyusha</td><td>0.5560 ± 0.0738</td><td>0.6870 ± 0.0433</td></tr><tr><td/><td>AVR-SExtraGD</td><td>0.5800 ± 0.0634</td><td>0.7140 ± 0.0297</td></tr></table>

Summary of Data Sets and Regularization Coefficient Data sets Sizes n Dimensions d Sparsity

Table content: <table><tr><td>λ 1</td><td>λ 2</td></tr></table>

Peer review (iclr2020):
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