Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper tackles stochastic nonsmooth nonconvex composite optimization, a class encompassing constrained optimization and neural network training, by extending the online-to-nonconvex conversion framework. The authors introduce novel losses for the online learner that incorporate the convex regularizer directly, enabling a variant of online mirror descent to achieve low regret. The resulting algorithm achieves optimal $O(\delta^{-1}\varepsilon^{-3})$ stochastic gradient query or $O(d\delta^{-1}\varepsilon^{-3})$ function-value query complexity, matching noncomposite settings and proving the regularizer's minimal impact on oracle complexity.
Optimal oracle complexity for nonsmooth nonconvex composite optimization is finally achieved, matching noncomposite rates by cleverly incorporating the convex regularizer into online learning losses.
We consider stochastic nonsmooth nonconvex composite optimization, which includes several important problems such as constrained optimization and the regularized training of neural networks. The objective is the sum of a possibly nonsmooth nonconvex Lipschitz function and a convex regularizer, and the function is accessed through stochastic gradients or function values. The goal is to find a point that satisfies a Goldstein-type stationarity condition designed for composite objectives. To our knowledge, no oracle complexity bound for this setting is known under first-order access, and existing complexities under zeroth-order access are suboptimal. To handle this issue, we employ the framework of online-to-nonconvex conversion, which chooses update directions by an online learner and is known to achieve optimal rates for noncomposite problems. We extend the framework to our composite scenario by introducing new losses for the learner, which contain the regularizer itself rather than its linearization and for which a variant of online mirror descent achieves low regret. We show that the resulting algorithm finds such a point with $O(\delta^{-1}\varepsilon^{-3})$ stochastic gradient queries or $O(d\delta^{-1}\varepsilon^{-3})$ function-value queries, where $\delta$ is the Goldstein radius, $\varepsilon$ is the stationarity tolerance, and $d$ is the dimension. These rates match the optimal ones for noncomposite nonsmooth nonconvex optimization, demonstrating that the additional convex regularizer does not worsen the oracle complexity. We also give rates for the smooth case and present numerical experiments.