In recent years, the success of deep learning has inspired many researchers to study the optimization of general smooth non-convex functions. However, recent works have established pessimistic worst-case complexities for this class functions, which is in stark contrast with their superior performance in real-world applications (e.g. training deep neural networks). On the other hand, it is found that many popular non-convex optimization problems enjoy certain structured properties which bear some similarities to convexity. In this paper, we study the class of \textit{quasar-convex functions} to close the gap between theory and practice. We study the convergence of first order methods in a variety of different settings and under different optimality criterions. We prove complexity upper bounds that are similar to standard results established for convex functions and much better that state-of-the-art convergence rates of non-convex functions. Overall, this paper suggests that \textit{quasar-convexity} allows efficient optimization procedures, and we are looking forward to seeing more problems that demonstrate similar properties in practice.
翻译:近些年来,深层学习的成功激励了许多研究人员研究如何优化一般平滑的非康维克斯功能。然而,最近的工作为这一类功能确立了悲观的最坏情况复杂性,这与其在现实世界应用中的优异性表现形成鲜明对比(例如,培训深神经网络 ) 。 另一方面,人们发现,许多受欢迎的非康维克斯优化问题具有某些结构化特性,与共性有某些相似之处。在本论文中,我们研究了\ textit{quasar-convex函数的类别,以缩小理论与实践之间的差距。我们研究了不同场合和不同最佳性标准下第一级方法的趋同性。我们证明,复杂性的上限与为共通性功能设定的标准结果相似,而且远比非康维克斯功能的状态一致率要好得多。总体而言,本文表明, ktextit{quasar-convexity} 允许高效的优化程序,我们期待看到更多在实践中显示类似特性的问题。