Near-Optimal Methods for Minimizing Star-Convex Functions and Beyond
Near-Optimal Methods for Minimizing Star-Convex Functions and Beyond
复制标题
DOI：
--
复制
发表时间：
2019-06
期刊：
影响因子：
--
通讯作者：
Oliver Hinder;Aaron Sidford;N. Sohoni
中科院分区：
文献类型：
--
作者：
Oliver Hinder;Aaron Sidford;N. Sohoni
在本文中，我们提供了近乎最佳的加速一阶方法，以最大程度地减少一类平滑的非凸函数，这些函数在所有线路上都通过最小化的方式严格地是单峰。我们称之为平滑的Quasar-convex函数类别的此功能类是由常数$ \ gamma \ in（0,1] $中的参数，其中$ \ gamma = 1 $包含平滑凸和star-convex的类别函数，$ \ gamma $的较小值表明该功能可以是“更多的非convex”。用$ o（\ gamma^{ - 1} \ epsilon^{ - 1/2} \ log（\ gamma^{ - 1} \ epsilon^{ - 1}））$还可以在最坏的情况下，在任何确定的一阶方法所需的梯度评估数量上，在$ \ omega（\ gamma^{ - 1} \ epsilon^{ - 1/2}）$的下限最多可以达到对数因素，没有确定性的一阶算法可以改善我们的。
In this paper, we provide near-optimal accelerated first-order methods for minimizing a broad class of smooth nonconvex functions that are strictly unimodal on all lines through a minimizer. This function class, which we call the class of smooth quasar-convex functions, is parameterized by a constant $\gamma \in (0,1]$, where $\gamma = 1$ encompasses the classes of smooth convex and star-convex functions, and smaller values of $\gamma$ indicate that the function can be "more nonconvex." We develop a variant of accelerated gradient descent that computes an $\epsilon$-approximate minimizer of a smooth $\gamma$-quasar-convex function with at most $O(\gamma^{-1} \epsilon^{-1/2} \log(\gamma^{-1} \epsilon^{-1}))$ total function and gradient evaluations. We also derive a lower bound of $\Omega(\gamma^{-1} \epsilon^{-1/2})$ on the number of gradient evaluations required by any deterministic first-order method in the worst case, showing that, up to a logarithmic factor, no deterministic first-order algorithm can improve upon ours.