Optimal Algorithms for Nonsmooth Nonconvex Stochastic Optimization with Constraints
The paper claims optimal rates for finding constrained Goldstein stationary points in nonsmooth nonconvex stochastic optimization.
Buzaglo and Kornowski give both projection-based and projection-free algorithms for convex constraint sets. With stochastic gradients, they report a \(\widetilde O(\delta^{-1}\varepsilon^{-3})\) rate; with zeroth-order queries, \(\widetilde O(d\delta^{-1}\varepsilon^{-3})\). They also prove matching lower bounds, including one framed through the Frank-Wolfe gap that applies even to smooth problems. Their conclusion is that, for this task, constraints and nonsmoothness do not worsen the nonconvex stochastic convergence rate. ArXiv · AI/CL/LG's note
Buzaglo and Kornowski give both projection-based and projection-free algorithms for convex constraint sets. With stochastic gradients, they report a \(\widetilde O(\delta^{-1}\varepsilon^{-3})\) rate; with zeroth-order queries, \(\widetilde O(d\delta^{-1}\varepsilon^{-3})\). They also prove matching lower bounds, including one framed through the Frank-Wolfe gap that applies even to smooth problems. Their conclusion is that, for this task, constraints and nonsmoothness do not worsen the nonconvex stochastic convergence rate. ArXiv · AI/CL/LG's note
score 5