and suggestions for improvement: I have several concerns about the potential impact of both theoretical and practical results. Mainly:
By referring to Wilson et al., 2017, the authors argue that diagonal step sizes in adaptive algorithms hurt generalization. First, I find this claim rather vague, as there has been many followups to Wilson et al., 2017, so I suggest the authors to be more precise and include more recent observations. Moreover, one can use non-diagonal versions of these algorithms. For example, see [2 and Adagrad-norm from Ward et al., 2019], it is easy to consider similar non-diagonal versions of Adam/AMSGrad/Adagrad with first order momentum (a.k.a. AdamNC or AdaFOM), then, are these algorithms also supposed to have good generalization? I think it is important to see how these non-diagonal adaptive methods behave in practice compared to SGD/Adam+ for generalization to support the authors' claim.
I think the algorithm seems more like an extension of momentum SGD, than Adam.
It is nice to improve \eps^{-4} complexity with Lipschitz Hessian assumption, but what happens when this assumption fails? Does Adam+ get standard \epsilon^{-4}?
From what I understand in remark after Lemma 1, the variance reduction is ensured by taking β to 0
. The authors use 1 / T a
for some a ∈ ( 0 , 1 )
. Here, I have several questions. First, how does such a small β
work in practice? If in practice, a larger β
works well and theory requires β → 0
for working, it shows to me that theoretical analysis of the paper does not translate to the practical performance. When one uses β
values that work well in practice, does the theory show convergence?
Related to the previous part, I am also not sure about "adaptivity" of the method. The authors need to use Lipschitz constants L , L H
to set step sizes. Moreover β
is also fixed in advance, depending on horizon T
, which is the main reason to have variance reduction on z t − ∇ f ( w k )
. So, I do not understand what is adaptive in the step size or in the variance reduction mechanism of the method.
For experiments, the authors say that Adam+ is comparable with "tuned" SGD. However, from the explanations in the experimental part, I understand that Adam+ is also tuned similar to SGD. Then, what is the advantage compared to SGD? If one needs the same amount of tuning for Adam+, and the performance is similar, I do not see much advantage compared to SGD. On this front, I suggest the authors to show what happens when the step size parameter is varied, is Adam+ more robust to non-tuned step sizes compared to SGD?
To sum up, I vote for rejection since 1) the analysis and parameters require strict condition, 2) it is not clear if the analysis illustrates the practical performance (very small β
is needed in theory), 3) practical merit is unclear since the algorithm needs to be tunes similar to SGD and the results are also similar to SGD.
[1] Zhang, Lin, Jegelka, Jadbabaie, Sra, Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions, ICML 2020. [2] Levy, Online to Offline Conversions, Universality and Adaptive Minibatch Sizes, NIPS 2017.
======== after discussion phase ==========
I still think that the merit of the method is unclear due to reasons: 1) It is not clear how the method behaves without Lipschitz Hessian assumption. 2) The method only obtains the state-of-the-art complexity of ϵ − 3.5
with large mini-batch sizes and the complexity with small mini-batch sizes (section 2.1) is suboptimal (in fact drawbacks such as this needs to be presented explicitly, right now I do not see enough discussions about this.). 3) Adaptive variance reduction property claimed by the authors boils down to picking "small enough" β
parameter, which in my opinion takes away the adaptivity claim and is for example not the case in adaptive methods such as AdaGrad. 4) The comparison with AdaGrad and Adam with scalar step sizes is not included (the authors promised to include it later, but I cannot make a decision about these without seeing results) and I am not sure if Adam+ will bring benefits over them. 5) Presentation of the paper needs major improvements. I recommend making the remarks after Lemma 1 and theorems clearer, by writing down exact expressions and the implications of these (for example remarks such as "As the algorithm converges with E [ ∇ F ( w ) 2 ] and β
decreases to zero, the variance of z t
will also decrease" can be made more rigorous and clearer, by writing down exactly the bound for the variance of z t
by iterating the recursion written with E δ t + 1
and highlighting what each term does in the bound. This way will be much easier for readers to understand your paper).
Therefore, I am keeping my score.
1) It is not clear how the method behaves without Lipschitz Hessian assumption.