Costly Zero Order Oracles

We study optimization with an approximate zero order oracle where there is a cost $c(\epsilon)$ associated with querying the oracle with $\epsilon$ accuracy. We consider the task of reconstructing a linear function: given a linear function $f : X \subseteq \R^d \rightarrow [-1,1]$ defined on a not-necessarily-convex set $X$, the goal is to reconstruct $\hat f$ such that $\vert{f(x) - \hat f(x)}\vert \leq \epsilon$ for all $x \in X$. We show that this can be done with cost $O(d \cdot c(\epsilon/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 $\epsilon$ requires $c(\epsilon) = \log(1/\epsilon)$. For this, our algorithm has cost $O(d \log(d/\epsilon))$ which matches the $\Omega(d \log(1/\epsilon))$ lower bound up to log factors.