A Theoretical and Empirical Comparison of Gradient Approximations in Derivative-Free Optimization
A Theoretical and Empirical Comparison of Gradient Approximations in Derivative-Free Optimization
复制标题
DOI：
10.1007/s10208-021-09513-z
复制
发表时间：
2019-05
影响因子：
3
通讯作者：
A. Berahas;Liyuan Cao;K. Choromanski;K. Scheinberg
中科院分区：
文献类型：
--
作者：
A. Berahas;Liyuan Cao;K. Choromanski;K. Scheinberg
在本文中，我们分析了几种方法来逼近噪声函数的梯度仅使用函数值。这些方法包括有限差分、线性插值、高斯平滑和球面平滑。这些方法在采样函数的数量、采样点的选择以及导出梯度近似的方式上有所不同。对于每种方法，我们推导出的样本数和采样半径，保证良好的收敛性能的线搜索或固定步长下降法的界限。为此，我们使用Berahas等人的结果。（带噪声的通用线搜索算法的全局收敛率分析，arXiv：1910.04055，2019）并展示了每种方法如何满足充分条件，可能只有在每次迭代时具有足够大的概率，就像高斯平滑和球面平滑一样。最后，我们提出的数值结果评估的梯度近似的质量，以及它们的性能与线搜索导数自由优化算法。
In this paper, we analyze several methods for approximating gradients of noisy functions using only function values. These methods include finite differences, linear interpolation, Gaussian smoothing, and smoothing on a sphere. The methods differ in the number of functions sampled, the choice of the sample points, and the way in which the gradient approximations are derived. For each method, we derive bounds on the number of samples and the sampling radius which guarantee favorable convergence properties for a line search or fixed step size descent method. To this end, we use the results in Berahas et al. (Global convergence rate analysis of a generic line search algorithm with noise, arXiv:1910.04055, 2019) and show how each method can satisfy the sufficient conditions, possibly only with some sufficiently large probability at each iteration, as happens to be the case with Gaussian smoothing and smoothing on a sphere. Finally, we present numerical results evaluating the quality of the gradient approximations as well as their performance in conjunction with a line search derivative-free optimization algorithm.