Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 6: Weak Accept
review_content: Balancing the generalization and convergence speed is an important direction in deep learning. This paper propose a new method to balance them. That is very interesting to me. However, I have several concerns as follows.
1. I cannot agree that "fewer hyper-parameters" in Algorithm 1. The authors should provide more materials to support this claim, such as a comparison table of different mathods. 
2. In Theorem 42, how to set the parameter \epsilon to obtain the conclusion.
3. The authors should provide more comparison of the theoretical results of different SGD algorithms (such Adam, RMSProp ...)
Some minor issues:
1. The conditions of formulation of Eq. (6) should be placed together with Eq. (6).
2. What is the definition to c_2,0, c_2,1 .... It is not clear to readers.
3. The presentation and structure of the paper should be improved further, such as adding several subsection in Sec. 3, so that readers could easily follow the main idea of this paper.
review_title: Official Blind Review #3

final_score: rating: 1: Reject
review_content: This paper attempts to remove the use of the second moment in Adam in order to improve the generalization ability of Adam. 
- Apriori, it is not clear why removing the second moment is important. Does it improve the generalization or decrease the runtime substantially?
- Please clarify how our method compares against Yogi (Adaptive Methods for Nonconvex Optimization, Zaheer' 2018) and the more recent RADAM (ON THE VARIANCE OF THE ADAPTIVE LEARNING
RATE AND BEYOND, Liu 2019) , both theoretically and empirically. 
- The paper is meandering and confusing. State your update/algorithm and then explain how it compares against the other methods. Besides, there might be technical problems with it. 

See the detailed review below:
- Section 1: "the generalization results (of adaptive methods) cannot be as good as SGD". Please cite the relevant papers, (for example, Wilson. 2017)  that show this empirically. 
-  Section 1: "the proposed algorithm outperforms Adam in convergence speed" - Please clarify what "convergence speed" refers to. Is it the number of gradient evaluations, the rate of convergence or the wall-clock time. Please state how did you conclude this. 
- Section 2: The update rule of Adagrad is incorrect. The step-size is constant \alpha and it is decreased over time because of the v_t term. 
- Section 3: There is no guarantee on the approximation in Equation 5. Young's inequality and the resulting upper bound can be quite loose. 
- Section 3: In general, it is not possible to have an update that decreases the loss on the current batch, but does not increase the previous batches loss. It is always possible to construct a counter-example to this. 
- "In practice, the computational cost of computing" the gradient for all i is expensive. Indeed, this is batch gradient descent. I am not sure how this is relevant to the discussion in the paper. 
- Cite and compare against the variance reduced methods (Stochastic Average Gradient, Schmidt, 2013; SVRG, Johnson, 2013) as these try to "approximate" the full gradient in order to decrease the variance. 
- The derivation/formulation of Equation 8 is not clear to me. Why is the \hat{m} normalized? 
- In algorithm 1, it seems you need to choose the sequence of step-sizes \alpha_t and \beta_t. How is this an adaptive method then? How are these sequences chosen theoretically and practically? Please clarify this. 
- Section 4: Please compare the resulting regret bound to that of Adam, Adagrad and AMSgrad. Why does \alpha_t = O(1/t)? If we have to decrease the step-size according to a sequence, why should I not use standard SGD?
- Section 5: "we decay the learning rate by 0.1 every 50 epochs" This is not aligned with either the theory or the algorithm you proposed. 
 
review_title: Official Blind Review #1

final_score: rating: 3: Weak Reject
review_content: This paper proposes new stochastic optimization methods to achieve a fast convergence of adaptive SGD and preserve the generalization ability of SGD. The idea is to let the search direction opposite to the gradient at the current batch of examples and a bit orthogonal to previous batch of examples. The algorithm is easy to implement and backed up with regret bounds. Several experimental results are also reported to verify the effectiveness of the algorithm.

The regret bound in Theorem 4.2. is not quite satisfactory. For example, Adagrad in Duchi et al (2011) can achieve the regret bound $O(\sum_{i=1}^{d}\|g_{1:T,i}\|_2)$. However, there is an additional factor of $\sqrt{d}$ in the regret boun in Theorem 4.2, which is not appealing in high dimensional problems. The regret analysis follows largely from standard arguments.

I can not follow the last identity of (10). It should not hold since there is a missing $\epsilon$ there.

In both eq (14) and (15), it is not clear to me why the authors divided the summation into two parts. Also, $\sqrt{\sum_{t=1}^{T}\frac{1}{\sqrt{t}}}$ should be $\sqrt{\sum_{t=1}^{T}\frac{1}{t}}$ there.

----------------------
After rebuttal:

I have read the author response. Unlike AdaGrad, the proposed algorithm does not show an advantage over standard OGD. I would like to keep my original score.
review_title: Official Blind Review #2

Meta-review: The paper addresses an important problem of finding a good trade-off between generalization and convergence speed of stochastic gradient methods for training deep nets. However, there is a consensus among the reviewers, even after rebuttals provided by the authors, that  the contribution is somewhat limited and the paper may require additional work before it is ready to be published.
Decision: Reject