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

Chuan He · 2024

Read A stochastic first-order method with multi-extrapolated momentum for highly smooth unconstrained optimization by Chuan He (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-14488.txt.

Introduction

Chuan He proposes a stochastic first order method with multi-extrapolated momentum in two thousand twenty-four. The target is unconstrained optimization with a very smooth objective. Each step runs several extrapolations before a momentum update. Smoothness of high order is the fuel for speed.

He assumes a Lipschitz bound on a high derivative of the objective. Under mild extra terms, a sample complexity bound follows. It beats the best known rates for this class of methods. No mean squared smoothness is assumed, a first for such gains. Early numeric tests back both speed and theory.

Catalog record

CREATORChuan He
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE81 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-14488

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A stochastic first-order method with multi-extrapolated momentum for highly smooth unconstrained optimization Chuan He Abstract In this paper, we consider unconstrained stochastic optimization problems in which the objective function exhibits higher-order smoothness. In particular, we propose a stochastic first-order method (SFOM) with multi-extrapolated momentum, where multiple extrapolations are performed in each iteration, followed by a momentum update based on these extrapolations. We show that the proposed SFOM can accelerate optimization by exploiting the higher-order smoothness of the objective function f f . Assuming that the p p th-order derivative of f f is Lipschitz continuous for some p ≥ 2 p\geq 2 , and under additional mild assumptions, we establish that our method achieves a sample and first-order operation complexity of 𝒪 ~ ( ϵ − ( 3 p + 1 ) / p ) \widetilde{{\mathcal{O}}}(\epsilon^{-(3p+1)/p}) for finding an ϵ \epsilon -stochastic stationary point x x that satisfies 𝔼 ​ [ ‖ ∇ f ​ ( x ) ‖ ] ≤ ϵ \mathbb{E}[\|\nabla f(x)\|]\leq\epsilon . To the best of our knowledge, this is the first SFOM to leverage the Lipschitz continuity of arbitrarily higher-order derivatives of the objective function for acceleration. Preliminary numerical experiments validate the practical performance of our method and support our theoretical results. Keywords: Unconstrained optimization, higher-order smoothness, stochastic first-order method, extrapolation, momentum, sample complexity, first-order operation complexity Mathematics Subject Classification 49M05, 49M37, 90C25, 90C30 1 Introduction In this paper, we consider the smooth unconstrained optimization problem: \displaystyle\min_{x\in\mathbb{R}^{n}}f(x), (1) where f:\mathbb{R}^{n}\to\mathbb{R} is continuously differentiable and has a Lipschitz continuous p th-order derivative for some p\geq 2 (see Assumption 2 for details). We assume that problem Eq. 1 has at least one optimal solution. Our goal is to develop a first-order method for solving Eq. 1 in the stochastic regime, where the derivatives of f are not directly accessible. Instead, the algorithm relies solely on the stochastic estimator G(\cdot;\xi) for \nabla f(\cdot) , which is unbiased and has bounded variance (see Assumption 1 (c) for details). Here, \xi is a random variable with a sample space \Xi . In recent years, there have been significant developments in stochastic first-order methods (SFOMs) with complexity guarantees for solving problem Eq. 1 . Notably, when assuming \nabla f is Lipschitz continuous (see Assumption 1 (b)), SFOMs [ 6 , 11 , 12 ] have been proposed with a sample and first-order operation complexity 1 1 1 Sample complexity and first-order operation complexity refer to the total number of samples of \xi and the evaluations of G(\cdot,\cdot) throughout the algorithm, respectively. of \mathcal{O}(\epsilon^{-4}) for finding an \epsilon -stochastic stationary point x of problem Eq. 1 such that \displaystyle\mathbb{E}[\|\nabla f(x)\|]\leq\epsilon, (2) where \epsilon\in(0,1) is a given tolerance parameter, and the expectation is taken over the randomness in the algorithm. This complexity bound has been proven to be optimal in [ 2 ] without any additional smoothness assumptions beyond the Lipschitz continuity of the gradient. Among these works, [ 6 ] proposed a normalized SFOM that incorporates Polyak momentum updates: \displaystyle m^{k}=(1-\gamma_{k-1})m^{k-1}+\gamma_{k-1}G(x^{k};\xi^{k})\qquad\forall k\geq 0, (3) where \{x^{k}\} denotes the algorithm iterates, \{\gamma_{k}\} denotes the momentum parameters, and \{m^{k}\} denotes the estimators of \{\nabla f(x^{k})\} . Recently, [ 10 ] proposed an SFOM with Polyak momentum for stochastic composite optimization. As shown in [ 6 , 10 ] , Polyak momentum induces a variance reduction effect in gradient estimation for SFOMs. Several other attempts have been made to improve the sample complexity of SFOMs by leveraging the second-order smoothness of f . Assuming that \nabla^{2}f is Lipschitz continuous, i.e., Assumption 2 with p=2 , an SFOM [ 6 ] has been proposed with sample and first-order operation complexity of \mathcal{O}(\epsilon^{-7/2}) for finding x satisfying Eq. 2 . This method incorporates implicit gradient transport that combines extrapolations with Polyak momentum updates: \displaystyle z^{k}=x^{k}+\frac{1-\gamma}{\gamma}(x^{k}-x^{k-1}),\quad m^{k}=(1-\gamma)m^{k-1}+\gamma G(z^{k};\xi^{k})\qquad\forall k\geq 0 (4) with some fixed parameter \gamma\in(0,1) . It has been shown in [ 6 ] that constructing \{z^{k}\} through extrapolations and combining them with Polyak momentum achieves faster variance reduction for gradient estimators \{m^{k}\} , leading to an improved overall complexity bound. In addition, a restarted stochastic gradient method has been proposed in [ 9 ] to escape saddle points for problem Eq. 1 assuming a Lipschitz continuous Hessian, which achieves a sample and first-order operation complexity of \mathcal{O}(\epsilon^{-7/2}) for finding an (\epsilon,\mathcal{O}(\sqrt{\epsilon})) -second-order stationary point of problem Eq. 1 with high probability. However, the algorithm input parameters in [ 6 , 9 ] (e.g., step sizes and momentum parameters) require explicit access to the problem-specific parameters (e.g., Lipschitz constants and bounds for noise), and is therefore generally hard to implement in practice. Furthermore, there appear to be no SFOMs that leverage higher-order smoothness of f beyond the Hessian Lipschitz condition for acceleration. Aside from leveraging the smoothness of f for acceleration, recent work [ 7 , 8 , 19 ] has shown that SFOMs can be accelerated by leveraging the mean-squared smoothness of the stochastic gradient estimator G(\cdot;\xi) , which is expressed as \displaystyle\mathbb{E}_{\xi}[\|G(y;\xi)-G(x;\xi)\|^{2}]\leq L^{2}\|y-x\|^{2}\qquad\forall x,y\in\mathbb{R}^{n} (5) for some L>0 . These methods achieve a sample and first-order operation complexity of \mathcal{O}(\epsilon^{-3}) for finding an \epsilon -stochastic stationary point of Eq. 1 , which has been proven to be optimal in [ 2 ] under the assumption of Eq. 5 . In addition, SFOMs [ 22 , 24 , 25 , 26 ] have been proposed for stochastic composite optimization problems, achieving a sample and first-order operation complexity of \mathcal{O}(\epsilon^{-3}) under mean-squared smoothness condition stated in Eq. 5 . Thus far, the mean-squared smoothness in Eq. 5 appears to be crucial for achieving the complexity of \mathcal{O}(\epsilon^{-3}) for finding x that satisfies Eq. 2 . On the other hand, it should be noted that the mean-squared smoothness is an assumption imposed on the stochastic gradient estimator G(\cdot;\xi) rather than the function f itself. To illustrate this, we provide an example in Appendix A that shows an unbiased stochastic gradient estimator G(\cdot;\xi) with bounded variance can violate Eq. 5 when the gradient and arbitrarily higher-order derivatives of f are Lipschitz continuous. Recently, many studies have also extended the aforementioned acceleration methods for unconstrained optimization to develop accelerated SFOMs for constrained optimization with complexity guarantees. For example, [ 1 , 16 , 20 , 21 , 23 ] establish the complexity for equality constrained stochastic optimization problems, while [ 13 ] establishes the complexity for conic constrained stochastic optimization. Since the main focus of this paper is on unconstrained optimization, we omit a detailed discussion of these studies. In this paper, we explore the possibility to accelerate SFOMs for solving problem Eq. 1 by exploiting the higher-order smoothness of the objective function f . In particular, we show that SFOMs can achieve acceleration by exploiting arbitrarily higher-order smoothness of f through the introduction of an SFOM with multi-extrapolated momentum (Algorithm 1 ). We demonstrate that for any p\geq 2 , performing p-1 separate extrapolations in each iteration and combining them with a Polyak momentum update can accelerate variance reduction by exploiting the smoothness of the p th-order derivative of f , thereby leading to a sample and first-order operation complexity of \widetilde{\mathcal{O}}(\epsilon^{-(3p+1)/p}) 2 2 2 \widetilde{\mathcal{O}}(\cdot) represents {\mathcal{O}}(\cdot) with hidden logarithmic factors. . Our complexity result significantly generalizes the complexity

Read the complete text