论文标题
我们可以找到非平滑非凸功能的近乎同一的点吗？
Can We Find Near-Approximately-Stationary Points of Nonsmooth Nonconvex Functions?
论文作者
论文摘要
众所周知，鉴于有限，平滑的非凸功能，基于标准梯度的方法可以找到$ \ Mathcal {o}（1/ε^2）$迭代中的$ε$ - 定位点（其中梯度标准小于$ε$）。但是，许多重要的非凸优化问题，例如与训练现代神经网络相关的问题，本质上并不顺利，这使得这些结果不可及。此外，正如最近在Zhang等人所指出的那样。 [2020]，通常不可能提供有限的时间保证来找到非平滑函数的$ε$ - 稳定点。也许最自然的放松是找到接近此类$ε$稳定点的点。在本文中，我们表明，通常只有黑框访问功能值和梯度，也很难获得这个轻松的目标。我们还讨论了替代方法的利弊。
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.
