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 - \eta_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 \L ojasiewicz inequality with \L ojasiewicz exponent $\theta$, $\eta_t$ is the step size (learning rate), and $ \widehat{ \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 $ \{ \| \mathbf{ x}_t - \mathbf{ x}_\infty \| \}_{ t \in \mathbb{ N} }$, regardless of whether the objective $f$ is smooth or nonsmooth.
Categories: math.OC cs.LG