# 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 $R_{n}$, we construct an *exploratory distribution* $μ$ 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 $μ$ is such that $poly(n/ϵ)$ noisy evaluations of $g$ at i.i.d. points from $μ$ suffices to determine with high probability whether $g=f$ or $g=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