Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 6: Weak Accept
review_content: 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.

- 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.
- Nice summary of recent progress in this research area. 
- How does it compare to SVRG++? How about the Proximal Proximal Gradient? 
- algorithm suitable for non-smooth optimization problems
- their experimental results look convincing.

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

 
review_title: Official Blind Review #2

final_score: rating: 1: Reject
review_content: 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

review_title: Official Blind Review #3

final_score: rating: 8: Accept
review_content: 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.

I 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:

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

- Algorithm 1 has a set K as input, according to which the solution is updated. How should this set be chosen in practice?
review_title: Official Blind Review #1

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