# Sharp Analysis of Stochastic Optimization under Global Kurdyka-Lojasiewicz Inequality

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

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Oct 2022.

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

- [Stochastic Policy Gradient Methods: Improved Sample Complexity for Fisher-non-degenerate Policies](https://mlsanity.com/paper/2302.01734/) (2023)
- [On Finding Small Hyper-Gradients in Bilevel Optimization: Hardness Results and Improved Analysis](https://mlsanity.com/paper/2301.00712/) (2023)
- [A Novel Framework for Policy Mirror Descent with General Parameterization and Linear Convergence](https://mlsanity.com/paper/2301.13139/) (2023)
- [Reinforcement Learning with General Utilities: Simpler Variance Reduction and Large State-Action Space](https://mlsanity.com/paper/2306.01854/) (2023)
- [Convergence Rates for Stochastic Approximation: Biased Noise with Unbounded Variance, and Applications](https://mlsanity.com/paper/2312.02828/) (2023)
- [Unified Convergence Theory of Stochastic and Variance-Reduced Cubic Newton Methods](https://mlsanity.com/paper/2302.11962/) (2023)
- [SGD with Adaptive Preconditioning: Unified Analysis and Momentum Acceleration](https://mlsanity.com/paper/2506.23803/) (2025)
- [Taming Nonconvex Stochastic Mirror Descent with General Bregman Divergence](https://mlsanity.com/paper/2402.17722/) (2024)
- [Loss Landscape Characterization of Neural Networks without Over-Parametrization](https://mlsanity.com/paper/2410.12455/) (2024)
- [Non-Euclidean SGD for Structured Optimization: Unified Analysis and Improved Rates](https://mlsanity.com/paper/2511.11466/) (2025)
- [On the Role of Batch Size in Stochastic Conditional Gradient Methods](https://mlsanity.com/paper/2603.21191/) (2026)
- [Almost sure convergence rates of stochastic gradient methods under gradient domination](https://mlsanity.com/paper/2405.13592/) (2024)
- [Controlling the Flow: Stability and Convergence for Stochastic Gradient Descent with Decaying Regularization](https://mlsanity.com/paper/2505.11434/) (2025)
- [Gradient-Normalized Smoothness for Optimization with Approximate Hessians](https://mlsanity.com/paper/2506.13710/) (2025)
- [On the Complexity of Finite-Sum Smooth Optimization under the Polyak-Lojasiewicz Condition](https://mlsanity.com/paper/2402.02569/) (2024)
- [Causal Invariance Learning via Efficient Nonconvex Optimization](https://mlsanity.com/paper/2412.11850/) (2024)
- [A Generalized Version of Chung's Lemma and its Applications](https://mlsanity.com/paper/2406.05637/) (2024)
- [A Homogenization Approach for Gradient-Dominated Stochastic Optimization](https://mlsanity.com/paper/2308.10630/) (2023)
- [Some remarks on gradient dominance and LQR policy optimization](https://mlsanity.com/paper/2507.10452/) (2025)
- [Variance-Reduced Policy Gradient is Nearly Minimax-Optimal](https://mlsanity.com/paper/2610.13692/) (2026)

## Abstract (arXiv)

We study the complexity of finding the global solution to stochastic nonconvex optimization when the objective function satisfies global Kurdyka-Lojasiewicz (KL) inequality and the queries from stochastic gradient oracles satisfy mild expected smoothness assumption. We first introduce a general framework to analyze Stochastic Gradient Descent (SGD) and its associated nonlinear dynamics under the setting. As a byproduct of our analysis, we obtain a sample complexity of O(ε-(4-α)/α) for SGD when the objective satisfies the so called α-PL condition, where α is the degree of gradient domination. Furthermore, we show that a modified SGD with variance reduction and restarting (PAGER) achieves an improved sample complexity of O(ε-2/α) when the objective satisfies the average smoothness assumption. This leads to the first optimal algorithm for the important case of α=1 which appears in applications such as policy optimization in reinforcement learning.