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

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 $\widehat{\mathrm{\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}}_{\mathrm{\infty }}){\}}_{t\in \mathbb{N}}$ can converge faster than $\{\mathrm{\parallel }{\mathbf{x}}_t-{\mathbf{x}}_{\mathrm{\infty }}\mathrm{\parallel }{\}}_{t\in \mathbb{N}}$, regardless of whether the objective $f$ is smooth or nonsmooth.