# A Hybrid Stochastic Optimization Framework for Stochastic Composite Nonconvex Optimization

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

## Key facts

- Cited by 27 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Jul 2019.

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

- [A Single-Timescale Method for Stochastic Bilevel Optimization](https://mlsanity.com/paper/2102.04671/) (2021)
- [LiMuon: Light and Fast Muon Optimizer for Large Models](https://mlsanity.com/paper/2509.14562/) (2025)
- [Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation Constrained Optimization](https://mlsanity.com/paper/2212.09513/) (2022)
- [DASHA: Distributed Nonconvex Optimization with Communication Compression, Optimal Oracle Complexity, and No Client Synchronization](https://mlsanity.com/paper/2202.01268/) (2022)
- [On Momentum-Based Gradient Methods for Bilevel Optimization with Nonconvex Lower-Level](https://mlsanity.com/paper/2303.03944/) (2023)
- [Communication Compression for Byzantine Robust Learning: New Efficient Algorithms and Improved Rates](https://mlsanity.com/paper/2310.09804/) (2023)
- [Variance-reduced first-order methods for deterministically constrained stochastic nonconvex optimization with strong convergence guarantees](https://mlsanity.com/paper/2409.09906/) (2024)
- [Non-convex Stochastic Composite Optimization with Polyak Momentum](https://mlsanity.com/paper/2403.02967/) (2024)
- [DoCoM: Compressed Decentralized Optimization with Near-Optimal Sample Complexity](https://mlsanity.com/paper/2202.00255/) (2022)
- [Enhanced Adaptive Gradient Algorithms for Nonconvex-PL Minimax Optimization](https://mlsanity.com/paper/2303.03984/) (2023)
- [Projected gradient methods for nonconvex and stochastic smooth optimization: new complexities and auto-conditioned stepsizes](https://mlsanity.com/paper/2412.14291/) (2024)
- [Adaptive Federated Minimax Optimization with Lower Complexities](https://mlsanity.com/paper/2211.07303/) (2022)
- [Towards Faster Decentralized Stochastic Optimization with Communication Compression](https://mlsanity.com/paper/2405.20114/) (2024)
- [Near-Optimal Decentralized Momentum Method for Nonconvex-PL Minimax Problems](https://mlsanity.com/paper/2304.10902/) (2023)
- [CDMA: A Practical Cross-Device Federated Learning Algorithm for General Minimax Problems](https://mlsanity.com/paper/2105.14216/) (2021)
- [Faster Adaptive Momentum-Based Federated Methods for Distributed Composition Optimization](https://mlsanity.com/paper/2211.01883/) (2022)
- [Faster Adaptive Decentralized Learning Algorithms](https://mlsanity.com/paper/2408.09775/) (2024)
- [Gradient-Free Method for Heavily Constrained Nonconvex Optimization](https://mlsanity.com/paper/2409.00459/) (2024)
- [Stochastic interior-point methods for smooth conic optimization with applications](https://mlsanity.com/paper/2412.12987/) (2024)
- [Adaptive Lipschitz-Free Proximal Gradient Methods for Stochastic Composite Nonconvex Optimization](https://mlsanity.com/paper/2502.21099/) (2025)
- [Versatile Single-Loop Method for Gradient Estimator: First and Second Order Optimality, and its Application to Federated Learning](https://mlsanity.com/paper/2209.00361/) (2022)
- [A stochastic first-order method with multi-extrapolated momentum for highly smooth unconstrained optimization](https://mlsanity.com/paper/2412.14488/) (2024)
- [Mirror Descent Linearized Augmented Lagrangian Methods for Nonconvex Constrained Stochastic Zeroth-Order Optimization](https://mlsanity.com/paper/2504.09409/) (2025)
- [A Hybrid Stochastic Gradient Tracking Method for Distributed Online Optimization Over Time-Varying Directed Networks](https://mlsanity.com/paper/2508.20645/) (2025)
- [DualHash: A Stochastic Primal-Dual Algorithm with Theoretical Guarantee for Deep Hashing](https://mlsanity.com/paper/2510.18218/) (2025)
- [CLion: Efficient Cautious Lion Optimizer with Enhanced Generalization](https://mlsanity.com/paper/2604.14587/) (2026)
- [A proximal subgradient method for nonconvex stochastic optimization under the Kurdyka-Lojasiewicz condition](https://mlsanity.com/paper/2608.05460/) (2026)

## Abstract (arXiv)

We introduce a new approach to develop stochastic optimization algorithms for a class of stochastic composite and possibly nonconvex optimization problems. The main idea is to combine two stochastic estimators to create a new hybrid one. We first introduce our hybrid estimator and then investigate its fundamental properties to form a foundational theory for algorithmic development. Next, we apply our theory to develop several variants of stochastic gradient methods to solve both expectation and finite-sum composite optimization problems. Our first algorithm can be viewed as a variant of proximal stochastic gradient methods with a single-loop, but can achieve O(σ3varepsilon-1 + σ varepsilon-3)-oracle complexity bound, matching the best-known ones from state-of-the-art double-loop algorithms in the literature, where σ > 0 is the variance and varepsilon is a desired accuracy. Then, we consider two different variants of our method: adaptive step-size and restarting schemes that have similar theoretical guarantees as in our first algorithm. We also study two mini-batch variants of the proposed methods. In all cases, we achieve the best-known complexity bounds under standard assumptions. We test our methods on several numerical examples with real datasets and compare them with state-of-the-arts. Our numerical experiments show that the new methods are comparable and, in many cases, outperform their competitors.