Information-theoretic lower bounds for convex optimization with erroneous oracles
Information-theoretic lower bounds for convex optimization with erroneous oracles
复制标题
带有错误预言的凸优化的信息论下界
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
J. Vondrák
中科院分区：
文献类型：
--
作者：
Yaron Singer;J. Vondrák
我们考虑通过访问错误的零阶预言来优化凸函数和凹函数的问题。特别是，对于给定的函数 x → f (x)，当一个人可以访问返回值在 [f (x) - ∊, f (x) + ∊] 中的绝对误差预言机或返回值在 [(1 - ∊)f (x), (1 + ∊)f (x)] 中的相对误差预言机（对于某些 ∊ > 0）时，我们考虑优化。我们展示了最小化凸函数的赤裸信息论不可能性结果并在此模型中最大化多面体上的凹函数。
We consider the problem of optimizing convex and concave functions with access to an erroneous zeroth-order oracle. In particular, for a given function x → f (x) we consider optimization when one is given access to absolute error oracles that return values in [f (x) - ∊, f (x) + ∊] or relative error oracles that return value in [(1 - ∊)f (x), (1 + ∊)f (x)], for some ∊ > 0. We show stark information theoretic impossibility results for minimizing convex functions and maximizing concave functions over polytopes in this model.