Information-theoretic lower bounds for convex optimization with erroneous oracles

Abstract

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.