# Stochastic Quasi-Newton Methods for Nonconvex Stochastic Optimization

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

## Key facts

- Cited by 37 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Jul 2016.

## Built on by (most cited first, 30 of 37)

- [An Improved Analysis of (Variance-Reduced) Policy Gradient and Natural Policy Gradient Methods](https://mlsanity.com/paper/2211.07937/) (2022)
- [Linear Convergence of Natural Policy Gradient Methods with Log-Linear Policies](https://mlsanity.com/paper/2210.01400/) (2022)
- [SUPER-ADAM: Faster and Universal Framework of Adaptive Gradients](https://mlsanity.com/paper/2106.08208/) (2021)
- [Secure Bilevel Asynchronous Vertical Federated Learning with Backward Updating](https://mlsanity.com/paper/2103.00958/) (2021)
- [Differentially private inference via noisy optimization](https://mlsanity.com/paper/2103.11003/) (2021)
- [An Adaptive Stochastic Sequential Quadratic Programming with Differentiable Exact Augmented Lagrangians](https://mlsanity.com/paper/2102.05320/) (2021)
- [Tensor Normal Training for Deep Learning Models](https://mlsanity.com/paper/2106.02925/) (2021)
- [Provably Convergent Plug-and-Play Quasi-Newton Methods](https://mlsanity.com/paper/2303.07271/) (2023)
- [SP2: A Second Order Stochastic Polyak Method](https://mlsanity.com/paper/2207.08171/) (2022)
- [Stochastic Approximation Beyond Gradient for Signal Processing and Machine Learning](https://mlsanity.com/paper/2302.11147/) (2023)
- [Stochastic Variance-Reduced Newton: Accelerating Finite-Sum Minimization with Large Batches](https://mlsanity.com/paper/2206.02702/) (2022)
- [Gradient descent with generalized Newton's method](https://mlsanity.com/paper/2407.02772/) (2024)
- [Stochastic Anderson Mixing for Nonconvex Stochastic Optimization](https://mlsanity.com/paper/2110.01543/) (2021)
- [Kronecker-factored Quasi-Newton Methods for Deep Learning](https://mlsanity.com/paper/2102.06737/) (2021)
- [slimTrain -- A Stochastic Approximation Method for Training Separable Deep Neural Networks](https://mlsanity.com/paper/2109.14002/) (2021)
- [A Normal Map-Based Proximal Stochastic Gradient Method: Convergence and Identification Properties](https://mlsanity.com/paper/2305.05828/) (2023)
- [A New Random Reshuffling Method for Nonsmooth Nonconvex Finite-sum Optimization](https://mlsanity.com/paper/2312.01047/) (2023)
- [Physics-Informed Neural Networks with Trust-Region Sequential Quadratic Programming](https://mlsanity.com/paper/2409.10777/) (2024)
- [Revisiting Recursive Least Squares for Training Deep Neural Networks](https://mlsanity.com/paper/2109.03220/) (2021)
- [FedSSO: A Federated Server-Side Second-Order Optimization Algorithm](https://mlsanity.com/paper/2206.09576/) (2022)
- [Incremental Quasi-Newton Methods with Faster Superlinear Convergence Rates](https://mlsanity.com/paper/2402.02359/) (2024)
- [Symmetric Rank-One Quasi-Newton Methods for Deep Learning Using Cubic Regularization](https://mlsanity.com/paper/2502.12298/) (2025)
- [Why is Normalization Preferred? A Worst-Case Complexity Theory for Stochastically Preconditioned SGD under Heavy-Tailed Noise](https://mlsanity.com/paper/2602.13413/) (2026)
- [Adaptive First- and Second-Order Algorithms for Large-Scale Machine Learning](https://mlsanity.com/paper/2111.14761/) (2021)
- [A Novel Fast Exact Subproblem Solver for Stochastic Quasi-Newton Cubic Regularized Optimization](https://mlsanity.com/paper/2204.09116/) (2022)
- [On the efficiency of Stochastic Quasi-Newton Methods for Deep Learning](https://mlsanity.com/paper/2205.09121/) (2022)
- [Convergence Rates of Stochastic Zeroth-order Gradient Descent for L ojasiewicz Functions](https://mlsanity.com/paper/2210.16997/) (2022)
- [FOSI: Hybrid First and Second Order Optimization](https://mlsanity.com/paper/2302.08484/) (2023)
- [A Stochastic Quasi-Newton Method for Non-convex Optimization with Non-uniform Smoothness](https://mlsanity.com/paper/2403.15244/) (2024)
- [A theoretical and empirical study of new adaptive algorithms with additional momentum steps and shifted updates for stochastic non-convex optimization](https://mlsanity.com/paper/2110.08531/) (2021)

## Abstract (arXiv)

In this paper we study stochastic quasi-Newton methods for nonconvex stochastic optimization, where we assume that noisy information about the gradients of the objective function is available via a stochastic first-order oracle (SFO). We propose a general framework for such methods, for which we prove almost sure convergence to stationary points and analyze its worst-case iteration complexity. When a randomly chosen iterate is returned as the output of such an algorithm, we prove that in the worst-case, the SFO-calls complexity is O(ε-2) to ensure that the expectation of the squared norm of the gradient is smaller than the given accuracy tolerance ε. We also propose a specific algorithm, namely a stochastic damped L-BFGS (SdLBFGS) method, that falls under the proposed framework. Moreover, we incorporate the SVRG variance reduction technique into the proposed SdLBFGS method, and analyze its SFO-calls complexity. Numerical results on a nonconvex binary classification problem using SVM, and a multiclass classification problem using neural networks are reported.