论文标题
对全球Lipschitz优化的Piyavskii-Shubert算法的遗憾分析
Regret analysis of the Piyavskii-Shubert algorithm for global Lipschitz optimization
论文作者
论文摘要
我们考虑通过顺序查询其（可能扰动的）值，在紧凑型结构域上最大化非concave Lipschitz多元函数的问题。我们研究了最初由Piyavskii和Shubert设计的天然算法，1972年，我们证明了有关达到或证明给定优化准确性所需功能的评估次数的新范围。我们的分析使用了强烈的优化观点，并通过界定评估的数量来证明给定准确性的数量几乎是包装数字，从而解决了Hansen等人（1991）的开放问题。
We consider the problem of maximizing a non-concave Lipschitz multivariate function over a compact domain by sequentially querying its (possibly perturbed) values. We study a natural algorithm designed originally by Piyavskii and Shubert in 1972, for which we prove new bounds on the number of evaluations of the function needed to reach or certify a given optimization accuracy. Our analysis uses a bandit-optimization viewpoint and solves an open problem from Hansen et al.\ (1991) by bounding the number of evaluations to certify a given accuracy with a near-optimal sum of packing numbers.
