JournalsmslVol. 1, No. 1pp. 73–100

Exploratory distributions for convex functions

  • Sébastien Bubeck

    Microsoft Research, Redmond, USA
  • Ronen Eldan

    Weizmann Institute of Science, Rehovot, Israel
Exploratory distributions for convex functions cover
Download PDF

A subscription is required to access this article.

Abstract

Given a Lipschitz and convex function ff on a compact and convex domain in Rn\mathbb R^n, we construct an exploratory distribution μ\mu of ff in the following sense. Let gg be a Lipschitz and convex function on the same domain, such that either g=fg=f, or alternatively the minimum of gg is ϵ\epsilon smaller than the minimum of ff. Then μ\mu is such that poly(n/ϵ)\mathrm{poly}(n/\epsilon) noisy evaluations of gg at i.i.d. points from μ\mu suffices to determine with high probability whether g=fg=f or gfg \neq 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.

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