Convergence Rates of Stochastic Zeroth-order Gradient Descent for L ojasiewicz Functions
Not on the map. Why?
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.
Key facts. Cited by 1 paper in the map (data through 7 Oct 2026). Builds on 10 of its 38 references that are in the map. First posted on arXiv 31 Oct 2022.
Builds on
10 of 38 references.
References · 10
- 2021Convex optimizationcited by 2,479
- 2016Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Conditioncited by 526
- 2013Optimal rates for zero-order convex optimization: the power of two function evaluationscited by 190
- 2016Stochastic Quasi-Newton Methods for Nonconvex Stochastic Optimizationcited by 37
- 2016Calculus of the exponent of Kurdyka-Lojasiewicz inequality and its applications to linear convergence of first-order methodscited by 35
- 2021Zeroth order optimization with orthogonal random directionscited by 21
- 2022Stochastic Zeroth Order Gradient and Hessian Estimators: Variance Reduction and Refined Bias Boundscited by 7
- 2021From the Greene--Wu Convolution to Gradient Estimation over Riemannian Manifoldscited by 6
- 2022On Sharp Stochastic Zeroth Order Hessian Estimators over Riemannian Manifoldscited by 4
- 2021A convex function satisfying the Lojasiewicz inequality but failing the gradient conjecture both at zero and infinitycited by 3
Built on by
Citing papers per year: 2026: 1.
1 paper.