论文标题
随机信任区域和直接搜索方法：较弱的尾巴结合条件和样本尺寸降低
Stochastic trust-region and direct-search methods: A weak tail bound condition and reduced sample sizing
论文作者
论文摘要
使用尾部边界，我们引入了一种新的概率条件，以进行随机无衍生物优化的功能估计，从而导致样品数量减少并减少算法分析。此外，我们开发了简单的随机直接搜索和信任区域方法，以优化潜在的非平滑函数，其值只能通过随机观察来估计。为了接受试验点，这些算法需要估计的函数值，以产生足够的减小，以大于1个算法的步骤的功率来测量。 我们的新尾巴条件精确地施加在用于实现如此充分减少的还原估计上。这种条件使我们可以选择用于减少迭代所需的样本数量的足够减少的步进功率。在以前的作品中，这种类型的算法的每种迭代$ k $在每种迭代中所需的样本数为$ o（δ_{k}^{ - 4}）$，其中$Δ_K$是sptepize或Trust-trust-region radius。但是，使用新的尾巴结合条件，在噪音的轻度假设下，可以证明，这样的许多样品仅为$ o（δ_k^{ - 2 - 2 - \ varepsilon}）$，其中$ \ varepsilon> 0 $可以通过选择足够的步骤来任意地将足够的步骤缩小到足够的步骤中，以使足够的步骤缩小降低测试的降低测试的降低降低，以降低测试的降低，以任意$ 1 $ 1 $ 1 $ 1 $ 1 $ 1 $ 1 $ 1 $ 1 $ 1 $ 1 $ 1 $ 1 $ 1 $ 1 $。随机直接搜索和信任区域算法的全局收敛属性是在新的尾巴结合条件下建立的。
Using tail bounds, we introduce a new probabilistic condition for function estimation in stochastic derivative-free optimization which leads to a reduction in the number of samples and eases algorithmic analyses. Moreover, we develop simple stochastic direct-search and trust-region methods for the optimization of a potentially non-smooth function whose values can only be estimated via stochastic observations. For trial points to be accepted, these algorithms require the estimated function values to yield a sufficient decrease measured in terms of a power larger than 1 of the algoritmic stepsize. Our new tail bound condition is precisely imposed on the reduction estimate used to achieve such a sufficient decrease. This condition allows us to select the stepsize power used for sufficient decrease in such a way to reduce the number of samples needed per iteration. In previous works, the number of samples necessary for global convergence at every iteration $k$ of this type of algorithms was $O(Δ_{k}^{-4})$, where $Δ_k$ is the stepsize or trust-region radius. However, using the new tail bound condition, and under mild assumptions on the noise, one can prove that such a number of samples is only $O(Δ_k^{-2 - \varepsilon})$, where $\varepsilon > 0$ can be made arbitrarily small by selecting the power of the stepsize in the sufficient decrease test arbitrarily close to $1$. The global convergence properties of the stochastic direct-search and trust-region algorithms are established under the new tail bound condition.
