Costly Zero Order Oracles
Abstract
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
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
