mlsanityData to 14 Oct 2026

Optimal Algorithms for Nonsmooth Nonconvex Stochastic Optimization with Constraints

arXiv 2610.13787 ↗First posted 9 Oct 2026math.OC cs.LGcited by 0

Not on the map. Why?

Abstract (arXiv)

We present new algorithms for stochastic optimization problems in which the objective is neither smooth nor convex, subject to a convex constraint set. Our algorithms return a (δ,varepsilon)-Goldstein stationary point, as recently defined for constrained problems by Liu et al. (2024), with improved complexities, and are the first to achieve optimal convergence rates for this task in several settings. In particular, we design projection-based and projection-free algorithms that achieve a widetilde O(δ-1varepsilon-3) rate using stochastic gradients, which we show to be optimal, and a widetilde O(dδ-1varepsilon-3) rate using zeroth-order queries, which is also optimal in its dependence on the dimension d and improves over prior work. Notably, our lower bound is given in terms of the Frank-Wolfe gap and holds even for smooth problems, which is of independent interest. These results show that in nonconvex stochastic optimization, the convergence rate is degraded neither by the presence of constraints nor by nonsmoothness. Our analysis is based on a reduction to online linear optimization, extending a related technique from unconstrained optimization.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 41 of its 69 references that are in the map. First posted on arXiv 9 Oct 2026.

Builds on

41 of 69 references.

References · 41

  1. 2017Towards Deep Learning Models Resistant to Adversarial Attackscited by 6,415
  2. 2013Intriguing properties of neural networkscited by 5,155
  3. 2020Sharpness-Aware Minimization for Efficiently Improving Generalizationcited by 1,417
  4. 2019Introduction to Online Convex Optimizationcited by 803
  5. 2019Online Learning: A Modern Introduction Using Convex Optimizationcited by 417
  6. 2023Visual Adversarial Examples Jailbreak Aligned Large Language Modelscited by 328
  7. 2019Lower Bounds for Non-Convex Stochastic Optimizationcited by 307
  8. 2013Optimal rates for zero-order convex optimization: the power of two function evaluationscited by 198
  9. 2013Maxout Networkscited by 187
  10. 2013Mini-batch Stochastic Approximation Methods for Nonconvex Stochastic Composite Optimizationcited by 143
  11. 2021On the Convergence and Robustness of Adversarial Trainingcited by 130
  12. 2017Lower Bounds for Finding Stationary Points Icited by 126
29 more
  1. 2018Stochastic subgradient method converges on tame functionscited by 124
  2. 2015An Optimal Algorithm for Bandit and Zero-Order Convex Optimization with Two-Point Feedbackcited by 111
  3. 2013Accelerated Gradient Methods for Nonconvex Nonlinear and Stochastic Programmingcited by 75
  4. 2016Convergence Rate of Frank-Wolfe for Non-Convex Objectivescited by 63
  5. 2023Optimal Stochastic Non-smooth Non-convex Optimization through Online-to-Non-convex Conversioncited by 45
  6. 2014Faster Rates for the Frank-Wolfe Method over Strongly-Convex Setscited by 44
  7. 2022Gradient-Free Methods for Deterministic and Stochastic Nonsmooth Nonconvex Optimizationcited by 43
  8. 2016Stochastic Frank-Wolfe Methods for Nonconvex Optimizationcited by 41
  9. 2020Faster Projection-free Online Learningcited by 40
  10. 2021Oracle Complexity in Nonsmooth Nonconvex Optimizationcited by 39
  11. 2021A gradient sampling method with complexity guarantees for Lipschitz functions in high and low dimensionscited by 39
  12. 2021Efficient Projection-Free Online Convex Optimization with Membership Oraclecited by 30
  13. 2023Why Does Sharpness-Aware Minimization Generalize Better Than SGD?cited by 28
  14. 2024Understanding Adam Optimizer via Online Learning of Updates: Adam is FTRL in Disguisecited by 26
  15. 2023An Algorithm with Optimal Dimension-Dependence for Zero-Order Nonsmooth Nonconvex Stochastic Optimizationcited by 23
  16. 2024Adam with model exponential moving average is effective for nonconvex optimizationcited by 23
  17. 2019Complexity of Highly Parallel Non-Smooth Convex Optimizationcited by 22
  18. 2020Revisiting Projection-free Online Learning: the Strongly Convex Casecited by 21
  19. 2021Complexity of Linear Minimization and Projection on Some Setscited by 20
  20. 2024Random Scaling and Momentum for Non-smooth Non-convex Optimizationcited by 19
  21. 2024General framework for online-to-nonconvex conversion: Schedule-free SGD is also effective for nonconvex optimizationcited by 15
  22. 2019Convergence of a Stochastic Subgradient Method with Averaging for Nonsmooth Nonconvex Constrained Optimizationcited by 10
  23. 2020Regret minimization in stochastic non-convex learning via a proximal-gradient approachcited by 9
  24. 2024Online Convex Optimization with a Separation Oraclecited by 8
  25. 2023Goldstein Stationarity in Lipschitz Constrained Optimizationcited by 6
  26. 2023Lookbehind-SAM: k steps back, 1 step forwardcited by 5
  27. 2025Zeroth-Order Methods for Stochastic Nonconvex Nonsmooth Composite Optimizationcited by 2
  28. 2025Finite-Time Analysis of Stochastic Nonconvex Nonsmooth Optimization on the Riemannian Manifoldscited by 2
  29. 2026The Complexity of Finding Stationary Points in Nonsmooth Nonconvex Optimizationcited by 1

Built on by

Not cited yet.