Given a Lipschitz and convex function on a compact and convex domain in , we construct an exploratory distribution of in the following sense. Let be a Lipschitz and convex function on the same domain, such that either , or alternatively the minimum of is smaller than the minimum of . Then is such that noisy evaluations of at i.i.d. points from suffices to determine with high probability whether or . 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.
Cite this article
Sébastien Bubeck, Ronen Eldan, Exploratory distributions for convex functions. Math. Stat. Learn. 1 (2018), no. 1, pp. 73–100DOI 10.4171/MSL/1-1-3