# Mini-batch Stochastic Approximation Methods for Nonconvex Stochastic Composite Optimization

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

## Key facts

- Cited by 143 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Aug 2013.

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

- [Dash: Semi-Supervised Learning with Dynamic Thresholding](https://mlsanity.com/paper/2109.00650/) (2021)
- [Adam Can Converge Without Any Modification On Update Rules](https://mlsanity.com/paper/2208.09632/) (2022)
- [Distributionally Robust Federated Averaging](https://mlsanity.com/paper/2102.12660/) (2021)
- [On Penalty-based Bilevel Gradient Descent Method](https://mlsanity.com/paper/2302.05185/) (2023)
- [Policy Gradient Method For Robust Reinforcement Learning](https://mlsanity.com/paper/2205.07344/) (2022)
- [Low-Rank Sinkhorn Factorization](https://mlsanity.com/paper/2103.04737/) (2021)
- [Linear-Time Gromov Wasserstein Distances using Low Rank Couplings and Costs](https://mlsanity.com/paper/2106.01128/) (2021)
- [Principled Penalty-based Methods for Bilevel Reinforcement Learning and RLHF](https://mlsanity.com/paper/2402.06886/) (2024)
- [SUPER-ADAM: Faster and Universal Framework of Adaptive Gradients](https://mlsanity.com/paper/2106.08208/) (2021)
- [Stochastic gradient descent with noise of machine learning type. Part I: Discrete time analysis](https://mlsanity.com/paper/2105.01650/) (2021)
- [Non-convex Distributionally Robust Optimization: Non-asymptotic Analysis](https://mlsanity.com/paper/2110.12459/) (2021)
- [Sinkhorn Distributionally Robust Optimization](https://mlsanity.com/paper/2109.11926/) (2021)
- [Complexity Lower Bounds for Nonconvex-Strongly-Concave Min-Max Optimization](https://mlsanity.com/paper/2104.08708/) (2021)
- [BiAdam: Fast Adaptive Bilevel Optimization Methods](https://mlsanity.com/paper/2106.11396/) (2021)
- [Provable Adaptivity of Adam under Non-uniform Smoothness](https://mlsanity.com/paper/2208.09900/) (2022)
- [ZeroSARAH: Efficient Nonconvex Finite-Sum Optimization with Zero Full Gradient Computation](https://mlsanity.com/paper/2103.01447/) (2021)
- [Enhanced Bilevel Optimization via Bregman Distance](https://mlsanity.com/paper/2107.12301/) (2021)
- [HET: Scaling out Huge Embedding Model Training via Cache-enabled Distributed Framework](https://mlsanity.com/paper/2112.07221/) (2021)
- [Probabilistic Bilevel Coreset Selection](https://mlsanity.com/paper/2301.09880/) (2023)
- [Generating Adversarial Computer Programs using Optimized Obfuscations](https://mlsanity.com/paper/2103.11882/) (2021)
- [On the Convergence of Step Decay Step-Size for Stochastic Optimization](https://mlsanity.com/paper/2102.09393/) (2021)
- [SWIFT: Rapid Decentralized Federated Learning via Wait-Free Model Communication](https://mlsanity.com/paper/2210.14026/) (2022)
- [Epidemic Learning: Boosting Decentralized Learning with Randomized Communication](https://mlsanity.com/paper/2310.01972/) (2023)
- [Auto-Train-Once: Controller Network Guided Automatic Network Pruning from Scratch](https://mlsanity.com/paper/2403.14729/) (2024)
- [Distributed Learning Systems with First-order Methods](https://mlsanity.com/paper/2104.05245/) (2021)
- [Bregman Gradient Policy Optimization](https://mlsanity.com/paper/2106.12112/) (2021)
- [Can SGD Handle Heavy-Tailed Noise?](https://mlsanity.com/paper/2508.04860/) (2025)
- [AsySQN: Faster Vertical Federated Learning Algorithms with Better Computation Resource Utilization](https://mlsanity.com/paper/2109.12519/) (2021)
- [Anchor Sampling for Federated Learning with Partial Client Participation](https://mlsanity.com/paper/2206.05891/) (2022)
- [Fusion of Global and Local Knowledge for Personalized Federated Learning](https://mlsanity.com/paper/2302.11051/) (2023)

## Abstract (arXiv)

This paper considers a class of constrained stochastic composite optimization problems whose objective function is given by the summation of a differentiable (possibly nonconvex) component, together with a certain non-differentiable (but convex) component. In order to solve these problems, we propose a randomized stochastic projected gradient (RSPG) algorithm, in which proper mini-batch of samples are taken at each iteration depending on the total budget of stochastic samples allowed. The RSPG algorithm also employs a general distance function to allow taking advantage of the geometry of the feasible region. Complexity of this algorithm is established in a unified setting, which shows nearly optimal complexity of the algorithm for convex stochastic programming. A post-optimization phase is also proposed to significantly reduce the variance of the solutions returned by the algorithm. In addition, based on the RSPG algorithm, a stochastic gradient free algorithm, which only uses the stochastic zeroth-order information, has been also discussed. Some preliminary numerical results are also provided.