Exploratory distributions for convex functions

  • Sébastien Bubeck

    Microsoft Research, Redmond, USA
  • Ronen Eldan

    Weizmann Institute of Science, Rehovot, Israel


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–100

DOI 10.4171/MSL/1-1-3