Improved algorithms find solutions in complex constrained problems
Optimal Algorithms for Nonsmooth Nonconvex Stochastic Optimization with Constraints
Machine Learning
Summary
Many optimization problems are hard because the problem isn’t smooth or simple and must obey certain rules. The authors present new methods that can find good approximate solutions efficiently even when the problem has tough constraints and is not smooth or convex. They prove their methods are as fast as possible in several important cases, which wasn’t known before. Their work shows that constraints and roughness don't slow down how quickly you can find solutions in these hard problems.
What this means in practice
- •For machine learning engineers: Optimize machine learning models with complex constraints and nonsmooth objectives more efficiently using the presented optimal-rate algorithms.
- •For operations research teams: Solve constrained decision-making problems where objective functions are nonsmooth and stochastic using faster algorithms with provable guarantees.
Authors
Gon Buzaglo, Guy Kornowski
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 $(δ,\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(δ^{-1}\varepsilon^{-3})$ rate using stochastic gradients, which we show to be optimal, and a $\widetilde O(dδ^{-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.