Exploratory distributions for convex functions

Abstract

Given a Lipschitz and convex function $f$ on a compact and convex domain in ${\mathbb{R}}^n$, we construct an exploratory distribution $\mu$ of $f$ in the following sense. Let $g$ be a Lipschitz and convex function on the same domain, such that either $g=f$, or alternatively the minimum of $g$ is $ϵ$ smaller than the minimum of $f$. Then $\mu$ is such that $\mathrm{poly}(n/ϵ)$ noisy evaluations of $g$ at i.i.d. points from $\mu$ suffices to determine with high probability whether $g=f$ or $g\ne f$. As an example of application for such exploratory distributions we show how to use them to estimate the minimax regret for adversarial bandit convex optimization.