# Exploratory distributions for convex functions

### Sébastien Bubeck

Microsoft Research, Redmond, USA### Ronen Eldan

Weizmann Institute of Science, Rehovot, Israel

## 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 $\epsilon$ smaller than the minimum of $f$. Then $\mu$ is such that $\mathrm{poly}(n/\epsilon)$ noisy evaluations of $g$ at i.i.d. points from $\mu$ suffices to determine with high probability whether $g=f$ or $g \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