Generalized-Smooth Nonconvex Optimization is As Efficient As Smooth Nonconvex Optimization
Generalized-Smooth Nonconvex Optimization is As Efficient As Smooth Nonconvex Optimization
复制标题
DOI：
--
复制
发表时间：
2023-03
期刊：
影响因子：
--
通讯作者：
Ziyi Chen;Yi Zhou;Yingbin Liang;Zhaosong Lu
中科院分区：
文献类型：
--
作者：
Ziyi Chen;Yi Zhou;Yingbin Liang;Zhaosong Lu
各种基于梯度的优化算法已经被开发用于光滑非凸优化。然而，许多非凸机器学习问题不属于光滑函数类，因此现有的算法是次优的。相反，这些问题已被证明满足某些广义光滑条件，这在现有的文献中还没有得到很好的理解。在本文中，我们提出了$\alpha$-对称广义光滑性的概念，它扩展了已有的概念，并涵盖了许多重要的函数，如高阶多项式和指数函数.我们研究了这类函数的基本性质，并建立了下降引理。然后，为了解决这类非凸问题，我们设计了一个特殊的确定性归一化梯度下降算法，该算法实现了最优迭代复杂度$\mathcal{O}（\displaystyle\mathcal{O}（\mathcal ^{-2}）$，并且证明了流行的SPIDER方差缩减算法在随机环境下实现了最优样本复杂度$\mathcal{O}（\displaystyle\mathcal ^{-3}）$。我们的结果表明，解决广义光滑非凸问题是有效的解决光滑非凸问题。
Various optimal gradient-based algorithms have been developed for smooth nonconvex optimization. However, many nonconvex machine learning problems do not belong to the class of smooth functions and therefore the existing algorithms are sub-optimal. Instead, these problems have been shown to satisfy certain generalized-smooth conditions, which have not been well understood in the existing literature. In this paper, we propose a notion of $\alpha$-symmetric generalized-smoothness that extends the existing notions and covers many important functions such as high-order polynomials and exponential functions. We study the fundamental properties and establish descent lemmas for the functions in this class. Then, to solve such a large class of nonconvex problems, we design a special deterministic normalized gradient descent algorithm that achieves the optimal iteration complexity $\mathcal{O}(\epsilon^{-2})$, and also prove that the popular SPIDER variance reduction algorithm achieves the optimal sample complexity $\mathcal{O}(\epsilon^{-3})$ in the stochastic setting. Our results show that solving generalized-smooth nonconvex problems is as efficient as solving smooth nonconvex problems.