Convergence Rates of Stochastic Zeroth-order Gradient Descent for Łojasiewicz Functions

Abstract

We prove convergence rates of Stochastic Zeroth-order Gradient Descent (SZGD) algorithms for Lojasiewicz functions. The SZGD algorithm iterates as \begin{align*} \mathbf{x}_{t+1} = \mathbf{x}_t - η_t \widehat{\nabla} f (\mathbf{x}_t), \qquad t = 0,1,2,3,\cdots , \end{align*} where $f$ is the objective function that satisfies the Łojasiewicz inequality with Łojasiewicz exponent $\theta$, ${\eta }_t$ is the step size (learning rate), and $\hat{\nabla }f({\mathbf{x}}_t)$ is the approximate gradient estimated using zeroth-order information only. Our results show that $\{f({\mathbf{x}}_t)-f({\mathbf{x}}_{\infty }){\}}_{t\in \mathbb{N}}$ can converge faster than $\{\Vert {\mathbf{x}}_t-{\mathbf{x}}_{\infty }\Vert {\}}_{t\in \mathbb{N}}$, regardless of whether the objective $f$ is smooth or nonsmooth.