High Probability Complexity Bounds for Line Search Based on Stochastic Oracles
High Probability Complexity Bounds for Line Search Based on Stochastic Oracles
复制标题
DOI：
--
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Billy Jin;K. Scheinberg;Miao Xie
中科院分区：
文献类型：
--
作者：
Billy Jin;K. Scheinberg;Miao Xie
我们考虑了一种随机设置下的连续优化的线搜索方法，其中函数值和梯度只能通过不精确的概率零阶和一阶预测来获得。这些预言捕捉多种标准设置，包括预期损失最小化和零阶优化。此外，我们的框架是非常通用的，允许函数和梯度估计是有偏差的。所提出的算法易于描述，易于实现，并且以类似于标准确定性线搜索使用精确函数和梯度值的方式使用这些预言器。在相当一般的oracle条件下，当应用于非凸光滑函数时，我们推导出算法迭代复杂度的高概率尾界。这些结果比其他现有的随机线搜索方法更强，适用于更一般的情况。
We consider a line-search method for continuous optimization under a stochastic setting where the function values and gradients are available only through inexact probabilistic zeroth and first-order oracles. These oracles capture multiple standard settings including expected loss minimization and zeroth-order optimization. Moreover, our framework is very general and allows the function and gradient estimates to be biased. The proposed algorithm is simple to describe, easy to implement, and uses these oracles in a similar way as the standard deterministic line search uses exact function and gradient values. Under fairly general conditions on the oracles, we derive a high probability tail bound on the iteration complexity of the algorithm when applied to non-convex smooth functions. These results are stronger than those for other existing stochastic line search methods and apply in more general settings.