Can We Find Near-Approximately-Stationary Points of Nonsmooth Nonconvex Functions?
This addresses a fundamental limitation in optimization theory for nonsmooth nonconvex problems, such as those in neural network training, but is incremental as it builds on prior impossibility results.
The paper tackles the problem of finding near-approximately-stationary points for nonsmooth nonconvex functions, showing that this relaxed goal is generally hard to achieve with black-box access to function values and gradients, and discusses alternative approaches.
It is well-known that given a bounded, smooth nonconvex function, standard gradient-based methods can find $ε$-stationary points (where the gradient norm is less than $ε$) in $\mathcal{O}(1/ε^2)$ iterations. However, many important nonconvex optimization problems, such as those associated with training modern neural networks, are inherently not smooth, making these results inapplicable. Moreover, as recently pointed out in Zhang et al. [2020], it is generally impossible to provide finite-time guarantees for finding an $ε$-stationary point of nonsmooth functions. Perhaps the most natural relaxation of this is to find points which are near such $ε$-stationary points. In this paper, we show that even this relaxed goal is hard to obtain in general, given only black-box access to the function values and gradients. We also discuss the pros and cons of alternative approaches.