论文标题
单变量零订单预算凸优化的近距离算法优化
A Near-Optimal Algorithm for Univariate Zeroth-Order Budget Convex Optimization
论文作者
论文摘要
本文通过顺序查询其值来最大程度地减少单变量凸功能的问题的自然概括。在每个时间段$ t $中，优化器可以在查询点上投资预算$ b_t $，以获取其选择的$ x_t $，以获取$ f $ in $ x_t $的模糊评估，其准确性取决于$ x_t $投资的预算金额。此设置是由目标最小化只能通过冗长或昂贵的计算来确定的目标的最小化。我们设计了一种称为二元搜索的任何无时间参数算法，我们证明了近乎最佳的优化错误保证。作为我们分析的副产品，我们表明，在误差范围内对全球Lipschitz常数的经典依赖性是预算粒度的伪像。最后，我们通过数值模拟说明了我们的理论发现。
This paper studies a natural generalization of the problem of minimizing a univariate convex function $f$ by querying its values sequentially. At each time-step $t$, the optimizer can invest a budget $b_t$ in a query point $X_t$ of their choice to obtain a fuzzy evaluation of $f$ at $X_t$ whose accuracy depends on the amount of budget invested in $X_t$ across times. This setting is motivated by the minimization of objectives whose values can only be determined approximately through lengthy or expensive computations. We design an any-time parameter-free algorithm called Dyadic Search, for which we prove near-optimal optimization error guarantees. As a byproduct of our analysis, we show that the classical dependence on the global Lipschitz constant in the error bounds is an artifact of the granularity of the budget. Finally, we illustrate our theoretical findings with numerical simulations.
