Accelerated Variance Reduced Stochastic Extragradient Method for Sparse Machine Learning Problems
Authors: Fanhua Shang
Lin Kong
Yuanyuan Liu
Hua Huang
Hongying Liu
Venue:  (2020)
Keywords: non-smooth optimization
SVRG
proximal operator
extragradient descent
momentum acceleration

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 the improved performance compared with Prox-SVRG and Katyusha. The asynchronous variant of AVR-SExtraGD outperforms KroMagnon and ASAGA, which are the asynchronous variants of SVRG and SAGA, respectively.

Under review as a conference paper at ICLR 2020
ACCELERATED VARIANCE REDUCED STOCHASTIC EXTRAGRADIENT METHOD FOR SPARSE MACHINE LEARNING PROBLEMS
Anonymous authors Paper under double-blind review
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 oper- ator will result in the enror of the optimal value. In order to address this issue, we introduce the idea of extragradient and propose a novel accelerated variance re- duced stochastic extragradient descent (AVR-SExtraC]] algorithm, which inher- its the advantages of Prox-SVRG and momentum acceleration techniques. More- over, 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- non-strongly convex problems. Finally, our experimental results show that for ERM problems and robust face recognition via sparse representation, our AVR -VR-SEXtraGD can yield better performance than state-of-the-arr 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.
INTRODUCTION
In this paper, we mainly consider the following composite convex optimization problem:
P(r) dnd F(x) F(x) + R(x) = Σ
- M(x)+ ((()))
min ZER
where F(x: R TR. is the average of smooth convex component functions fa(), and R(x) is relatively simple convex function (but may not be differentiable). In this paper, we use ||- to denote the standard Euclidean norm, and ||-I|ı denote the é -norm. Moreover, we use P. denote the real optimal value of P(.). and P. denote the optimal value obtained by algorithms.
This form of optimization problems often appears in machine learning, signal processing, data sci- ence, 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 represen- tation learning for object recognition. Specifically, for collection of given training examples {(a1, bi)..., (an, b,)),, where a, Rd. b, R (i 1,2, ..., n2) and a; is feature vector, while b, is the desired response. When fx(x) = - (a. x b2, we can obtain the ridge regression problem by setting R(x)= ||=. We also get the Lasso or Elastic-Net problems by setting R(x)) = X|| R(x)= | 2 Xa |ær|]1, respectively. Moreover, if fi(x:) log(1 +exp(=bbx a;)), will get the regularized logistic regression problem.
1.1 RECENT RESEARCH PROGRESS
The proximal gradient descent (PGD) method a standard and effective method for Problem 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 conver- gence rate of O11TT2) for non-strongly convex problems, where denotes the number of iterations.

---

Under review as a conference paper at ICLR 2020
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). D) because of its significantly lower per-iteration complexity than deterministic methods, I.c., O(d) vs. (nd)).
Besides, many tricks for SGD have also been proposed, such as Loshchilov & Hutter (216)). How- ever, the variance of the stochastic gradient may be large due to random sampling (Johnson & Tong (003)). 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 (2012) developed a stochastic average gradient descent (SAG) method, which is randomized variant of the incremental aggregated gradieni method proposed by Blatt et al. (2007). Then stochastic variance reduced gradient (SVRG) (Johnson & Tong (013)) was proposed, and has been widely introduced into various subsequent optimization algorithms, due to its lower storage space (i.c., (dd) than that of SAG (i.c.. O(dd). SVRG reduced the variance effectively by changing the estimation of stochastic gradients. The introduction of a snapshot point & 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 well as their mini-batch version (Konečný et al. (2014)). And their asynchronous distributed variant (Ruiliang al. (2016)) is also been proposed later. More recently, [in & Tong (014)) 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 solve the strongly convex optimization problems. In order to solve the non-strongly convex problems.Zeeyan Zeyuan & Yuan (2016) proposed the SVRG++ algorithm. Besides, to acceerate the algorithm and reducing the complexity, by combining the main ideas of APG and Prox- Nitanda (2014) proposed an accelerated variance reduction proximal stochastic gradient descent (Ace-Prup -ro-Prrx-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 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 inneriteration. Therefore, the idea of extragradient is our main motivation. In this paper, we propose 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 momen- tum acceleration, is proposed, called accelerated variance reduced stochastic extragradient descent (AVR-SExtraGID).
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 SEx-SED))) obviously better than the popular algorithm. Prox-SVRG which confirms the advantage of extragradient. For the widely used accel- erated algorithm, Katyusha, the performance of our algorithm is still improved.
2

---

Under review as a conference paper at ICLR 2020
2
RELATED WORK
2. BASIC ASSUMPTIONS
We first make the following assumptions to solve the problem (
Assumption (Smoothness). The convex function F(.) L-smooth, i.e, there exists constant L 0 such that for any I, ER, [[F (F))) = -
Assumption (Lower Semi-continuity), The regularization function R(-) is lower semi- continuous function, i.e., Vay ER"
lim inf R(x) 2 R(xa)-
But not necessarily differentiable or continuous.
Assumption (Strong Convexity). In Problem [. the function R(-) pu-strongly convex, i.e., there exists a constant >>> 0 such that for all y R it holds that
R(x)= 2 R(y) + (G, x 4) + 2
11
211
(2)
2
where G GERR(y) which is the set of sub--uuuuid 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
v(g((=-1) (i,(==-)) (ā) + VF(T);
(1=-1-
where 7 is the snapshot point used in SVRG, V/ is the variance reduced stochastic gradient estimator, and Prox,(: is the proximal operator. Although Prox-SVRG can converge fast, because of proximal operator, final solution has the deviation, which makes the solution inaccurate, thus Prox-SVRC still needs to be further improved, which is our important motivation.
classical method for solving variational inequality problems, and it generates an estimation sequence by using two pro- jection gradients in each iteration. By combining this idea with some first-order descent methods, Nguyen et al. (2017) proposed extended extragradient method (EEG) which can effectively solve the problem and can also solve relatively more general problems as follows:
The extragradient method was first proposed by Korpelevië (1976).
P(x) def F(x)+
min =ERd
where F(x) is not necessarily composed by multiple functions (x()). Unlike the classical extragra- dient method, EEG uses proximal gradient instead of orthogonal projection in each iteration. The main update rules EEG are
Prox (Ix 8 VF(*+)): Je+1 = Prox as (#x - Og (F())))
where and ag are two step sizes. From the update rules of EEG, we can see that in each iteration, EEG needs to calculate gradients, which will definitely slow down the algorithm. Therefore, the algorithm needs to further accelerated by an efficient technique.
2.3 MOMENTUM ACCELERATION AND MIG
Firstly, we introduce the momentum acceleration technique whose main update rules are
Udw. BUdw.. (1 B)dwa; W. Wt-1 Orlde
where dw is the gradient of the objective function at w, 3 is parameter, and is 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 wa after using momentum
3

---

Under review as a conference paper at ICLR 2020
Algorithm 1
Input: Initial vector To, the number of epochs S, the number of iterations m per epoch, the step sizes 1/1 momentum parameter 9, and the set K.
Initialize: J" zi Fo, p 1tp..
1: for ........5 S do
2: Compute (F (7=-111) )
3: 8. = 3 (SC) or B. 2
3+1 (non-SC);
4: for = 1,2 m do
5:
Pick l uniformly at random from n1,
6:
if k E K then
7:
- 1/2 1/2
Prox R p 1n1 Vf. (3.4 (1-
8:
o Prox 1k-1/22
1/2
VI 3. 1/2 + (1 Ba) )z )z--1)
9:
else
2t Prox (ot
111 Vf
(1 11),,² ( ));
11:
end if
end for
13:
3.(2 k= ph 1h-1)--1
m
k= p² 2 1
+ (1- (1-BB)) (SC)
2
or A
8. kk=1
1/3
+ +(1 - )
1 (non-SC);
2
14:
20
++1 zimi
15:
end for
Output: S8.
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 mo- mentum acceleration of MiG embodied in each iteration as follows:
パズ 3, (1 B.)
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. There- fore, we can also use this acceleration technique to accelerate our algorithm and address the issue of slow convergence due the calculations of two different gradients.
OUR AVR-SEXTRAGE METHOD
We note that EEG requires computing two full gradients in each iteration, which will take 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 re- duce the per-iteration computational complexity, and further propose an efficient variance reduced stochastic extragradient descent (VR-SExtraGD) algorithm. Their main update rules and the de- tailed algorithm of VR-SExtraGD can be found in Appendix C
On the basis of "R-SExtraGD, we refer to the momentum acceleration technique proposed in MiG, and propose innovative accelerated variance reduced stochastic extragradient descent algorithm, called AV S... It is used to solve non-smooth (both SC and non-SC) optimization prob- lems. To further accelerate the algorithm and address the issue of slow convergence speed caused by two gradients in each inner-iteration, only part the iterations are updated by extragradient descent. Our
algorithm is outlined in Algorithm
Firstly, we give some explanation for Algorithm For our AVR-SExtraGD, we need to compute full gradient of Fzz). And Step 3 in Algorithm 6 to Step 8 are the update rule AVR-SExtraGD, and Step is the update rule of MiG. Here we only use AVR-SExtraGi in the set K. Step 13 is the formulation of the snapshot point. Finally,
[ is the selection of momentum parameter. Step
4

---

Under review as a conference paper at ICLR 2020
give the set of the start point of next inner-iteration in Step 14. Moreover, output is the snapshot point of the last outer iteration.
And for 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, get the conditions: 1/1 S 27. 7/2 2 7/-
AVR-SExtraGD, we use one more trick to speed up the algorithm, that is, only part of the iterations (i.e., when & E K) are updated by extragradient descent, and the rest of the iterations 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 be seen in Section 5.3
For the momentum parameter B, when P(-) a strongly convex function, we can set / as a constant which is generally set 0.9. And B is also set 1-ypuz in Acc-Prox-SVRG, while set 3 = 0.9 in our AVR-SExurGDD. However, when P(-) is non-strongly convex, the value of / in each iteration is no longer fixed. We set B, as decreasing sequence, which satisfies
I-y/m2
1-8
Particularly, in AVR-SExtraGD.
set 3, .4 which satisfies the inequality defined above.
As we all know, for the general GD method, the iterate Fy in each iteration eventually converges to the real optimal point of the function, so there 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 the idea of extragradient, we know that the update structure of EEG can make use of the curvature information the objective function. Although we change the original EEG into 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 extragra- dient. is, although the method of extragradient value, it can improve the had result brought by the gap, and obtain a better result after every inner loop. Thus, "RSSExxtaGD can improve the accuracy of the algorithm.
not directly reduce the gap of the optimal
In summary, our AVR-SExtraGD method combines the advantage of ProX-SG for solving non- smooth optimization problems, the advantage of EEG, and the trick of SVRG 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.
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 Vi, F'(-) denote Vf, that defined in (3) in the analysis of AVR -VR-SExtraGD, We give some key lemmas, which are important to prove the convergence of AVR-SExtraGD Appendix 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 (Strongly Convex). Suppose that Assumptions 7 and 3 hold, and let x= arg ming P(z). In addition, assume 171 1/2 = 0 and L3
L
" Then, by appropri-
ately choosing n, 3 and m ===(n) Algorithm 7 achieves an c-additive error with following oracle complexities in expectation:
OVVKn kn log P(zo)-P(E..) (n log P(a))-((..))
which also means that for SC problems, the oracle complexity of Algorithm I is O((n + /Kn) log P(zo)-P(a.)
5

---

Under review as a conference paper at ICLR 2020
This result means that for strongly convex problems, WRR-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 be guaranteed by the follow- ing theorem.
Theorem (Non-Strongly Convex). Suppose that Assumptions
and 2 hold, and let I.
arg ming P(x). In addition, assume ?/ 1/2 1 La
1
and
B, 2 0. where is
2 constant. Then by setting 3g = 3t4 we have
4(1-3:) (S+4)BB)
La (S (8+4)2m 110 - xz xx.1 11?
-
(P(20)-P(x..)
which also means that when we choose m (n)), Algorithm achieves the following oracle com- plexity in expectation:
O(n P(xn)
nL 20 x.112
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 ! + + v )) 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
EXPERIMENTS
this section, we evaluate the performance of AVR-SExtraGD and compare with its counterparts including Prox-SVRG and Katyusha real-world data sets, whose information is shown as Table in Appendix
Besides, for these real-world data sets, 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
The Number of Inner-Iteration: The number inner-iterations of Katyusha and Prox-SVRG is usually set as m.= 2n. Our algorithm adds 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 caleulating 3n stochastic gradients. What's more, the reasonableness of such setting can be found in (Sebouuh et al. (2019).
We our step sizes as: 7/1 - .े. 1/2 = We note that the selected step sizes do satisfy the conditions requested in the remark of Section Nevertheless, we can see from the ex- perimental results that our algorithm still converges well, which means that in practice experiments, we can choose larger step sizes to improve the convergence speed.
Step Sizes:
For fair comparison, we implemented all the methods in C++ with a Matlab interface, and performed all the experiments on 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 -nom regularized logistic regression, whose models can be found in Appendix
Figure I 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 extra- gradient and the momentum acceleration able to improve Prox-SVRG efficiently. Moreover, for

---

Under review as a conference paper at ICLR 2020
O--rro--Vi AV
10
10
+ Fnbyurts
10
P
10100
10-
10
10-3
150
1003
1500
Running time tsec)
Running dine (SBC)
AVk AVR-SEA0U0
30
Calents
P
10
10
10-2
16
102
15
20
150
1003
1500
2020
Running tmm (sec)
Running time (sec)
Running time (Sac)
(a) a9n
(b) Covtype
(c) revl
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 r-axis corresponds to running time.
the two problems, we propose the asynchronous sparse variant of WR-SEExraGD 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 revl and real-sim, as shown in Table 2 The results are shown in Figure 2 which verify that the asynchronous variant of AVR-SExtraC 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 more comprehensive compari- son, we compare the performance of more algorithms for Lasso and the (-norm regularized logistic regression on a9a and Covtype, and the results are shown as Figure 4nd Figure 5 in Appendix
22
BROUGE
BRANGO
KOGGA
KAGGA
of Eifccin
Sunber effectee
Sunter of efistine
Suntor effccino
39*
30*
30
300
120
106
(a.1) Lasso, revl
(a.2) Lasso, real-sim
(b.1) Flastic-Net, rov
(b:2) Elastic-Net, real-sim
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 repre- sents the gap of objective value, and the z-axis corresponds to the number of effective passes (top) or running time (bottom).
5.2 RESULTS ON FACE RECOGNITION
We also apply our SXx-SEx as well as Prox-SVRG and Katyusha to robust face recogni- tion via sparse representation (John al. (2009) the AR and Yale. We the loss function
7

---

Under review as a conference paper at ICLR 2020
in the training process the same function the Lasso and Elastic-Net problems. For approxi- mately equal time, the number of outer loops is 200 for Prox-SVRG and AVR- WVR-SEEtraGG, and 50 for Katyusha. In order compare the results reasonably, implement all the algorithms for 20 times and get the average and standard deviation of recognition rates, as shown in Table
Table I: Comparison of Recognition Rates on the AR and Yale Datasets.
Problems
Algorithms
AR
Yale
Prox-SVRG
0.6000 + 0,0648
0.6200 + 0.0447
Lasso
Katyusha
0.5880 + 0.0832
0.7480 0.0415
AVR-SExtraGD
0.6200 + 0.0756
0.8100 + 0.0265
Prox-SVRG
0.5630 0.0580
0.6400 0.0394
Elastic-Net
Katyusha
0.5560 + 0.0738
0.6870 + 0.0433
AVR-SExtraGD
0.5800 + 0.0634
0.7140 0.0297
The results in Table show that the recognition 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 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
CB5
1003-Fo1
1011
E87
2:00
220
(a.1) a9a
(a.2) aBa
(b.1) Covtype
(b.2) Covtype
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 r-axis corre- sponds to the number of effective passes ((a.1) and (b.1)) running time ((a.2) and (b.2)).
where, K 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 not good for running time. Thus, for a9a, we choose K 25. As for Covtype, obviously, K = is the best choice.
that the extragradient is calculated every integer multiple of (n
6 CONCLUSIONS AND FUTURE WORK
In this paper, we mainly considered the non-smooth optimization problem in large-scale and high- dimensional settings. By introducing the idea of extragradient and momentum acceleration, improved the classical Prox-SVRG and then proposed novel algorithm, called AVR-SExtraGD. From 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 WERR-EExtaaDD 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 con- firmed 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 (002);; SShale--swward & Tong (2014)) which is a proximal variant of SDCA (Shalev-Shwartz & Tong (2013)), and will certainly improve the performance of these algorithms. Moreover,
also rewrite our algorithm into the form of mini-batch, whose computation of gradient evaluations
can be parallelized (Agarwal Duchi (201T) Dekel et al. (2012)).
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
A. Agarwal and J. C. Duchi. Distributed delayed stochastic optimization. In Decision and Control, 2011.
Amir Beck and Mare Teboulle. fast iterative seiinkage-trrsholddee algorithm for linear inverse problems. Siam Imaging Sciences, 2(1):113-22)) 2009.
Doron Blatt, Alfred O. Hero, and Hillel Gauchman. convergent incremental gradient method with constant step size. Siam Journal on Optimization, 18(1):29-51, 2007.
Aaron Defazio, Francis Bach, and Simon Lacostejulien. Saga: A fast incremental gradient method with support for non-strongly convex composite objectives. In International Conference on Neu- ral Information Processing Systems, 2014.
Ofer Dekel, Gilad Bachrach Ran, Ohad Shamir, and Xiao Lin. Optimal distributed online prediction using mini-bate hani-batches. Journal of Machine Learning Research, 13(1):165-22) 202, 2012.
Daniel Gabay and Bertrand Mercier. A dual algorithm for the solution of nonlinear variational problems via finite element approximation. Computers and Mathematics with Applications, 2(1): 17-40, 1976.
Wright John, Allen Y Yang, Ganesh Arvind, Sastry Shankar, and Ma Yi. Robust face recognition via sparse representation. IEEE Transactions Pattern Analysis and Machine Intelligence, 31 (2):210-227, 2009.
R. Johnson and Zhang Tong. Accelerating stochastic gradient descent using predictive variance reduction. In International Conference on Neural Information Processing Systems, 2013.
Zhou Kaiwen, Shang Fanhua, and Cheng James. simple stochastic variance reduced algorithm with fast convergence rates. ICML, 2018.
Jakub Konečný and Peter Richtárik. Semi-stochastic gradient descent methods. Mathematics, 3:9-, 2013.
Jakub Konečný, Liu Jie, Peter Richtárik, and Martin Taká. ms2gd: Mini-batch semi-stochastic gradient descent in the proximal setting. IEEE Journal of Selected Topics in Signal Processing, 10(2):242-255, 2014.
G. M Korpelevič. An extragradient method for finding saddle points and for other problems, Mate- con, 12:747-75, 1976.
John Langford, Li Lihong, and Zhang Tong, Sparse online learning via truncated gradient. Journal of Machine Learning Research, 10(2):777-801, 2009.
Rémi Leblond, Fabian Pedregosa, and Simon Lacoste-Julien. Asaga: Asynchronous parallel saga, 2016.
Xiao Lin and Zhang Tong. A proximal stochastic gradient method with progressive variance reduc- tion. Siam Journal Optimization, 24(4), 2014.
L. Lions and B. Mercier. Splitting algorithms for the sum of two nonlinear operators. Siam Journal on Numerical Analysis, 16(6):964-979, 1979.
Ilya Loshchilov and Frank Hutter. Sgdr:
Stochastic gradient descent with warm restarts. In ICLR 2017 (Sth International Conference on Learning Representations), 2016.
Horia Mania, Xinghao Pan, Dimitris Papailiopoulos, Benjamin Recht, Kannan Ramchandran, and Michael I. Jordan. Perturbed iterate analysis for asynchronous stochastic optimization. Mathe- matics, 18(1):51-52, 2015.
Trong Phong Nguyen, Edouard Pauwels, Emile Richard, and Bruce W. Suter. Extragradient method in optimization: Convergence and complexity. Journal of Optimization Theory and Applications, 776(1):1-26, 2017.

---

Under review as a conference paper at ICLR 2020
A. Nitanda. Stochastic proximal gradient descent with acceleration techniques. In International Conference on Neural Information Processing Systems, 2014.
R. Tyrrell Rockafellar. Convex Analysis. Princeton University Press, 1970.
Nicolas Le Roux, Mark Schmidt, and Francis Bach. A stochastic gradient method with an exponen- tial convergence rate for finite training sets. In International Conference on Neural Information Processing Systems, 2012.
Zhang Ruiliang, Zheng Shuai, and Kwok James T. Asynchronous distributed semi-stochastic gradi- ent optimization. In Thirtieth AAAI Conference on Artificial Intelligence, 2016.
Ernest K. Ryu and Yin Wotao. Proximal-prxximaalgraaeent method. UCLA CAM Report, pp. 17-51, 2017.
Mark Schmidt, Nicholas Le Roux, and Francis Bach. Minimizing finite sums with the stochastic average gradient. Mathematical Programming, 162(5):1-30, 2017.
Othmane Sebbouh, Nidham Gazagnadou, Samy Jelassi, Francis Bach, and Robert M. Gower. To- wards closing the gap between the theory and practice svrg, 2019.
Shai Shalev-Shwartz and Zhang Tong. Proximal stochastic dual coordinate ascent. Mathematics, 2012.
Shai Shalev-Shwartz and Zhang Tong. Accelerated mini-batch stochastic dual coordinate ascent. Advances in Neural Information Processing Systems, pp. 378-385, 2013.
Shai Shalev-shwartz and Zhang Tong. Accelerated proximal stochastic dual coordinate ascent for regularized loss minimization. International Conference on International Conference on Ma- chine Learning, 2014.
Zhang Tong. Solving large scale linear prediction problems using stochastic gradient descent algo- rithms. In International Conference on Machine Learning Omnipress, 2004.
P. Tseng, On accelerated proximal gradient methods for convex-concave optimizztonn Siam Journal on Optimization, 2008
Allen-Zhu Zeyuan. Katyusha: the first direct acceleration of stochastic gradient methods. STOC, pp. 1200-1205, 2017.
Allen-Zhu Zeyuan and Yang Yuan. Improved svrg for non-strongly-comvex sum-of-non-convex objectives. ICML, pp. 1080-1089, 2016.
10

---

Under review as a conference paper at ICLR 2020
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 ( can be solved by proximal operators and find out the reason for the introduction of the error. According to Prox-FG, we have
Ik Prox R
(5k-1 TJ (F++-))))
mi
1
arg min (R(u)
||u (Ik-1- M/ VF (F
uER
27
arg min (R(u)
Th
VF (F(xx-1)* (u xk-1) 277
1 |/u xx-1ll2)
uER
2
arg min (R(u) FI + VF(2x-1) zk-1) |/u 11
HERd
2nk
arg arggmnn (F(u) R(u)}.
WERd
The final approximation is obtained by the second-order Taylor expansion of F(u) Tx-1- From the above analysis, we can see that when using proximal operators to solve the problems with the --normm regularization, the iterate zę each iteration is estimation of the optimal point, the real optimal point. Therefore, in the last iteration, the final output point is also an estimation of P., which results the deviation of the optimal value.
B PROOFS OF AVR-SEXTRAGD
B. KEY LEMMAS
Lemma 1. If two vectors Rk, Fk-1 E Rdd. satisfy the following equality,
Tk arg min 1
- 1|1----a In -n- (Vi, 1 +[()))
21j
with constant vector V., (xx-1) and convex function R(-), then for Vu 1Rd,, we have
1 1|==-1-===11-- -2 -
(V. Is xx-
21 || -ul 2n [[(=)
Moreover, if R(-) is p-strongly convex, the above inequality becomes
1 2m 1 11 1 ul12
1+
(V,, F(T= u)
1 uuc-uul22 +RI)+R((u) R(xx).
2m
2m
Lemma (Variance Bound). Suppose each function se(-) is Le-mmooth, let ((rF(
(( -i VF which is the gradient estimation operator used in Algo-
rithm 1 Then the following inequality holds
R VF
F(r S - 11 1-11
Jk -2))
The detailed proof of Lemma I can be found in Kaiwen et al. 2018), and the proof of Lemma
2 can
be seen in Zeyuan (2077). and thus we omit the proots here. Next, we give the proofs of Theorems
1 and 2
11

---

Under review as a conference paper at ICLR 2020
B.2 PROOF OF THEOREM
Proof. In this part, we consider one particular epoch and omit the number of outer iteration (except
h--1 and (*). We assume the parameters v) and |3 satisfy the following inequality,
1 1-8
LB + <
(4)
Let - (1 .2x-1/2=BBr, (1)))=
Thus, we can obtain 2x 1/2 kk-1
8(1k-1/2- -x Thus, according to the L-smoothness of F(-), we can obtain
(4 2x 1))
L
", xz-
-
2
Then by using 4 we have
1
1-8
1 ((t
P (
R(5"111
-Ik-1)
3
3
1
LB
1 1 3k 111-
1/ 1/2 xx 11
21
2(1
+ +(VF(*+-1) Vi, F(xx 2o x2-1/2 2k xk-1)
According to Lemma I with Tk-1, 2b 1/21 u= v. and using the Young's inequality to expand
-VF( (6-11) - with the parameter and taking expectation with
respect to the sample is, we have
1-3
EP EP(88-11)) R(z.)+
R(1 F(Ex-))+B(V.. - xK-11)
3
1
1 1+
Ixx
2
E Elg.,
22 1/211
111=2-112-0x--0
2n
2n
2(1-3)
0
E
1
1/2
36
2
20
(6x
-v.
F(
12

---

Under review as a conference paper at ICLR 2020
We set == 1g 1-3 > and apply Lemma 2 then
1-B
1
(((r)
)
1(x
8
3
1
1+77
1-B B
11
11
11 2+
[F(2
)-F
21
2n
3
1
1-8 18-1
1
1-3
+B Vi, Fi,F(E F(t 1) 20 +
x
(82-1-5*-11 -2-
1
3
1-8
+ 1
< <R(r.)+
+
R(
F(ok-1)
1+1144
1- B
+
C. 11-
BB|| 1/2 1/2 1/
1) F(tx-1))
21
2n
B
1
+
Bi F(ix (1), 30. +(1-3)=xx -
E(
3
<R(x.)+ + 1-3 R(5--1)+ 1
<
F 1
+
10+ 1111
1+1
El -
1- B
B -F(A-)))(((AiI)))
21j
2m
1
+
F(3x, + +11 11))))x1111
F(xx-1)
B
B
1-3
RR(*-111 + F(fx-1)+ 1-3
<R(x.)+
+
) (
3
+
1-3
F(#x-1) 1
F((x-1)+
_
1:. 1 111
1+1/4
E
1/211
3
211
21
1 1-3
1+m
P(0 ((
- -111--
11..-- 11-
E
Fr.
1/211
B
2n
2n
The third inequality holds due to E,V, F( VF VF ( and the convexity of F(.), then
get
1-8 E E(P((x=1/2) p(x.)]s
1
1 1+11/1
2n || 11-1112-
Elix. Ik- 1/2 11?
8
21
Moreover, because 1 -1--3))
we can obtain = (1-3))=) Thus, it is
not hard to know
1 B[P(t))
1-3 P(c.)]
_
1
||.. Ia 1/2ll
1+
E E1
-2 1211
B
B
2n
2n
and is obvious that We set D1 3 BBk-1/ztus (1-
How 2n
< 0, then we have
2n
E[(((u)) - -( 1-8
-PP(-)))((x)1) 1 P(x))]+ ||,0- Fk
1
1|2
1 1
E E| - xx (5)
8
4n
4n
13

---

Under review as a conference paper at ICLR 2020
By setting p= tn and summing ( over B=1,.... m with increasing weight p²-1, have
Pm
1- 3
((P()))-P(xx)1
Vz 11
[P(E --P(== 100 2.ll?
4n
B
4n
km
Because, for SC problems, set x='
k=1
Pk-
Lk=1 p* yk in Algorithm
! have
1- 3
E[P((*)-P(a.
|
12.12 1125
[P PIP(0=11 -(.-)(())))))))))))))))))))))-
}]+
1 2.11²
4n
4n
Then, according the convergence analysis for SC problems in (Kaiwen et al. 2018
get
a similar result. That is, for case with
m2 3. we set 1)
JamL 3=
and m m
3r 2
then we can obtain
Sm
1 ) O(l+
-(P(#9)-P(xa])
-(p()))-((r)))
3nx
We note that 0 =x0=xo so we get
Sm
E|P(
O(1+
-((())))P(z)))
3nk
which implies that the oracle complexity in this case to achieve an e-additive enror is
( / log
Plao P(z.)). However, for the case with
11 - B = 1/2 and O()).
then we can obtain
(2) { -((x))) -O(P(=")-P(z.))
We know that 3 =ro. so we have
2
E(P(ES)-(EE)))
(3)
-(((z))-P(z.)),
which implies that the oracle complexity of AVR-SExtraGD in this case is O ( n log P(zo)-
B.3 PROOF THEOREM 2
Proof. In this part, we also omit the number of outer iteration s (except is-1 and i*). Due to
f 1/2 1/2 -- can get
P( P(300=11/22 -3) 330=-R(B0 R(3r (1- (1-8)=+-1) + F(Fx-1/2)-
14

---

Under review as a conference paper at ICLR 2020
From the convexity of R(-) and L-smoothness of F(.), we obtain
Reh.: xx-
T232
2 ||t
|, <
Lagf
|ikk-/22 - xE-1 1|
- F(t
2
21(
where the second inequality holds by using the Young's 's inequality with the parameter L(a - 1), where is small constant. After applying Lemma and taking expectation with respect to the
15

---

Under review as a conference paper at ICLR 2020
sample i,, have
E (F 11, -xx-1))
LaB?
+
2 1004-2k-111 -10,-2
1 22 1
+ 2L(a-11 B| B|
< <3R(x.)+ (1-3))))(1-3))(( (F
-xx-)))x))))
LaB²
+
(1|2, kk 1 - 1/21/
+ a-1 [F( EE V. 81 -80-111
a-1 [F(5-11- ((xx11)
F( -)3 f a- 1
Taß
+ 2
105--2-- xら (10.-
- - 11
(3R(a.)+() +11 -1 R( + F
[ 1)+ a-1
[F(;-1 1 F(
+F(3s.+(115 +11-3- a-1 a
. -F ((x
+ LaB?
2 (1|2, - xx- 1 - 1122//11 1/)
(11
($k 1)+
1) -((xx
a-1
1
1
+3F(z.)+(1
F
)
F( 1)-1)) (#x-
a
a
Laj?
+ 2 (1|2, - x6- -
-
La,32
= (1 (1-3) -
(1|x, (11x.- 111-- xx- 1/211)
The second inequality holds due to Lemma The reasons why the fourth inequality holds
VVV F(2x-1) -VF()-- and the convexity F(.). Besides, we need to assume 1-3- - 20
in this step. Then, we get
Lafz2
-P(()))
2 -11x.-24-11 xx 21 Ia x121121
16

---

Under review as a conference paper at ICLR 2020
Moreover, because žx-1 = - (1----111818))) B) we can obtain 2y. =x= (1- (1-3))=-1
2. Thus, it is
hard to know
Lag? (11,,
2g 1/211 -E xx 11
Let yı = - +(1-3) we have
La
-11x.-IA--1 xx-1 B|,,, J& 112))
That is.
(1-3)
La 1|22-1 -- - 2% l1²).
8a B[P(y)) P(x.)1
Since have -== =
E 24 1/2
Σ k= Uk in Algorithm and then by
summing the previous inequality over h: == 1,..,, m and according to a
=x we obtain
(1-3a)
La
8 E[P(
P(x))]
P((x))
(1|=, -00---1f zzl1² 1172-11a -1,11 -20 112).
83
4m
We set =,= 844
and can easily obtain
2
1-8. 83
Then by summing the previous inequality over
3
== 1, S, we can get
(1 (1-31)
La (1|=, - x/ -1130 - - 112)
BS
8f
4m
Then we have
4(1-3:)
La
- ((t0)-P(xx.))
(S+4)2m 1 - x.
(S+4)287
which holds because ||2 0. We note that ~0 2b z0. so we get
La 41)-3:) (P(z)) - P(x+)) + (S+4)2m 11:0 - xz 112.
-[ P(x,)]
(S+4)287
In other words, by choosing m the total oracle complexity is
P P(xo) P(s.)
nL [r - v. 1
0 n
+V
c
Finally, we finished the convergence analysis of AVR-SExtraGD. In our Algorithm [ 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-SExtraGH converge to P.. Therefore, the method in Algorithm I will not affect the results and can accelerate the algorithm.
make the objective function
17

---

Under review as a conference paper at ICLR 2020
Algorithm 2 VR-SExtraCn
Input: Initial vector Z0, the number of epochs S, the number of iterations per epoch, and the step sizes 1/1 7/2-
Initialize: 30 = x².
1: for 8= ,,, do
2: n VV
3: z8 -8-5"11 (SC) or -0 - (non-SC);
4:
for k= 1=1,2,.... do
5:
Pick is uniformly at random from [1,...n]]
6:
Vf,, - Vin - - (ī+ ) 1,
7:
- = Prox 11 (5k-1 - 771 v/ (x 1));
8:
Vf. (o Vf., 1/22) Vfn, (I (3--1)+
" = Ri (1 1-12 1/2 Vl, (-
9:
10: end for
11:
8- -11 E 23:
12: end for
Output: 35
C SEXTRAGD AND TR-SEXTRAGD
Based on the update rules of BEG, we first consider and propose the stochastic variant of the algo- rithm, 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:
1k-1/2 Prox m/ (#t-1 1/1 VSs (IK-1)); Fk = Prox (Ik-1/2 1/2 VS (xk-1/2))
The update rules of VR-SExtraGD:
Øk-1/2 Prox [ 1n Vi,, (Ir--1)): 3kk Prox 1k-1/22 1/2 Vi,, (z
where Vie (-) the gradient estimation defined in
We note that one difference between these two algorithms and EEG is that we change T&-1 in Step two to 1/21/2- which will beneficial to our theoretical analysis, but will not cause any major change to the results of the algorithms. Thus, 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 shown 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 and are used to prove Lemma which is an important lemma to prove the conver- gence of VR-SExxraGr
Lemma 3. Let R(-) be a convex function from Rd to I. and me Then, for all x, Rd.
Prox n (x:) Prox (v)ll Ia vll-
18

---

Under review as a conference paper at ICLR 2020
Lemma 4. Let P(z)=F(s)+RR()) and (F is Lipschitz continuous with parameter L. For any Rd and arbitrary u Rd, we define
1 (x -- x'), 1
x' = Prox, R -o))
A=v-VF(a))
where 1) is step size that satisfies 0 < k S +. Thus,
know that for any TR..
P(y) 2 +(x')+ - x) + " 11l1l1 + A - -y)-
Lemma 5. Considering P(x) as defined in Problem i and Vfi (v) defined in 3 where is an arbitrary stochastic sample, and I= arg min, P(x). We have El (v)] (F and
E| [f, VF 4L[P(0) - P(x.) P(z) P(x.)] )..
Because Lemma 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 (0144), and thus can be easily proved, so we also omit the proof here. Similarly, according Lemma 3.4 in Lin & Tong (2014), Lemma 5 can be also easily proved, and thus we will not give the detail about Then we can prove the following lemma by these three lemmas.
Lemma 6. For all randomly selected sample and h, if
v -rox 16-11 (1-nt((((h))
(6)
we have
Ellu - xx.12 || xx112 27)EP(()) P(x-)] 8L7 P(x,) P(ě) P(x.)),
where x. arg ming P(r).
Proof. First, define stochastic gradient mapping follows:
g = (h - v) = - Prox (h (h- (I-
According to this definition, 6 can be expressed more succinetly follows:
ng..
Then we consider the distance between and x..
||0 x. 112 | n9 xr.1² 110 x..12 2ng x.) + 1
19

---

Under review as a conference paper at ICLR 2020
Applying Lemma 4 with = h, (h), xt and y Ix. have
9" (h- x.) + 2 |1 P(x.) 42 v.m)
where 4 = (h) - vh).). Thus we have
||u- x. 1.1 2 | x.1l - 2n -v-I...
Then we can give an upper bound of -2n (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, (1)
So, we can obtain
-2m (o xx) -2m (v - h) - 2 (h- I.))
2n|| /11 21 3.2 (7 x..)
S 2n| - 1 Vir (1)) - (h - V]FF())) - 2n x.))
= 2n z.).
The first inequality follows from the Cauchy-Sehware inequality, and the second inequality holds
due to Lemma
3 So, we have
h - x. x21 Pn) - P(x.) + 20 27 (h x.).
Then, we take expectation on both sides of the above inequality with respect to is to obtain
Elhh x. S ||u x.1 (n(E P(x.)] 2| 2n
xx)).
(7)
can be noted that both h and x. are independent of the random variable in. and can easily
know that EA2 = 0. So
EI x.)] = (EAR)) (hh xx) = 0.
(8)
Substituting Lemma and into 7p. we obtain
Elih x. 2 < || 2.11 21 (h) P(z.)] + P(x))+((5) P(x))) (9)
20

---

Under review as a conference paper at ICLR 2020
D.1 FOR SC PROBLEMS
Firstly, we can prove the convergence of VR-SExtraGD for strongly convex (SC) problems, which showed by the following theorem.
Theorem (Strongly Convex). Suppose that Assumptions and hold, and let I
arg ming P(z). In addition, assume Tι > 0,72 > 0,m 2 4L and m2 2 ALoB and m suf-
ficiently large so that
4L + 1)mi + mn
< 1.
1mn(112 4TaR)
m(p2 4
Then VR-SExtraGD outlined in Algorithm aachieves linear convergence in the expected form, which can be formulated as follows:
P P(x.)) (P((()))) P(x.)).
(10)
Proof. According to Lemma 6 and the update rules of VR-SExtraGD,, we can easily get:
1/2 x. S 1| x.112 2m [EP [EP(((-112)) -(x.))
(11)
+ 8Lni(P((x-1) - P(x.) + P P(x.)
and
Bl 1.112 < 10 1/2 x2.12 20112 BP(xk) P(x.)]
(12)
+ P - P(x.) P(T) P(s.)).
Then, substitute 111
into
to obtain
E b2 - x. 12 rk-1 2,112 27t1 EP([k- 1/2) - P(x,)]
(P))(P(( P(x.) + P(t) - P(x.)) - 272 [P(()) - P(x.))
(xk-112) (xx.) P(क) P(xx)).
Suppose 77 2 4Ln2. i.e. -271 5 -8L1/- we can get
E| E1|2 12 12 < || 2+112 EP P(æ+)]
8L17(P((441) P(xx) + P(š) P(x+)] 2122 212 EP(ck) P(xx)]
+ {{ -((x)) 8L - P(x.)]
= =1 18811 -(xx)) + P(T)
P(x.)]
-2m([P((xx) P(x.)) SL1BIP(3) P(x.)]
21

---

Under review as a conference paper at ICLR 2020
By summing the previous inequality over lt 1.... m, we obtain
1| - -x112 + 21/2 ( P(xx)] + 2(112 4LnH) m.
EP(p))) P(x.)]
$ - 1 (LL)(())) - -
n2) PP)) mil
-(x)))
Since 172 -LT7/ < and from the algorithm of VR-SExtraGD, we know 2o = E. Therefore,
= 1 x.11? + 8L[(m + 1)mî + m - P(x.)) 2(122 - 4Lnft Σ BP(xs)) - P(r.)) =
Because in a fixed epoch, such as the s-th epoch, there are T" 1
m E 2g and _01 To. and
according to the convexity of P(.), P(o*) S Σ P(xx) can be obtained. Therefore,
2(12 2112-44nnmmBPP)e))PP() < [m 1)m
-x.11 (13)
Because of the convexity of F(-) and the strong convexity of R(.), we know P(.) also strongly
convex, then we have | 1 _ (IP(F~11) - P(xx)]. Thus.
2 + 8L((m + 1)li + (PP - P(x.)],
2(122 4B P(r.) <
which is equivalent to
E(P(**) - P(x.)] s 0| - P(x.)).
where
1
4L + 1)ml + mn
um((12 - 4Ln)))
m(12 4L,1))
At last, we have
E[P(E - P(x,)) )1 0E|P(E 1-00-11-PPAA P(xx)]
I <0'E|P(>S-3) -P(xa)
S s <09(p(>0) P(xx)]
We note that 0 To. so we can obtain
B[P(55) P(x.)) P(x.))
22

---

Under review as a conference paper at ICLR 2020
D.2 FOR NON-SC PROBLEMS
We can also use theorem to give the convergence of VR-SExtraGii for solving non-SC problems, as shown below.
Theorem (Non-Strongly Convex). Suppose that Assumptions
and 2 hold, and let I,
aig P(x). In addition, assume mh > 0. 72 0, and
7/2 1 Then, the conver-
gence property of TR-SExtraGD, as outlined in Algorithm is given as follows:
4m +
(P(x)) P(x.)] + La(a - 1)
([P(F) - P(xx)) <
2m( -75 1 - =.11..
(14)
m(a - 7)5
where Tout E0
Proof. Because know F(-) is L-smooth, then have
P(rx-1/22 S M(rk-1/2) F(xx-1) 11) xk-1)
+ 2タ - - 1 | f((x=-1) - -
- (IK- xk21/2 - xk-1)
L
< R(Ex-1/2) + F(
< (Ix-I), 2x - zk-1) +
2 | xk- 112
2L(a-1) [VF( Vh, ( L(a 1)
1|:22- 112 IK 1212
2
The second inequality holds due to Young's inequality with parameter L(a 1), where is small
constant. Then after taking expectation with respect to the sample i and using Lemma
we obtain
E[P(0x-1/2) S R(Fx-1/2) F(Fx-1)
E(V Súg (xt 1), Ik-1/2 xx-1)
La + 2 1k22 - 12 a
2 [((x=1)) - P(x.) + P(š) - P(x+))
Next, we apply Lemma
T with 1 Fx = 1/21/22
Ta. and have
B[P(ox-1/2) R(x.) + F(Ix-1) E fr, (Ix-1), xx-1)
La (||x, - Blax, Iz 1121/2
2
(P(#x-1) P(I..) + P(t) P(x.))
a --
< R(x.)) + F(x..) + La
2 (1123 8k- 1|2 Ellir. xx-1/2113)
2
[P(# P(x.) + P(ū) P(x.))
a
23

---

Under review as a conference paper at ICLR 2020
The second inequality holds because (Tx-1) = (F(xx=1)
and F()) is convex. Then
know
2
B[P(#x-1/2) P(x+)]
a ((( P(x.) P((x)) P(š) P(xx)]
(15)
La
+
(1
Ik-
E El -サー 1/211/
And for P(æx), can deduce by the same way, and obtain the similar result:
2
E[P(xx)
a P((x-11/2) P(x.)) + P(x) P(x.)]
(16)
La
+
(1 - I2 1/21/211 B1| - - xx.l²).
2
We assume that a is sufficiently large to make
2 a-l S 1, and
sum 15 and 16 together, then we
obtain
[[P())) - P(x.)l 2
[P(xz-1) P(x.)] +
[P( P(x.)
La
+ (115. -12-112 111--BlBarr Bl|.r. 1xxxxx11)) 12))
which is equivalent to
(1 2 B[((((t))) - P(x.)] <
2
{[P(Ix-1) P(r.) - - P(x.)]}
4 [(()) P(x.)] )] + La (1|x, Ik 12 1E 1x113).
By summing the previous inequality over k = 1...., m. we obtain
2
2
(1
Σ E(P(xk) - P(x,)] a (1P(x0)) P(x.)] - -P(mm)--(xx.) P(xx)])
a - (P( P(x.)) + La
4m
2 (1|x, - rall2 || - Jmm 1mml13)
Since we set J 1 Ex Ik and xg s+1
Em, and we know F(-) is convex function. Thus, we
have
(1 a [[[((T - P(x,)] < m(a - 1) ([((2)) - P(xx)] - (P(x)11) P(x.)]}
La (1| xzl12 - ||,, - 21+1 122).
[P( - P(x-)] +
2m
By summing the previous inequality over 1,...g S, we obtain
s
S-1
La (||x, - xxol22 - ||,r, - 51.222)
(1 E[P(T*) - P(x.))
Σ P((*)) -P(Z*)-(((m)) P(xx]]
a
2m
==0
2
+ mla 1) ([P(xb)) - (P(x - P(xx)]}
24

---

Under review as a conference paper at ICLR 2020
That is,
2
4
a 1 a E[P( P(x+)]
2
[P(x)) - P(x.)] + m(a 1) (1P(zt) - P(x.)1- - -PP(s P(x.)))
La
+
(1|t, =/l1? - -1 2 )
2m
2
4
La
(P(xt) - P(x+) +
[P(59) P(x.)]
2+ 2//12
m(a - 1)
2m
The first inequality holds due to 1 2
a and the second inequality holds because
4
p(r)) P(x.) 2 0 and ||=,- - 1 0. Because zy = 0 we have
6
2
4
La
(1
Σ
E P(x.)l S
+
[P(E9) - P(x.)] )1 +
1
x2.11
m(a - 1)
2m
Due to the convexity of F(.), we have
S
8 Σ -iP(i))P((x) -
EP xd) P(xx))
4m + 2
La(a 1)
m(a 7). (P(8)) - P(x.)]+
2m(a 7). 11 -x==1
We note that n = In. 80 we have
S
4m + 2 m(a 7)5
(P(r0) - P(x+)) + La(a - 1)
EPO
3*)) - P(x.)
100 x 112
2m(o 7)5
8=1
E MORE EXPERIMENTAL RESULTS
E.
THE INFORMATION OF DATA SETS
Table 2: Summary of Data Sets and Regularization Coefficient
Data sets
Sizes n
Dimensions d
Sparsity
A
A2
a9a 32,562
123
Sparse
10-6
10-4
Covtype 581,012
54
Dense
10-5
10-8
revl
20,242
47,236
Sparse
10
10-10
real-sim 72,309
20,598
Sparse
10-6
10-8
E.2 THE PROBLEM MODELS
In this part, we introduce two common problem models. The first one is
min ReR 2n
Σ cff b,)²
+
X2 lat 2
25

---

Under review as a conference paper at ICLR 2020
When A1 0, A2 =0, 0, obtain the Lasso problem, and when A1, X2 2 0, obtain the Elastic-Net problem, which are all non-smooth optimization problems. The second problem model
min EER
log(1 +
1=1
which is called the & 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.
PrCKSVRG
SVEG++
Kalyusha
D0 J- (x))
10
Fx (X
10.2
- -Po-5VRG
SVRG+*
VR-SFa
AVR SEttoGD
100
200
300
200
Gradient evadientevalluatoon
Gradient evaluations
PressSVRG
Katyusta
10
KiG
Fix" bx"
SExtaGD AVR-SExtaGO
10"7
SVR
10.10
SVRG++
AVR-SEatriG
10:45
10
2
10
12
20
40
60
80
100
Running (sec)
Running (sec)
(a)
(b) Coviype
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 r-axis corresponds to the number of effective passes (top) or running time (bottom).
shows 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 terms of the number of effective passes and running time. Besides, we note that VR-SExtraGD achieves almost the same result as AVR-SExtraGD 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)
Figure
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 4 norm regularized logistic regression problem, as shown in Figure
From Figure 5 we know that our AVR-SExD 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 not as good as ours because of the complicated structure of the algorithm.
26

---

Under review as a conference paper at ICLR 2020
PrexSVRG Kalyusha
1-1-F (x)
5
VIL-S staGD AVR SEXtrGD
NIG
F- FIX)
SVRG+
10
Catyusho
Vi-SFatruG
10a3
500
1000
1500
2000
500
1000
1500
Gradient
Gradient evallation
SVRG++
Katyusha
F (X
50
FIX" 3
AVR-SE
20
SVRS
10:30
Calytiha
VR-SEataGD AVR-SEatriD
Running time (sec)
Running time (sec)
(a) ala Figure 5: Comparison of experimental results of different algorithms for the é -nom regularized logistic regression problem. on different data sets. The y-axis represents the gap between the objec- tive value and the minimum, and the z-axis corresponds to the number of effective passes (top) or running time (bottom).
(b) Covtype
27


Reviews:
[{"review_id": "S1l6oaWstr", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nI am not working in the field of optimization, therefore, unfortunately I am not in a position to give detailed technical comments for the authors. However, as far as I could follow the paper, it seemed sound and well-written to me in general. I hope the following minor comments may be useful for improving the paper:\n\n- The paper gives detailed explanations about previous work. However, the proposed AVR-SExtraGD algorithm is only presented in the form of a pseudocode in Algorithm 1 and it is not explained in much detail. It would be good to explain and discuss intuitively the steps of the proposed algorithm in the main body of the paper as well, so that it is well understood.\n\n- Algorithm 1 has a set K as input, according to which the solution is updated. How should this set be chosen in practice?", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper."}, "extra_text": {}}, {"review_id": "B1x_ANL1cS", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nThis 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.\n\nThe 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.\n\nEach 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.\n\nTo 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.\n\nThe 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:\n1.\tFor 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.\n2.\tThis 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.\n3.\tIt is also preferable that the author compare with MiG [1], since the proposed algorithm is an extragradient version of [1].\n4.\tPlease 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.\n\nThe presentation and structure of this paper need to be improved. Here are some suggestions:\n1.\t In Section 1, only provide a high-level literature review and then motivate the work. A comprehensive review can come after the introduction.\n2.\tIn Section 4, put all the lemmas into the appendix while giving more intuitions and remarks. \n3.\tIssues including notions without pre-definition or reference, typos, and incorrect gramma need to be fixed.\n\n\nDetailed comments:\n1.\tFrom 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.\n2.\tThe paragraph before section 1.1: lasso and elastic-net are used without citation.\n3.\tSection 1.1: PGD and SGD are used without citation.\n4.\tBeginning of page 2: “And” should be “Besides”\n5.\t“Besides, for accelerating the algorithm and …”: “for accelerating” should be “to accelerate”\n6.\tSection 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.\n7.\tSection 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.\n8.\tSection 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.\n9.\tIn Assumption 2, you can refer to Part 2, Section 7 of [5] for the definition of semi-continuity.\n10.\t“dw is the gradient of the function at w”, what does “the function” refers to?\n11.\t“APG and Acc-Prox-SVRG” needs citation.\n12.\t“was proposed to simply the structure of Katyusha”, “simply” should be “simplify”\n13.\tSection 3.1: “updated with the update rules of MiG”: “with” should be “by”\n14.\tIn 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.\n15.\tSection 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]).\n16.\tThe references are not in a uniform format. Conference/Journal names are missing for some references.\n17.\tOne useful reference for this paper is [4], it discussed extragradient for online convex learning.\n\nAdditional question:\n[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?\n\n[1] A simple stochastic variance reduced algorithm with fast convergence rates, Zhou et al., 2018.\n[2] Katyusha: the first direct acceleration of stochastic gradient methods, Z. Allen-Zhu, 2017\n[3] Extragradient method in optimization: Convergence and complexity, T. Nguyen et al., 2017\n[4] Online Optimization with Gradual Variations, Chiang et al., 2012\n[5] Convex Analysis, R. Rockafella, 1970\n[6] Reducing Noise in GAN Training with Variance Reduced Extragradient, Chavdarova et al.  2019\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "B1eqF1Ykqr", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\n- technically sound, seems like a nice addition to the variance reduced gradient-type methods. Combines the nice properties of proximal methods with variance reduced gradient-descent.\n- Nice summary of recent progress in this research area. \n- How does it compare to SVRG++? How about the Proximal Proximal Gradient? \n- algorithm suitable for non-smooth optimization problems\n- their experimental results look convincing.\n\nHaving said that, it seems to me that combining momentum with an existing algorithm is not extremely novel -- I would defer to reviewers who are experts in the optimization area to fully assess the novelty and technical difficulty of the proposed solution.\n\n ", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a stochastic variance reduced extragradient algorithm. The reviewers had a number of concerns which I feel have been adequately addressed by the authors.

That being said, the field of optimizers is crowded and I could not be convinced that the proposed method would be used. In particular, (almost) hyperparameter-free methods are usually preferred (see Adam), which is not the case here.

To be honest, this work is borderline and could have gone either way but was rated lower than other borderline submissions.
Decision: Reject