Google Research

Costly Zero Order Oracles

COLT'20 (2020)


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

Research Areas

Learn more about how we do research

We maintain a portfolio of research projects, providing individuals and teams the freedom to emphasize specific types of work