The Adam algorithm has become extremely popular for large-scale machine learning. Under convexity condition, it has been proved to enjoy a data-dependent O( √ T ) regret bound where T is the time horizon. However, whether strong convexity can be utilized to further improve the performance remains an open problem. In this paper, we give an affirmative answer by developing a variant of Adam (referred to as SAdam) which achieves a data-dependent O(log T ) regret bound for strongly convex functions. The essential idea is to maintain a faster decaying yet under controlled step size for exploiting strong convexity. In addition, under a special configuration of hyperparameters, our SAdam reduces to SC-RMSprop, a recently proposed variant of RMSprop for strongly convex functions, for which we provide the first data-dependent logarithmic regret bound. Empirical results on optimizing strongly convex functions and training deep networks demonstrate the effectiveness of our method.
This paper studies Adam and proves that under strong convexity assumption, it obtains the improved regret bound $O(log(T))$. The regret bound is data-dependent, thus as a side-effect it also improves previous known result for strongly convex RMSProp (SC-RMSProp).
The paper is clear and well-written and I also think that theoretical results are correct and new. However, I have some concerns on the possible impacts of the results especially in the context of ICLR:
- First of all, the assumption to show improved regret is strong convexity of all functions $f_t$. However, this is very restrictive and much stronger than the assumption that the sum of functions is strongly convex. In addition, from what I see, in the proof of Theorem 1, the authors use strong convexity with the $x^\star$, so they can maybe replace global strong convexity to strong convexity restricted to the path towards the solution. A reference where these restricted strong convexity type assumptions are studied:
Necoara, Nesterov, Glineur, “Linear convergence of first order methods for non-strongly convex optimization”, Math. Prog. 2019.
- To show improved regret, consistent with previous work SC-Adagrad and SC-RMSProp, the authors modify the algorithm to use $V_t^{-1}$ in page 3 in the step size, instead of $V_t^{-1/2}$ of regular Adam. It is easy to see that this is to make sure step size has a faster decrease, which is needed also to show standard SGD gets $1/k$ rate for strongly convex problems. However, given that one might not now if the problem has strong convexity (there might exist cases where this property only exists locally), it is not clear if one should apply Adam or SAdam. 
- Another remark related to the previous one is the following. Standard SGD uses step size $\alpha_0/\sqrt{k}$ for convex optimization without strong convexity and $\alpha_0/k$ for strongly convex optimization. If one uses $alpha_0/k $for convex optimization without strong convexity, one gets a very bad rate $1/log(k)$ and very bad practical performance. So, given SAdam gives step sizes suited for strongly convex optimization (similar to SGD for strongly convex optimization), I would expect SAdam's step sizes to be not very suitable when there is no strong convexity.
- An additional point is that the step size of SAdam depends on the global strong convexity parameter $\lambda$ which further restricts the applicability of the method. For the theoretical results to hold, the step size should be set according to $\lambda$, and when the step size is not selected that way, one loses the fast convergence rate.
- In the experiments, the authors show the performance of SAdam for neural network training and related to my previous remarks, I have the following concerns. First of all, how do the authors pick step sizes now since it depends on strong convexity constant as in eq. (7). In addition, given that neural networks are certainly non-strongly convex, I would expect that the fast decreasing step size caused by using $V_t^{-1}$ might also hurt the performance considerably, which happens as I discussed above even for convex but non-strongly convex losses. I would suspect that much worse effects can be seen for non-convex optimization. Of course, the authors can argue that if the loss landscape of neural network has some local strong convexity parameters, SAdam would adapt and get faster convergence. But unfortunately, I would not agree with such a statement, because the analysis is not made to adapt to local strong convexity and a dependence to strong convexity constant is present due to eq. (7), so if one does not know the constant, the theoretical guarantees would not apply. In addition, the provided experiments for neural network training is not extensive enough to convince practitioners to use SAdam instead of Adam which has been used for years.
Overall, I think that it is interesting to see that a variant of Adam can be shown to obtain improved regret under strong convexity, I find the assumptions strong and the impact for neural network training, therefore for ICLR, quite questionable.