论文标题
水平设置近似的样本复杂性
The sample complexity of level set approximation
论文作者
论文摘要
我们通过依次查询其值来研究近似未知函数的水平集的问题。我们介绍了一种称为“二合一”和“近似值”的算法系列，我们将水平设置近似问题减少到局部函数近似问题。然后，我们展示这种方法如何导致h {Ö} lder函数的速率最佳样本复杂性保证，并且我们研究了当额外的平滑度或其他结构假设成立时，这种速率如何提高。
We study the problem of approximating the level set of an unknown function by sequentially querying its values. We introduce a family of algorithms called Bisect and Approximate through which we reduce the level set approximation problem to a local function approximation problem. We then show how this approach leads to rate-optimal sample complexity guarantees for H{ö}lder functions, and we investigate how such rates improve when additional smoothness or other structural assumptions hold true.
