Algorithms and matching lower bounds for approximately-convex optimization
Algorithms and matching lower bounds for approximately-convex optimization
复制标题
近似凸优化的算法和匹配下界
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Yuanzhi Li
中科院分区：
文献类型：
--
作者：
Andrej Risteski;Yuanzhi Li
近年来，在实际应用中，越来越多的应用需要优化非凸目标，如训练神经网络、学习图模型、最大似然估计等。虽然简单的算法，如梯度下降，很少修改，往往工作得很好，理论理解是非常薄弱的。
我们考虑可能是最自然的一类非凸函数，其中人们可以希望获得可证明的保证：“近似凸”的函数，即存在凸函数f使得对所有x，|f（x）- f（x）|对于固定值Δ，≤ Δ。然后我们想最小化f，即输出一个点x，使得f（x）≤ minx f（x）+ e。
很自然地推测，对于固定的e，对于较大的Δ，问题变得更难，然而，e和Δ的确切依赖性是未知的。在本文中，我们显着改善了已知的下限Δ作为一个函数的e和算法匹配的自然类凸体的这个下限。更准确地说，我们确定一个函数T：n + -n+，使得当Δ = O（T（e））时，我们可以给出一个算法，该算法输出一个点x，使得f（x）≤ minx f（x）+ e在时间poly（d，1/e）内。另一方面，当Δ = Ω（T（e））时，我们还证明了一个信息论下界，即任何输出这样一个x的算法必须使用f的求值的超多项式数。
In recent years, a rapidly increasing number of applications in practice requires optimizing non-convex objectives, like training neural networks, learning graphical models, maximum likelihood estimation. Though simple heuristics such as gradient descent with very few modifications tend to work well, theoretical understanding is very weak.
We consider possibly the most natural class of non-convex functions where one could hope to obtain provable guarantees: functions that are "approximately convex", i.e. functions f : ℝd → ℝ for which there exists a convex function f such that for all x, |f (x) - f(x)| ≤ Δ for a fixed value Δ. We then want to minimize f, i.e. output a point x such that f(x) ≤ minx f(x) + e.
It is quite natural to conjecture that for fixed e, the problem gets harder for larger Δ, however, the exact dependency of e and Δ is not known. In this paper, we significantly improve the known lower bound on Δ as a function of e and an algorithm matching this lower bound for a natural class of convex bodies. More precisely, we identify a function T : ℝ+ - ℝ+ such that when Δ = O(T(e)), we can give an algorithm that outputs a point x such that f (x) ≤ minx f (x) + e within time poly (d, 1/e). On the other hand, when Δ = Ω(T(e)), we also prove an information theoretic lower bound that any algorithm that outputs such a x must use super polynomial number of evaluations of f.