Optimal stochastic methods solve composite nonsmooth nonconvex problems
Composite Online-to-Nonconvex Conversion with Optimal Oracle Complexity
Machine Learning
Summary
Finding good solutions to complex optimization problems that have both smooth and nonsmooth parts can be very tricky. This paper shows a way to efficiently find points that meet a specific condition called Goldstein stationarity, even when only noisy gradient or function value information is available. The method improves on previous approaches by handling an extra convex regularizer without increasing the computational effort. The authors also provide formulas that describe how many steps are needed and back them up with numerical tests.
What this means in practice
- •For machine learning engineers: Train neural networks with nonsmooth regularizers more efficiently using fewer gradient or function evaluations.
- •For optimization software developers: Build optimization libraries that handle nonsmooth nonconvex composite problems with optimal query complexity guarantees.
Authors
Mingyi Li, Taira Tsuchiya, Kenji Yamanishi
Abstract
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(δ^{-1}\varepsilon^{-3})$ stochastic gradient queries or $O(dδ^{-1}\varepsilon^{-3})$ function-value queries, where $δ$ 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.