Optimal Algorithms for Nonsmooth Nonconvex Stochastic Optimization with Constraints

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 which both converge at a $\tilde{O}(\varepsilon^{-4})$ rate using stochastic gradients, which we also show to be optimal, or else at a $\tilde{O}(d\varepsilon^{-4})$ rate using zeroth-order queries in dimension $d$. Notably, our lower bound in terms of the Frank-Wolfe gap holds even for smooth problems, which is of independent interest. Our results show that the convergence rate does not degrade neither by incorporating constraints nor by the lack of smoothness. Our analysis is based on a reduction from constrained optimization to online linear optimization, extending a related technique from unconstrained optimization.