Global Convergence Rate Analysis of a Generic Line Search Algorithm with Noise
Global Convergence Rate Analysis of a Generic Line Search Algorithm with Noise
复制标题
DOI：
10.1137/19m1291832
复制
发表时间：
2019-10
期刊：
影响因子：
--
通讯作者：
A. Berahas;Liyuan Cao;K. Scheinberg
中科院分区：
文献类型：
--
作者：
A. Berahas;Liyuan Cao;K. Scheinberg
本文研究了一种改进的线搜索方法的收敛性分析，该方法适用于具有噪声且梯度估计不精确且可能是随机的目标函数。假设噪声的绝对值有界，不作任何附加假设。我们扩展了基于随机方法的框架[Cartis和Scheinberg， 2018]，该框架旨在提供对具有精确函数值和随机梯度的标准线搜索方法的分析，以用于噪声函数的情况。我们在梯度上引入了一个条件，当每次迭代满足足够大的概率时，保证了线搜索方法的收敛性。导出了凸函数、强凸函数和非凸函数的期望复杂度界。
In this paper, we develop convergence analysis of a modified line search method for objective functions whose value is computed with noise and whose gradient estimates are inexact and possibly random. The noise is assumed to be bounded in absolute value without any additional assumptions. We extend the framework based on stochastic methods from [Cartis and Scheinberg, 2018] which was developed to provide analysis of a standard line search method with exact function values and random gradients to the case of noisy function. We introduce a condition on the gradient which when satisfied with some sufficiently large probability at each iteration, guarantees convergence properties of the line search method. We derive expected complexity bounds for convex, strongly convex and nonconvex functions.