Summary
The paper proposes a new proof strategy for the convergence of Adam in the
non-convex setting. The new analysis relaxes the typical assumptions
in the following ways: 1) it assumes relaxed smoothness, where the norm of the Hessian
grows sub-quadratically with the gradient norm; 2) it does not require
bounded gradients. With a deterministic gradient oracle, the obtained rate is $O(1/\epsilon^2)$.
For the stochastic setting, the author shows a convergence rate of $O(1/\epsilon^4)$
with high probability.
Furthermore, the author proposes a variance-reduced version of Adam and proves
a rate of $O(1/\epsilon^3)$. The above rates in stochastic setting is dimension-dependent
and can be dimension-free if the Hessian norm is sub-affine on the gradient norm.
The main limitation is that although the bounded gradient assumption is removed,
the bounded noise is still needed.
Strengths
1. The paper is well-written and easy to follow. Specifically, the technical
challenges and the intuition behind the new analysis are discussed comprehensively.
2. Removing the bounded gradient assumption is generally challenging. Although
there are a few works for AdaGrad that address this, existing work targeting
the removal of this assumption for Adam only converges to a neighborhood of
stationary points.
3. The paper considers the smoothness condition where the norm of the
Hessian is bounded by a sub-quadratic function of the gradient norm, which
is more general than $(L_0, L_1)$-smoothness.
Weaknesses
1. Although the work relaxes the bounded stochastic gradient assumption
commonly required in the analysis of Adam, assuming almost surely bounded
noise is still somewhat strong and impractical. Since the proof technique,
the contradiction argument, heavily relies on this assumption, it is
unclear whether it can be used in more realistic settings.
2. It is difficult to assess the usefulness of the proposed variance reduction method
since the convergence result does not improve upon previous methods and there
is no experimental evidence.
Minor:
The result presented for the deterministic setting is not formal. It would be
better to have a formal theorem, at least in the appendix.
Questions
1. In Theorem 4.1, the same value of $\beta_{sp}$ and $\beta$ are selected,
which differ from conventional choice of $(1 - \beta)^2 < 1 - \beta_{sp}$.
Could the author please explain the reason behind this?
2. Why do we have a dependence on $d$ in the convergence result when $\rho \geq 1$
and suddenly become dimension-free when $\rho < 1$? Also, some results for Adam
assume the infinity norm of the gradient is upper bounded by a constant [1], which
natural leads to dimension dependence. It seems that by assuming bounded 2-norm, the
results become dimension-free [2, 3]. Could the author provide further elaborate on this matter?
3. It seems that if we have access to problem-dependent parameters and the initial conditions (e.g., the gradient norm at the first iteration), SGD can also converge with the optimal rate [4]. What is the benefit of adaptive methods (if they also require tuning) compared to SGD in the more generalized smoothness setting?
References:
1. Défossez, A., Bottou, L., Bach, F., & Usunier, N. (2020). A simple convergence proof of adam and adagrad. arXiv preprint arXiv:2003.02395.
2. Chen, X., Liu, S., Sun, R., & Hong, M. (2018). On the convergence of a class of adam-type algorithms for non-convex optimization. arXiv preprint arXiv:1808.02941.
3. Guo, Z., Xu, Y., Yin, W., Jin, R., & Yang, T. (2021). A novel convergence analysis for algorithms of the adam family and beyond. arXiv preprint arXiv:2104.14840.
4. Li, H., Qian, J., Tian, Y., Rakhlin, A., & Jadbabaie, A. (2023). Convex and Non-Convex Optimization under Generalized Smoothness. arXiv preprint arXiv:2306.01264.
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.