Exploratory distributions for convex functions (Q1737974)

Let \(\mathcal{K}\) be a convex body in \(\mathbb{R}^n\) of diameter at most \(1\). Let \(f:\mathcal{K}\to[0,\infty)\) be convex and 1-Lipschitz, and let \(\varepsilon>0\). The main result of the paper establishes that there exists a probability measure \(\mu\) on \(\mathcal{K}\) such that for every \(\alpha\in\mathcal{K}\) and for every convex and 1-Lipschitz function \(g:\mathcal{K}\to\mathbb{R}\) satisfying \(g(\alpha)<-\varepsilon\), the \(\mu\)-measure of the set of all \(x\in\mathcal{K}\) such that \(|f(x)-g(x)|\) is greater than \(c\max(\varepsilon,f(x))n^{-7.5}/\log(1+n/\varepsilon)\) is at least \(cn^{-3}/\log(1+n/\varepsilon)\). The result is applied to estimate the minimax regret for adversarial bandit convex optimisation.