Costly Zero Order Oracles

We study optimization with an approximate zero order oracle where there is a cost c() associated with querying the oracle with  accuracy. We consider the task of reconstructing a linear function: given a linear function f : X ⊆ R d → [−1, 1] defined on a not-necessarily-convex set X, the goal is to reconstruct ˆf such that |f(x) − ˆf(x)| ≤  for all x ∈ X. We show that this can be done with cost O(d · c(/d)). The algorithm is based on a (poly-time computable) John-like theorem for simplices instead of ellipsoids, which may be of independent interest. This question is motivated by optimization with threshold queries, which are common in economic applications such as pricing. With threshold queries, approximating a number up to precision  requires c() = log(1/). For this, our algorithm has cost O(d log(d/)) which matches the Ω(d log(1/)) lower bound up to log factors

• Machine Intelligence