mlsanityData to 14 Oct 2026

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

arXiv 2205.12856 ↗First posted 25 May 2022cs.LG math.OCcited by 20

Not on the map. Why?

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.

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

28 of 65 references.

References · 28

  1. 2016Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Conditioncited by 539
  2. 2019Momentum-Based Variance Reduction in Non-Convex SGDcited by 306
  3. 2020On the Global Convergence Rates of Softmax Policy Gradient Methodscited by 264
  4. 2019Neural Policy Gradient Methods: Global Optimality and Rates of Convergencecited by 159
  5. 2020Better Theory for SGD in the Nonconvex Worldcited by 158
  6. 2017Convergence Analysis of Two-layer Neural Networks with ReLU Activationcited by 137
  7. 2019Global Convergence of Policy Gradient Methods to (Almost) Locally Optimal Policiescited by 124
  8. 2020Variational Policy Gradient Method for Reinforcement Learning with General Utilitiescited by 111
  9. 2016Identity Matters in Deep Learningcited by 109
  10. 2021A general sample complexity analysis of vanilla policy gradientcited by 76
  11. 2021On the Convergence and Sample Efficiency of Variance-Reduced Policy Gradient Methodcited by 70
  12. 2017Sub-sampled Cubic Regularization for Non-convex Optimizationcited by 63
16 more
  1. 2019An Improved Convergence Analysis of Stochastic Variance-Reduced Policy Gradientcited by 59
  2. 2017Stochastic Cubic Regularization for Fast Nonconvex Optimizationcited by 55
  3. 2020Second-Order Information in Non-Convex Stochastic Optimization: Power and Limitationscited by 40
  4. 2018Uniform Convergence of Gradients for Non-Convex Learning and Optimizationcited by 38
  5. 2017Second-Order Optimization for Non-Convex Machine Learning: An Empirical Studycited by 35
  6. 2020Momentum-Based Policy Gradient Methodscited by 30
  7. 2013An Asynchronous Parallel Stochastic Coordinate Descent Algorithmcited by 26
  8. 2018Tight Dimension Independent Lower Bound on the Expected Convergence Rate for Diminishing Step Sizes in SGDcited by 18
  9. 2020Sample Complexity of Policy Gradient Finding Second-Order Stationary Pointscited by 17
  10. 2018Stochastic Variance-Reduced Cubic Regularization for Nonconvex Optimizationcited by 12
  11. 2019Stochastic Recursive Variance-Reduced Cubic Regularization Methodscited by 12
  12. 2018Stochastic Variance-Reduced Cubic Regularized Newton Methodcited by 10
  13. 2016Finding Approximate Local Minima Faster than Gradient Descentcited by 8
  14. 2018Convergence of Cubic Regularization for Nonconvex Optimization under KL Propertycited by 8
  15. 2018Adaptive Stochastic Variance Reduction for Subsampled Newton Method with Cubic Regularizationcited by 3
  16. 2019Inexact Proximal Cubic Regularized Newton Methods for Convex Optimizationcited by 1

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 7; 2024: 8; 2025: 2; 2026: 3.

20 papers.

Sort:

By area:

  1. 2023A Novel Framework for Policy Mirror Descent with General Parameterization and Linear Convergencecited by 30
  2. 2023Improved Sample Complexity Analysis of Natural Policy Gradient Algorithm with General Parameterization for Infinite Horizon Discounted Reward Markov Decision Processescited by 25
  3. 2023Reinforcement Learning with General Utilities: Simpler Variance Reduction and Large State-Action Spacecited by 18
  4. 2023Unified Convergence Theory of Stochastic and Variance-Reduced Cubic Newton Methodscited by 12
  5. 2024Learning Optimal Deterministic Policies with Stochastic Policy Gradientscited by 12
  6. 2024Sample-Efficient Constrained Reinforcement Learning with General Parameterizationcited by 11
  7. 2023A safe exploration approach to constrained Markov decision processescited by 10
  8. 2025On The Sample Complexity Bounds In Bilevel Reinforcement Learningcited by 10
  9. 2024Global Convergence of Natural Policy Gradient with Hessian-aided Momentum Variance Reductioncited by 6
  10. 2024Global Convergence Guarantees for Federated Policy Gradient Methods with Adversariescited by 6
  11. 2026Regret Analysis of Unichain Average Reward Constrained MDPs with General Parameterizationcited by 4
  12. 2024On The Global Convergence Of Online RLHF With Neural Parametrizationcited by 3
8 more
  1. 2024Last-Iterate Global Convergence of Policy Gradients for Constrained Reinforcement Learningcited by 2
  2. 2024Deep Learning Frameworks for Cognitive Radio Networks: Review and Open Research Challengescited by 2
  3. 2024Last-Iterate Convergence of General Parameterized Policies in Constrained MDPscited by 1
  4. 2026Blockwise Stabilized Adaptive Cubic Regularization with Subsolvers via Recurrencecited by 1
  5. 2023Stochastic Gradient Langevin Dynamics Based on Quantization with Increasing Resolutioncited by 0
  6. 2023A Homogenization Approach for Gradient-Dominated Stochastic Optimizationcited by 0
  7. 2025A Variance-Reduced Cubic-Regularized Newton for Policy Optimizationcited by 0
  8. 2026Variance-Reduced Policy Gradient is Nearly Minimax-Optimalcited by 0