论文标题
具有嘈杂orac的信任区域方法的一阶和二阶高概率复杂性界限
First- and Second-Order High Probability Complexity Bounds for Trust-Region Methods with Noisy Oracles
论文作者
论文摘要
在本文中，我们提供了一种经过修改的信任区域方法的融合保证，该方法旨在最大程度地减少其价值，梯度和黑森估计的目标函数，并使用噪声计算。这些估计值是由通用随机甲壳产生的，这些牙齿并非被认为是公正或一致的。我们介绍了这些口腔，并表明它们比先前关于随机信任区域的文献中使用的随机甲壳更一般，并且具有更轻松的假设。我们的方法利用了放松的步骤接受标准和谨慎的信任区域半径更新策略，该策略使我们能够在迭代复杂度上呈指数衰减的尾巴范围，从而使收敛到满足近似一阶和二阶最优性条件的点。最后，我们提出了两组数值结果。我们首先在一个以对抗性零和一阶甲壳为例的示例中探索了我们的理论结果的紧密度。然后，我们研究了修改后的信任区域算法在标准噪声无衍生物的优化问题上的性能。
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.
