First- and second-order high probability complexity bounds for trust-region methods with noisy oracles
First- and second-order high probability complexity bounds for trust-region methods with noisy oracles
复制标题
DOI：
10.1007/s10107-023-01999-5
复制
发表时间：
2022-05
影响因子：
2.7
通讯作者：
Liyuan Cao;A. Berahas;K. Scheinberg
中科院分区：
文献类型：
--
作者：
Liyuan Cao;A. Berahas;K. Scheinberg
在这篇文章中，我们给出了一种改进的信赖域方法的收敛保证，该信赖域方法是为最小化目标函数而设计的，其值、梯度和Hessian估计都是在有噪声的情况下计算的。这些估计是由通用随机预言产生的，没有假设是无偏的或一致的。我们介绍了这些预言，并表明它们比以往文献中关于随机信赖域方法的随机预言更具一般性和更宽松的假设。我们的方法利用一个宽松的步长接受准则和谨慎的信赖域半径更新策略，使得我们可以得到收敛到满足近似一阶和二阶最优性条件的点的迭代复杂度的指数衰减尾界。最后，给出了两组数值结果。我们首先在一个具有对抗性的零阶和一阶先知的例子上探索我们的理论结果的紧密性。然后，我们研究了改进的信赖域算法在标准噪声无导数优化问题上的性能。
In this paper, we present convergence guarantees for a modified trust-region method designed for minimizing objective functions whose value and gradient and Hessian estimates are computed with noise. These estimates are produced by generic stochastic oracles, which are not assumed to be unbiased or consistent. We introduce these oracles and show that they are more general and have more relaxed assumptions than the stochastic oracles used in prior literature on stochastic trust-region methods. Our method utilizes a relaxed step acceptance criterion and a cautious trust-region radius updating strategy which allows us to derive exponentially decaying tail bounds on the iteration complexity for convergence to points that satisfy approximate first- and second-order optimality conditions. Finally, we present two sets of numerical results. We first explore the tightness of our theoretical results on an example with adversarial zeroth- and first-order oracles. We then investigate the performance of the modified trust-region algorithm on standard noisy derivative-free optimization problems.