Information-theoretic lower bounds for convex optimization with erroneous oracles

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.