Optimal Algorithms for Nonsmooth Nonconvex Stochastic Optimization with Constraints
Abstract
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 (δ,ε)-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 Õ(δ−1ε−3) rate using stochastic gradients, which we show to be optimal, and a Õ(dδ−1ε−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.
Related
- Variable Bregman Majorization-Minimization algorithms for nonconvex nonsmooth optimization, with application to Poisson imaging
- Dimension-Free Decentralized Nonsmooth Nonconvex Stochastic Optimization
- Deterministic Oracle Complexity for Goldstein Stationarity in Nonsmooth Nonconvex Optimization with Constraints
- Lower Bounds for Stochastic First-Order Algorithms with Variance Reduction in Nonconvex--Concave Minimax Optimization
- Asymptotic Analysis of Gradient Mapping-type Stationarity Measure for the Sum of Nonconvex Nonsmooth Functions and Applications to Proximal Gradient-type Algorithms
BibTeX
@misc{buzaglo2026optimal,
title = {{Optimal Algorithms for Nonsmooth Nonconvex Stochastic Optimization with Constraints}},
author = {Gon Buzaglo and Guy Kornowski},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.13787},
eprint = {2610.13787},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.13787},
}
RIS
TY - UNPB
TI - Optimal Algorithms for Nonsmooth Nonconvex Stochastic Optimization with Constraints
AU - Gon Buzaglo
AU - Guy Kornowski
PY - 2026
DA - 2026/10/09
PB - arXiv
DO - 10.48550/arxiv.2610.13787
UR - https://arxiv.org/abs/2610.13787
AB - 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 (δ,ε)-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 Õ(δ^−1ε^−3) rate using stochastic gradients, which we show to be optimal, and a Õ(dδ^−1ε^−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.
ER -