On the global convergence rate of the gradient des

Authors: Maryam Yashtini

Publish Date: 2015/08/26

Volume: 10, Issue: 6, Pages: 1361-1370

PDF Link

Abstract

The gradient descent method minimizes an unconstrained nonlinear optimization problem with mathcal O1/sqrtK where K is the number of iterations performed by the gradient method Traditionally this analysis is obtained for smooth objective functions having Lipschitz continuous gradients This paper aims to consider a more general class of nonlinear programming problems in which functions have Hölder continuous gradients More precisely for any function f in this class denoted by mathcal C1nu L there is a nu in 01 and L0 such that for all mathbfxyin mathbb Rn the relation Vert nabla fmathbfxnabla fmathbfyVert le L Vert mathbfxmathbfyVert nu holds We prove that the gradient descent method converges globally to a stationary point and exhibits a convergence rate of mathcal O1/Kfracnu nu +1 when the stepsize is chosen properly ie less than fracnu +1Lfrac1nu Vert nabla fmathbfx kVert frac1nu 1 Moreover the algorithm employs mathcal O1/epsilon frac1nu +1 number of calls to an oracle to find barmathbfx such that Vert nabla fbarmathbfxVert epsilon

Keywords: