# Hybrid Stochastic Gradient Descent Algorithms for Stochastic Nonconvex Optimization

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

## Key facts

- Cited by 32 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 May 2019.

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

- [A Near-Optimal Algorithm for Stochastic Bilevel Optimization via Double-Momentum](https://mlsanity.com/paper/2102.07367/) (2021)
- [Provably Faster Algorithms for Bilevel Optimization](https://mlsanity.com/paper/2106.04692/) (2021)
- [Convergence of Adam Under Relaxed Assumptions](https://mlsanity.com/paper/2304.13972/) (2023)
- [FedVARP: Tackling the Variance Due to Partial Client Participation in Federated Learning](https://mlsanity.com/paper/2207.14130/) (2022)
- [STEM: A Stochastic Two-Sided Momentum Algorithm Achieving Near-Optimal Sample and Communication Complexities for Federated Learning](https://mlsanity.com/paper/2106.10435/) (2021)
- [An Introduction to Bi-level Optimization: Foundations and Applications in Signal Processing and Machine Learning](https://mlsanity.com/paper/2308.00788/) (2023)
- [Lions and Muons: Optimization via Stochastic Frank-Wolfe under Heavy-Tailed Noise](https://mlsanity.com/paper/2506.04192/) (2025)
- [SUPER-ADAM: Faster and Universal Framework of Adaptive Gradients](https://mlsanity.com/paper/2106.08208/) (2021)
- [ZeroSARAH: Efficient Nonconvex Finite-Sum Optimization with Zero Full Gradient Computation](https://mlsanity.com/paper/2103.01447/) (2021)
- [Breaking the Lower Bound with (Little) Structure: Acceleration in Non-Convex Stochastic Optimization with Heavy-Tailed Noise](https://mlsanity.com/paper/2302.06763/) (2023)
- [FedShuffle: Recipes for Better Use of Local Work in Federated Learning](https://mlsanity.com/paper/2204.13169/) (2022)
- [Revisiting Gradient Normalization and Clipping for Nonconvex SGD under Heavy-Tailed Noise: Necessity, Sufficiency, and Acceleration](https://mlsanity.com/paper/2410.16561/) (2024)
- [Bregman Gradient Policy Optimization](https://mlsanity.com/paper/2106.12112/) (2021)
- [From Adaptive Query Release to Machine Unlearning](https://mlsanity.com/paper/2307.11228/) (2023)
- [An Accelerated Algorithm for Stochastic Bilevel Optimization under Unbounded Smoothness](https://mlsanity.com/paper/2409.19212/) (2024)
- [GT-STORM: Taming Sample, Communication, and Memory Complexities in Decentralized Non-Convex Learning](https://mlsanity.com/paper/2105.01231/) (2021)
- [Training Structured Neural Networks Through Manifold Identification and Variance Reduction](https://mlsanity.com/paper/2112.02612/) (2021)
- [DIAMOND: Taming Sample and Communication Complexities in Decentralized Bilevel Optimization](https://mlsanity.com/paper/2212.02376/) (2022)
- [Near-Optimal Non-Convex Stochastic Optimization under Generalized Smoothness](https://mlsanity.com/paper/2302.06032/) (2023)
- [MDPGT: Momentum-based Decentralized Policy Gradient Tracking](https://mlsanity.com/paper/2112.02813/) (2021)
- [Passage-Mask: A Learnable Regularization Strategy for Retriever-Reader Models](https://mlsanity.com/paper/2211.00915/) (2022)
- [Adaptive Variance Reduction for Stochastic Optimization under Weaker Assumptions](https://mlsanity.com/paper/2406.01959/) (2024)
- [META-STORM: Generalized Fully-Adaptive Variance Reduced SGD for Unbounded Functions](https://mlsanity.com/paper/2209.14853/) (2022)
- [STORM+: Fully Adaptive SGD with Momentum for Nonconvex Optimization](https://mlsanity.com/paper/2111.01040/) (2021)
- [Unbiased and Biased Variance-Reduced Forward-Reflected-Backward Splitting Methods for Stochastic Composite Inclusions](https://mlsanity.com/paper/2603.15576/) (2026)
- [Achieving O(ε-1.5) Complexity in Hessian/Jacobian-free Stochastic Bilevel Optimization](https://mlsanity.com/paper/2312.03807/) (2023)
- [Probabilistic Guarantees of Stochastic Recursive Gradient in Non-Convex Finite Sum Problems](https://mlsanity.com/paper/2401.15890/) (2024)
- [Faster Perturbed Stochastic Gradient Methods for Finding Local Minima](https://mlsanity.com/paper/2110.13144/) (2021)
- [Unified High-Probability Analysis of Stochastic Variance-Reduced Estimation](https://mlsanity.com/paper/2605.15388/) (2026)
- [Better Methods and Theory for Federated Learning: Compression, Client Selection and Heterogeneity](https://mlsanity.com/paper/2207.00392/) (2022)

## Abstract (arXiv)

We introduce a hybrid stochastic estimator to design stochastic gradient algorithms for solving stochastic optimization problems. Such a hybrid estimator is a convex combination of two existing biased and unbiased estimators and leads to some useful property on its variance. We limit our consideration to a hybrid SARAH-SGD for nonconvex expectation problems. However, our idea can be extended to handle a broader class of estimators in both convex and nonconvex settings. We propose a new single-loop stochastic gradient descent algorithm that can achieve O(maxσ3varepsilon-1,σvarepsilon-3)-complexity bound to obtain an varepsilon-stationary point under smoothness and σ2-bounded variance assumptions. This complexity is better than O(σ2varepsilon-4) often obtained in state-of-the-art SGDs when σ < O(varepsilon-3). We also consider different extensions of our method, including constant and adaptive step-size with single-loop, double-loop, and mini-batch variants. We compare our algorithms with existing methods on several datasets using two nonconvex models.