Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The authors observe that Adam has too much freedom in optimization, while SGD has one direction (too little freedom), hence the authors propose to propose an algorithm that has flexibility between SGD and Adam to achieve the benefits of both. Specifically, the authors proposed DRAG, which combines Adam with a trust-region like framework, and optimize the loss along $k$ descent directions, where $k$ is a pre-defined hyper-parameter ranging between 1 and $n$ ($n$ is the number of parameters).

The authors also proved the convergence of DRAG in the stochastic non-convex optimization setting, and validated DRAG with experiments for CNN and LSTM.
strength_and_weaknesses: Strength:
1) The perspective of update freedom for comparing Adam vs SGD is novel to me. Furthermore, the authors formalize the trust-region idea, and limits the update direction to be a linear combination of first-order momentum and Nesterov-update, this limits the update at each step to be in the convex hull of all past gradients, which was shown to not hurt generalization performance as Adam.
2) The authors conducted experiments on various architectures (CNN and LSTM) and compare with most of recently proposed optimizers, which is a more thorough comparison.

Weakness:
1) I'm not fully convinced by Thm1. Specifically, I checked the proof which should be correct up to Lemma 4. When deriving Thm1 from Lemma4, it does not look fully correct to me, because in Lemma4 RHS there's a term $C_2 (1-\beta) \sigma^2$, which does not goes to 0 as $T \to \infty$. This conclusion does not show that the risk $\frac{1}{T} \sum \mathbb{E} ||\nabla f(x_t)||^2 \to 0 as T \to \infty$, which means Lemma4 does not fully prove the convergence of the algorithm. 

For proof of Thm1, the condition that $C_2 (1-\beta) \sigma^2 \leq \epsilon^2 / 3$ is again pretty tricky, because $\sigma^2$ is the noise of gradient which you can not control, $C_2$ is another constant that depends on $\eta$, $C_2 = \frac{4G}{\delta} \geq \frac{\eta}{\alpha}$ without an upper bound, (I derive this based on Lemma4's assumption $0<\delta<\frac{\alpha}{\eta}$, which means this term in quite hard to bound unless you make an extra assumption on the lower-bound of $\eta$.

(I might be missing some point here, if the authors could correct me I would be happy to increase rating)

2) The experiments are OK but not very complete. I would suggest the authors to test the proposed method on tasks where Adam typically outperforms SGD, for example transformers and reinforcement learning. For current experiments SGD almost always outperforms Adam.
clarity,_quality,_novelty_and_reproducibility: Quality:
Current quality is fine but not extremely good. (Maybe I misunderstood Thm1 and Lemma4, wait for the authors' response).

Clarity:
good

Originality:
good
summary_of_the_review: The authors propose an interesting and novel idea, which controls the freedom of update to be between Adam and SGD. The analysis is in general complete and experiments are satisfactory. I'm concerned that Thm1 might be wrong, but honestly I think Thm1 is unnecessary and just Thm2 is sufficient. I'll adjust my rating according to the authors' response.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: In this paper, the authors proposed a Dimension-Reduced Adaptive Gradient Method (DRAG) to eliminate the generalization gap of adaptive gradient method. DRAG makes a combination of SGD and Adam by adopting a trust-region like framework. DRAG is compatible with the common deep learning training pipeline without introducing extra hyper-parameters and with negligible extra computation.  
strength_and_weaknesses: 
Strength: 
1. a new adaptive gradient method for better generalization performances
2. no extra hyper-parameters

Weakness
1. improvement is not significant at all
2. does not have very clear intuitions on why the strategy would help
3. theoretical result does not reflect the improvement

clarity,_quality,_novelty_and_reproducibility: see main comments
summary_of_the_review: 1. The intuition for the proposed methods is not quite convincing. Why the two-dimensional search is better than a one-dimension or d-dimensional case? Seems a bit unnatural

2. There are many approximations/vague parts in the process, e.g., the Hessian is approximated, and the trust-region is set without many justifications, why would such a trust-region solution give better estimates on the learning rate? 

3. Continue with point 2, I am concerned that the optimal lr may only give you better convergence rather than generalization. For example, running vanilla SGD/Adam with line searched lr may not give you better results. I would suggest the authors to compare the derived best lr at the beginning of Page 5 vs the vanilla SGD and the line searched SGD, as well as the Adam version.

4. There are no major improvements shown in experiments. Currently the advantage of DRAG is quite marginal. Also the theoretical result only gives a convergence rate matching existing solutions, which does not give any new information on the generalization.

5. The following method also attempts to combine SGD with Adam for better generalization. The authors may want to comment on/compare with it since the goal is the same.

[1] "Closing the generalization gap of adaptive gradient methods in training deep neural networks." IJCAI2020
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper proposes yet another variant of the Adam optimizer, by combining the idea of trust-region problem with adaptive optimization method. The authors provide some heuristics of creating this method and some theoretical analysis of the algorithm. Experimental results validate their claim that DRAG performs better than the other adaptive algorithms. 
strength_and_weaknesses: Strength:
  1. The proposed algorithm is easy to implement and understand.
  2. The paper is well-written and easy-to-follow.
  3. The experimental results show advantages over traditional methods.

Weakness:
  1. This algorithm seems to be just another variant of Adam in the vast number of similar works, where too many algorithms have been proposed and all claim to be better than Adam, with no theoretical gain and only experimental better performance on some datasets. The contribution of this paper seems insufficient to me.

  2. My first question is, why is the algorithm designed in this particular way? I can kind of understand why and how the trust-region problem is formulated, but why is $H_t$ in line 7 of Algo 1 chosen to be the denominator of Adam? Is there a particular reason why the authors choose Adam? What if I replace it by the simple average of gradient squares (variant of AdaGrad) instead of the exponential moving average? In line 10 of Algo 1 and Sec 3.2, the update seems to be a linear combination of the past gradients $g_1, g_2, ..., g_t$, and $H_t$ is not involved expect for the computation of $\alpha_1$ and $\alpha_2$. If the authors only use $H_t$ to be an estimate of, say the Hessian matrix, then I think any similar estimate can be such matrix? Please correct me if I am wrong.

  3. The theoretical results (Sec 4) do not show any advantage over SGD or Adam. It only proves that the algorithm converges in the nonconvex setting. Although this is appreciated, it does not show that the proposed algorithm can, at least have similar property as Adam in the convex case, i.e., in the convex problem, when the gradients are small or sparse, adaptive algorithms such as AdaGrad and Adam can converge faster than SGD, which is a major reason why people like John Duchi have proposed adaptive algorithms in the first place [1].

  4. The experimental results look quite promising. However, they are all on small datasets with small neural networks. I would be much more convinced if the authors can provide results such as, on ImageNet with ResNet50, on One Billion Word with LSTMs, or similar large-scale experiments. Other kinds of experiments such as Image Generation (GAN), Image Segmentation would also be helpful.


[1]. John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 12(7), 2011.
clarity,_quality,_novelty_and_reproducibility: The work is mostly clear.
summary_of_the_review: In summary, the paper is well-written and easy-to-understand. However, I don't think the contributions are enough to make the paper accepted. I would increase my score if the authors can

1. Provide theoretical results showing that DRAG can converge faster than SGD/Adam in convex/nonconvex problems.

2. Provide experimental results on large datasets/other datasets.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper proposes Dimension-Reduced Adaptive Gradient Method (DRAG), a combination of SGD and Adam by solving a trust-region sub problem. The method is inspired by DRSOM (Zhang et al., 2022) which uses Hessian-vector products in two directions. The authors show convergence theory and experiment results for DRAG. 
strength_and_weaknesses: The strengths are: 
- The proposed method has a nice connection with Adam and SGD, which helps further understanding of optimizations algorithms. This paper provided discussions on various approaches for search directions (one-dimension or full-dimension) and convergence theory for DRAG using standard assumptions. 
- Experiment results show encouraging performance compared to prior methods. 


The weaknesses are 
- The subproblem is not motivated well enough. It is hard to find an explanation why the exact objective function of the subproblem should be minimized. Other details may explain that the algorithm are searching for the direction in a subspace of 2-dimension, but it does not explain their choice of objective function. The authors says "update is optimal with respect to the quadratic approximation of the loss function", however solving for that subproblem does not necessary guarantee a good descent direction. 
- Some details related to the algorithm and convergence theory is unclear, thus it is hard for the readers to fully understand this method. (Please see the comment below.)

Comments: 
- It is unclear when the authors state "We omit $\epsilon$ here and below for discussion simplicity.", but mentioning $\epsilon$ in the complexity later in the paragraph (Page 4). In my understanding, this epsilon maybe the accuracy in approximating the subproblem. If that is true, this complexity should be included in the consideration of total algorithm complexity. In addition, it is not clear if the algorithm use an exact solution of the subproblem or an approximation. Please consider this in the convergence results as well. 
- From the context of theorems I assume $\alpha_{1t}$ and $\alpha_{2t}$ should be non-negative. However, I cannot find any justification/explanation on this. Hence the questions: 
1. If true, can you provide a theoretical reason why $\alpha_{1t}$ and $\alpha_{2t}$ should be non-negative? 
2. The theorems assume that those solutions are lower bounded. Why this may hold true in practice? (if the assumption does not hold, there is no theoretical guarantee for this method.)

- It is not really fair to say that the theory has the "same assumptions" as other methods because the assumptions on $\alpha_{1t}$ and $\alpha_{2t}$, $c\eta$ and $C$ depends on the particular algorithm. 
- The abstract is too long. Please shorten it and put the motivation/explanation to the introduction. 
clarity,_quality,_novelty_and_reproducibility: Though this paper needs clarifications, the overall clarity is good. Since it is inspired by the prior method DRSOM (Zhang et al., 2022), the novelty is not really impressive. 
summary_of_the_review: This paper has some unclear points regarding the subproblem in the algorithm and the convergence analysis. I will be more open to accept this paper if the authors clarify these points.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: None of the reviewers judged this paper to be above the acceptance bar. In particular, as one reviewer writes, this paper seems "just another variant of Adam in the vast number of similar works, where too many algorithms have been proposed and all claim to be better than Adam, with no theoretical gain and only experimental better performance on some datasets." Indeed, the theory does not show any advantage over SGD. Note that while the SGD rate is optimal, one could still try to argue for specific cases where this algorithm has advantage or that in practice some terms might have a smaller value than the worst-case ones. Moreover, the experiments are also unconvincing. Overall, the paper is not ready to be published at ICLR.
justification_for_why_not_higher_score: Clearly a weak optimization paper.
Decision: Reject