论文标题
线性收敛的无梯度方法，以最大程度地降临抛物线近似
Linearly Convergent Gradient-Free Methods for Minimization of Parabolic Approximation
论文作者
论文摘要
找到非凸功能的全球最小值是现代优化中的主要也是最困难的问题之一。在本文的第一部分中，我们考虑了一定类别的“良好”非凸功能，可以通过抛物线函数在上方和下方界定。我们表明，仅使用Zeroth-rorder Oracle，可以获得线性速度$ \ log \ left（\ frac {1} {\ varepsilon} \ right）$ $ right）$ right）$ y right）$。本文的第二部分以略有不同的方式查看了非凸问题。我们假设将二次函数最小化，但与此同时，我们可以访问带有噪声的零级甲骨文，并且该噪声与溶液的距离成正比。在文献中，处理这种无梯度方法的噪声假设是新的。我们表明，这里也可以实现收敛的线性速率。
Finding the global minimum of non-convex functions is one of the main and most difficult problems in modern optimization. In the first part of the paper, we consider a certain class of "good" non-convex functions that can be bounded above and below by a parabolic function. We show that using only the zeroth-order oracle, one can obtain the linear speed $\log \left(\frac{1}{\varepsilon}\right)$ of finding the global minimum on a cube. The second part of the paper looks at the nonconvex problem in a slightly different way. We assume that minimizing the quadratic function, but at the same time we have access to a zeroth-order oracle with noise and this noise is proportional to the distance to the solution. Dealing with such noise assumptions for gradient-free methods is new in the literature. We show that here it is also possible to achieve the linear rate of convergence.
