mlsanityData to 14 Oct 2026

Mini-batch Stochastic Approximation Methods for Nonconvex Stochastic Composite Optimization

arXiv 1308.6594 ↗First posted 29 Aug 2013math.OCcited by 143

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 28; 2022: 26; 2023: 24; 2024: 24; 2025: 26; 2026: 15.

143 papers.

Sort:

By area:

  1. 2021Dash: Semi-Supervised Learning with Dynamic Thresholdingcited by 148
  2. 2022Adam Can Converge Without Any Modification On Update Rulescited by 114
  3. 2021Distributionally Robust Federated Averagingcited by 104
  4. 2023On Penalty-based Bilevel Gradient Descent Methodcited by 87
  5. 2022Policy Gradient Method For Robust Reinforcement Learningcited by 69
  6. 2021Low-Rank Sinkhorn Factorizationcited by 67
  7. 2021Linear-Time Gromov Wasserstein Distances using Low Rank Couplings and Costscited by 61
  8. 2024Principled Penalty-based Methods for Bilevel Reinforcement Learning and RLHFcited by 41
  9. 2021SUPER-ADAM: Faster and Universal Framework of Adaptive Gradientscited by 40
  10. 2021Stochastic gradient descent with noise of machine learning type. Part I: Discrete time analysiscited by 39
  11. 2021Non-convex Distributionally Robust Optimization: Non-asymptotic Analysiscited by 39
  12. 2021Sinkhorn Distributionally Robust Optimizationcited by 38
38 more
  1. 2021Complexity Lower Bounds for Nonconvex-Strongly-Concave Min-Max Optimizationcited by 36
  2. 2021BiAdam: Fast Adaptive Bilevel Optimization Methodscited by 33
  3. 2022Provable Adaptivity of Adam under Non-uniform Smoothnesscited by 30
  4. 2021ZeroSARAH: Efficient Nonconvex Finite-Sum Optimization with Zero Full Gradient Computationcited by 29
  5. 2021Enhanced Bilevel Optimization via Bregman Distancecited by 28
  6. 2021HET: Scaling out Huge Embedding Model Training via Cache-enabled Distributed Frameworkcited by 28
  7. 2023Probabilistic Bilevel Coreset Selectioncited by 27
  8. 2021Generating Adversarial Computer Programs using Optimized Obfuscationscited by 22
  9. 2021On the Convergence of Step Decay Step-Size for Stochastic Optimizationcited by 21
  10. 2022SWIFT: Rapid Decentralized Federated Learning via Wait-Free Model Communicationcited by 21
  11. 2023Epidemic Learning: Boosting Decentralized Learning with Randomized Communicationcited by 21
  12. 2024Auto-Train-Once: Controller Network Guided Automatic Network Pruning from Scratchcited by 20
  13. 2021Distributed Learning Systems with First-order Methodscited by 17
  14. 2021Bregman Gradient Policy Optimizationcited by 17
  15. 2025Can SGD Handle Heavy-Tailed Noise?cited by 17
  16. 2021AsySQN: Faster Vertical Federated Learning Algorithms with Better Computation Resource Utilizationcited by 16
  17. 2022Anchor Sampling for Federated Learning with Partial Client Participationcited by 14
  18. 2023Fusion of Global and Local Knowledge for Personalized Federated Learningcited by 14
  19. 2023First Order Methods with Markovian Noise: from Acceleration to Variational Inequalitiescited by 14
  20. 2023Contextual Stochastic Bilevel Optimizationcited by 14
  21. 2024Convergence Guarantees for RMSProp and Adam in Generalized-smooth Non-convex Optimization with Affine Noise Variancecited by 14
  22. 2021AdaGDA: Faster Adaptive Gradient Descent Ascent Methods for Minimax Optimizationcited by 13
  23. 2022A Unified Convergence Theorem for Stochastic Optimization Methodscited by 12
  24. 2024Gradient Compressed Sensing: A Query-Efficient Gradient Estimator for High-Dimensional Zeroth-Order Optimizationcited by 12
  25. 2025Refining Adaptive Zeroth-Order Optimization at Easecited by 12
  26. 2022On the Hidden Biases of Policy Mirror Ascent in Continuous Action Spacescited by 11
  27. 2022Zeroth-Order Alternating Gradient Descent Ascent Algorithms for a Class of Nonconvex-Nonconcave Minimax Problemscited by 11
  28. 2024Taming Nonconvex Stochastic Mirror Descent with General Bregman Divergencecited by 11
  29. 2022Alternating Implicit Projected SGD and Its Efficient Variants for Equality-constrained Bilevel Optimizationcited by 10
  30. 2024Non-convex Stochastic Composite Optimization with Polyak Momentumcited by 9
  31. 2025Leveraging Coordinate Momentum in SignSGD and Muon: Memory-Optimized Zero-Ordercited by 9
  32. 2021Random-reshuffled SARAH does not need a full gradient computationscited by 7
  33. 2022Convergence of First-Order Methods for Constrained Nonconvex Optimization with Dependent Datacited by 7
  34. 2022Fast Adaptive Federated Bilevel Optimizationcited by 7
  35. 2023Nonconvex Stochastic Bregman Proximal Gradient Method with Application to Deep Learningcited by 7
  36. 2024MGDA Converges under Generalized Smoothness, Provablycited by 7
  37. 2024A Primal-Dual-Assisted Penalty Approach to Bilevel Optimization with Coupled Constraintscited by 7
  38. 2025Zeroth-Order Optimization is Secretly Single-Step Policy Optimizationcited by 7

50 most cited of 143 All 143 (JSON)