Abstract:
We study optimization with an approximate zero order oracle where there is a\ncost $c(\epsilon)$ associated with querying the oracle with $\epsilon$ accuracy.\nWe consider the task of reconstructing a linear function: given a \nlinear function $f : X \subseteq \mathbb{R}^d \rightarrow [-1,1]$ defined on a\nnot-necessarily-convex set $X$, the goal is to reconstruct $\hat f$ such that\n$\vert{f(x) - \hat f(x)}\vert \leq \epsilon$ for all $x \in X$. We show that this can\nbe done with cost $O(d \cdot c(\epsilon/d))$. \nThe algorithm is based on a (poly-time\ncomputable) John-like theorem for simplices instead of ellipsoids, which may be\nof independent interest.\n\nThis question is motivated by optimization with threshold queries, which are\ncommon in economic applications such as pricing. With threshold queries,\napproximating a number up to precision $\epsilon$ requires $c(\epsilon) =\n\log(1/\epsilon)$. For this, our algorithm has cost $O(d \log(d/\epsilon))$\nwhich matches the $\Omega(d \log(1/\epsilon))$ lower bound up to log factors.
