# Stochastic Second-Order Methods Improve Best-Known Sample Complexity of SGD for Gradient-Dominated Function

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

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 65 references that are in the map.
- First posted on arXiv 25 May 2022.

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

- [Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Condition](https://mlsanity.com/paper/1608.04636/) (2016)
- [Momentum-Based Variance Reduction in Non-Convex SGD](https://mlsanity.com/paper/1905.10018/) (2019)
- [On the Global Convergence Rates of Softmax Policy Gradient Methods](https://mlsanity.com/paper/2005.06392/) (2020)
- [Neural Policy Gradient Methods: Global Optimality and Rates of Convergence](https://mlsanity.com/paper/1909.01150/) (2019)
- [Better Theory for SGD in the Nonconvex World](https://mlsanity.com/paper/2002.03329/) (2020)
- [Convergence Analysis of Two-layer Neural Networks with ReLU Activation](https://mlsanity.com/paper/1705.09886/) (2017)
- [Global Convergence of Policy Gradient Methods to (Almost) Locally Optimal Policies](https://mlsanity.com/paper/1906.08383/) (2019)
- [Variational Policy Gradient Method for Reinforcement Learning with General Utilities](https://mlsanity.com/paper/2007.02151/) (2020)
- [Identity Matters in Deep Learning](https://mlsanity.com/paper/1611.04231/) (2016)
- [A general sample complexity analysis of vanilla policy gradient](https://mlsanity.com/paper/2107.11433/) (2021)
- [On the Convergence and Sample Efficiency of Variance-Reduced Policy Gradient Method](https://mlsanity.com/paper/2102.08607/) (2021)
- [Sub-sampled Cubic Regularization for Non-convex Optimization](https://mlsanity.com/paper/1705.05933/) (2017)
- [An Improved Convergence Analysis of Stochastic Variance-Reduced Policy Gradient](https://mlsanity.com/paper/1905.12615/) (2019)
- [Stochastic Cubic Regularization for Fast Nonconvex Optimization](https://mlsanity.com/paper/1711.02838/) (2017)
- [Second-Order Information in Non-Convex Stochastic Optimization: Power and Limitations](https://mlsanity.com/paper/2006.13476/) (2020)
- [Uniform Convergence of Gradients for Non-Convex Learning and Optimization](https://mlsanity.com/paper/1810.11059/) (2018)
- [Second-Order Optimization for Non-Convex Machine Learning: An Empirical Study](https://mlsanity.com/paper/1708.07827/) (2017)
- [Momentum-Based Policy Gradient Methods](https://mlsanity.com/paper/2007.06680/) (2020)
- [An Asynchronous Parallel Stochastic Coordinate Descent Algorithm](https://mlsanity.com/paper/1311.1873/) (2013)
- [Tight Dimension Independent Lower Bound on the Expected Convergence Rate for Diminishing Step Sizes in SGD](https://mlsanity.com/paper/1810.04723/) (2018)
- [Sample Complexity of Policy Gradient Finding Second-Order Stationary Points](https://mlsanity.com/paper/2012.01491/) (2020)
- [Stochastic Variance-Reduced Cubic Regularization for Nonconvex Optimization](https://mlsanity.com/paper/1802.07372/) (2018)
- [Stochastic Recursive Variance-Reduced Cubic Regularization Methods](https://mlsanity.com/paper/1901.11518/) (2019)
- [Stochastic Variance-Reduced Cubic Regularized Newton Method](https://mlsanity.com/paper/1802.04796/) (2018)
- [Finding Approximate Local Minima Faster than Gradient Descent](https://mlsanity.com/paper/1611.01146/) (2016)
- [Convergence of Cubic Regularization for Nonconvex Optimization under KL Property](https://mlsanity.com/paper/1808.07382/) (2018)
- [Adaptive Stochastic Variance Reduction for Subsampled Newton Method with Cubic Regularization](https://mlsanity.com/paper/1811.11637/) (2018)
- [Inexact Proximal Cubic Regularized Newton Methods for Convex Optimization](https://mlsanity.com/paper/1902.02388/) (2019)

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

- [A Novel Framework for Policy Mirror Descent with General Parameterization and Linear Convergence](https://mlsanity.com/paper/2301.13139/) (2023)
- [Improved Sample Complexity Analysis of Natural Policy Gradient Algorithm with General Parameterization for Infinite Horizon Discounted Reward Markov Decision Processes](https://mlsanity.com/paper/2310.11677/) (2023)
- [Reinforcement Learning with General Utilities: Simpler Variance Reduction and Large State-Action Space](https://mlsanity.com/paper/2306.01854/) (2023)
- [Unified Convergence Theory of Stochastic and Variance-Reduced Cubic Newton Methods](https://mlsanity.com/paper/2302.11962/) (2023)
- [Learning Optimal Deterministic Policies with Stochastic Policy Gradients](https://mlsanity.com/paper/2405.02235/) (2024)
- [Sample-Efficient Constrained Reinforcement Learning with General Parameterization](https://mlsanity.com/paper/2405.10624/) (2024)
- [A safe exploration approach to constrained Markov decision processes](https://mlsanity.com/paper/2312.00561/) (2023)
- [On The Sample Complexity Bounds In Bilevel Reinforcement Learning](https://mlsanity.com/paper/2503.17644/) (2025)
- [Global Convergence of Natural Policy Gradient with Hessian-aided Momentum Variance Reduction](https://mlsanity.com/paper/2401.01084/) (2024)
- [Global Convergence Guarantees for Federated Policy Gradient Methods with Adversaries](https://mlsanity.com/paper/2403.09940/) (2024)
- [Regret Analysis of Unichain Average Reward Constrained MDPs with General Parameterization](https://mlsanity.com/paper/2602.08000/) (2026)
- [On The Global Convergence Of Online RLHF With Neural Parametrization](https://mlsanity.com/paper/2410.15610/) (2024)
- [Last-Iterate Global Convergence of Policy Gradients for Constrained Reinforcement Learning](https://mlsanity.com/paper/2407.10775/) (2024)
- [Deep Learning Frameworks for Cognitive Radio Networks: Review and Open Research Challenges](https://mlsanity.com/paper/2410.23949/) (2024)
- [Last-Iterate Convergence of General Parameterized Policies in Constrained MDPs](https://mlsanity.com/paper/2408.11513/) (2024)
- [Blockwise Stabilized Adaptive Cubic Regularization with Subsolvers via Recurrence](https://mlsanity.com/paper/2608.22129/) (2026)
- [Stochastic Gradient Langevin Dynamics Based on Quantization with Increasing Resolution](https://mlsanity.com/paper/2305.18864/) (2023)
- [A Homogenization Approach for Gradient-Dominated Stochastic Optimization](https://mlsanity.com/paper/2308.10630/) (2023)
- [A Variance-Reduced Cubic-Regularized Newton for Policy Optimization](https://mlsanity.com/paper/2507.10120/) (2025)
- [Variance-Reduced Policy Gradient is Nearly Minimax-Optimal](https://mlsanity.com/paper/2610.13692/) (2026)

## Abstract (arXiv)

We study the performance of Stochastic Cubic Regularized Newton (SCRN) on a class of functions satisfying gradient dominance property with 1≤α≤2 which holds in a wide range of applications in machine learning and signal processing. This condition ensures that any first-order stationary point is a global optimum. We prove that the total sample complexity of SCRN in achieving ε-global optimum is O(ε-7/(2α)+1) for 1≤α< 3/2 and mathcaltildeO(ε-2/(α)) for 3/2≤α≤ 2. SCRN improves the best-known sample complexity of stochastic gradient descent. Even under a weak version of gradient dominance property, which is applicable to policy-based reinforcement learning (RL), SCRN achieves the same improvement over stochastic policy gradient methods. Additionally, we show that the average sample complexity of SCRN can be reduced to O(ε-2) for α=1 using a variance reduction method with time-varying batch sizes. Experimental results in various RL settings showcase the remarkable performance of SCRN compared to first-order methods.