A stochastic first-order method with multi-extrapolated momentum for highly smooth unconstrained optimization

Abstract

In this paper, we consider an unconstrained stochastic optimization problem where the objective function exhibits high-order smoothness. Specifically, we propose a new stochastic first-order method (SFOM) with multi-extrapolated momentum, in which multiple extrapolations are performed in each iteration, followed by a momentum update based on these extrapolations. We demonstrate that the proposed SFOM can accelerate optimization by exploiting the high-order smoothness of the objective function $f$. Assuming that the $p$th-order derivative of $f$ is Lipschitz continuous for some $p\ge 2$, and under additional mild assumptions, we establish that our method achieves a sample complexity of $\tilde{\mathcal{O}}(\hat{I}{\mu }^{-(3p+1)/p})$ for finding a point $x$ such that $\mathbb{E}[\Vert \nabla f(x)\Vert ]\le \hat{I}\mu$. To the best of our knowledge, this is the first SFOM to leverage arbitrary-order smoothness of the objective function for acceleration, resulting in a sample complexity that improves upon the best-known results without assuming the mean-squared smoothness condition. Preliminary numerical experiments validate the practical performance of our method and support our theoretical findings.

An example is provided to illustrate the gap between the smoothness of the objective function itself and the mean-squared smoothness of the stochastic gradient estimator