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) null,f (x) + null ] or relative error oracles that return value in [(1 null) f ( x), (1 + null)f ( x)], for some null > 0. We show stark information theoretic impossibility results for minimizing convex functions and maximizing concave functions over polytopes in this model.