Timezone: »

Information-theoretic lower bounds for convex optimization with erroneous oracles
Yaron Singer · Jan Vondrak

Wed Dec 09 07:10 AM -- 07:35 AM (PST) @ Room 210 A
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 \to f(x)$ we consider optimization when one is given access to absolute error oracles that return values in [f(x) - \epsilon,f(x)+\epsilon] or relative error oracles that return value in [(1+\epsilon)f(x), (1 +\epsilon)f (x)], for some \epsilon larger than 0. We show stark information theoretic impossibility results for minimizing convex functions and maximizing concave functions over polytopes in this model.

Author Information

Yaron Singer (Harvard University)
Jan Vondrak (IBM Research)

More from the Same Authors