Stochastic first-order methods with multi-extrapolated momentum for highly smooth unconstrained optimization

In this paper we consider an unconstrained stochastic optimization problem where the objective function exhibits a high order of smoothness. In particular, we propose a stochastic first-order method (SFOM) with multi-extrapolated momentum, in which multiple extrapolations are performed in each iteration, followed by a momentum step based on these extrapolations. We show that our proposed SFOM with multi-extrapolated momentum can accelerate optimization by exploiting the high-order smoothness of the objective function \(\)\(f\). Specifically, assuming that the gradient and the \(\)\(p\)th-order derivative of \(\)\(f\) are Lipschitz continuous for some \(\)\(p\ge2\), and under some additional mild assumptions, we establish that our method achieves a sample complexity of \(\)\(\widetilde{\mathcal{O}}(\epsilon^{-(3p+1)/p})\) for finding a point \(\)\(x\) satisfying \(\)\(\mathbb{E}[\|\nabla f(x)\|]\le\epsilon\). To the best of our knowledge, our method is the first SFOM to leverage arbitrary order smoothness of the objective function for acceleration, resulting in a sample complexity that strictly improves upon the best-known results without assuming the average smoothness condition. Finally, preliminary numerical experiments validate the practical performance of our method and corroborate our theoretical findings.

Article

Download

View PDF