Can We Find Near-Approximately-Stationary Points of Nonsmooth Nonconvex Functions?
Can We Find Near-Approximately-Stationary Points of Nonsmooth Nonconvex Functions?
复制标题
我们能找到非光滑非凸函数的近似驻点吗？
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Ohad Shamir
中科院分区：
文献类型：
--
作者：
Ohad Shamir
众所周知，给定一个有界的光滑非凸函数，标准的基于梯度的方法可以在$\mathcal{O}（1/\epsilon ^2）$迭代中找到$\mathcal $-稳定点（其中梯度范数小于$\mathcal{O}（1/\epsilon ^2）$）。然而，许多重要的非凸优化问题，如与训练现代神经网络相关的问题，本质上是不光滑的，使得这些结果不适用。此外，正如最近在Zhang et al. [2020]中指出的那样，通常不可能为找到非光滑函数的$\n $-稳定点提供有限时间保证。也许最自然的放松这是找到点附近的这些$\n $-平稳点。在本文中，我们表明，即使是这个宽松的目标是很难获得一般，只给黑盒访问的函数值和梯度。我们还讨论了替代方法的利弊。
It is well-known that given a bounded, smooth nonconvex function, standard gradient-based methods can find $\epsilon$-stationary points (where the gradient norm is less than $\epsilon$) in $\mathcal{O}(1/\epsilon^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 $\epsilon$-stationary point of nonsmooth functions. Perhaps the most natural relaxation of this is to find points which are near such $\epsilon$-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.
影响因子：
3
作者：
Davis, Damek;Drusvyatskiy, Dmitriy;Lee, Jason D.
通讯作者：
Lee, Jason D.
影响因子：
2.7
作者：
Drusvyatskiy, D.;Paquette, C.
通讯作者：
Paquette, C.