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

arXiv: https://arxiv.org/abs/2210.16997 · HTML: https://mlsanity.com/paper/2210.16997/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 38 references that are in the map.
- First posted on arXiv 31 Oct 2022.

## Builds on (most cited first, 10 of 10)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Condition](https://mlsanity.com/paper/1608.04636/) (2016)
- [Optimal rates for zero-order convex optimization: the power of two function evaluations](https://mlsanity.com/paper/1312.2139/) (2013)
- [Stochastic Quasi-Newton Methods for Nonconvex Stochastic Optimization](https://mlsanity.com/paper/1607.01231/) (2016)
- [Calculus of the exponent of Kurdyka-Lojasiewicz inequality and its applications to linear convergence of first-order methods](https://mlsanity.com/paper/1602.02915/) (2016)
- [Zeroth order optimization with orthogonal random directions](https://mlsanity.com/paper/2107.03941/) (2021)
- [Stochastic Zeroth Order Gradient and Hessian Estimators: Variance Reduction and Refined Bias Bounds](https://mlsanity.com/paper/2205.14737/) (2022)
- [From the Greene--Wu Convolution to Gradient Estimation over Riemannian Manifolds](https://mlsanity.com/paper/2108.07406/) (2021)
- [On Sharp Stochastic Zeroth Order Hessian Estimators over Riemannian Manifolds](https://mlsanity.com/paper/2201.10780/) (2022)
- [A convex function satisfying the Lojasiewicz inequality but failing the gradient conjecture both at zero and infinity](https://mlsanity.com/paper/2102.05342/) (2021)

## Built on by (most cited first, 1 of 1)

- [Riemannian Zeroth-Order Gradient Estimation with Structure-Preserving Metrics for Geodesically Incomplete Manifolds](https://mlsanity.com/paper/2601.08039/) (2026)

## Abstract (arXiv)

We prove convergence rates of Stochastic Zeroth-order Gradient Descent (SZGD) algorithms for Lojasiewicz functions. The SZGD algorithm iterates as beginalign* xt+1 = xt - ηt widehatnabla f (xt), qquad t = 0,1,2,3,cdots , endalign* where f is the objective function that satisfies the L ojasiewicz inequality with L ojasiewicz exponent θ, ηt is the step size (learning rate), and  widehatnabla f (xt)  is the approximate gradient estimated using zeroth-order information only. Our results show that   f (xt) - f (x_∞) _t ∈ mathbbN   can converge faster than   | xt - x_∞ | _t ∈ mathbbN , regardless of whether the objective f is smooth or nonsmooth.