Track synthesis, materials and catalysis as it is published.
Search papers, labs, and topics across Lattice.
This paper introduces new projection-based and projection-free algorithms for nonsmooth, nonconvex stochastic optimization with convex constraints, achieving optimal convergence rates of $\widetilde O(\delta^{-1}\varepsilon^{-3})$ for stochastic gradients and $\widetilde O(d\delta^{-1}\varepsilon^{-3})$ for zeroth-order queries. These algorithms find $(\delta,\varepsilon)$-Goldstein stationary points, a recently defined notion of stationarity for constrained problems, and establish new lower bounds in terms of the Frank-Wolfe gap. The findings demonstrate that constraints and nonsmoothness do not inherently degrade convergence rates in nonconvex stochastic optimization.
Optimal $\widetilde O(\delta^{-1}\varepsilon^{-3})$ convergence for nonsmooth, nonconvex stochastic optimization with constraints is now achievable, matching theoretical lower bounds.
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 $(\delta,\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(\delta^{-1}\varepsilon^{-3})$ rate using stochastic gradients, which we show to be optimal, and a $\widetilde O(d\delta^{-1}\varepsilon^{-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.