Approximate Function Evaluation via Multi-Armed Bandits
This addresses the challenge of sample-efficient function evaluation in high-dimensional noisy settings, which is incremental as it adapts existing multi-armed bandit methods to a specific optimization problem.
The paper tackles the problem of estimating a known smooth function at an unknown point with noisy component sampling, by developing an instance-adaptive algorithm that learns optimal sampling frequencies based on directional derivatives, achieving an ε-accurate estimate with probability at least 1-δ and showing dramatic gains in sample efficiency through numerical experiments.
We study the problem of estimating the value of a known smooth function $f$ at an unknown point $\boldsymbolμ \in \mathbb{R}^n$, where each component $μ_i$ can be sampled via a noisy oracle. Sampling more frequently components of $\boldsymbolμ$ corresponding to directions of the function with larger directional derivatives is more sample-efficient. However, as $\boldsymbolμ$ is unknown, the optimal sampling frequencies are also unknown. We design an instance-adaptive algorithm that learns to sample according to the importance of each coordinate, and with probability at least $1-δ$ returns an $ε$ accurate estimate of $f(\boldsymbolμ)$. We generalize our algorithm to adapt to heteroskedastic noise, and prove asymptotic optimality when $f$ is linear. We corroborate our theoretical results with numerical experiments, showing the dramatic gains afforded by adaptivity.