Deterministic computation of quantiles in a Lipschitz framework

Abstract

In this article, we focus on computing the quantiles of a random variable $f(X)$, where $X$ is a $[0,1{]}^d$-valued random variable, $d\in {\mathbb{N}}^{\ast }$, and $f:[0,1{]}^d\to \mathbb{R}$ is a deterministic Lipschitz function. We are particularly interested in scenarios where the cost of a single function evaluation is high, while the law of $X$ is assumed to be known. In this context, we propose a deterministic algorithm to compute deterministic lower and upper bounds for the quantile of $f(X)$ at a given level $\hat{I}\pm \in (0,1)$. With a fixed budget of $N$ function calls, we demonstrate that our algorithm achieves an exponential deterministic convergence rate for $d=1$ ($\mathcal{O}(\ddot{I}{}^N)$ with $\ddot{I}\in (0,1)$) and a polynomial deterministic convergence rate for $d>1$ ($\mathcal{O}(N^{-\frac{1}{d-1}})$) and show the optimality of those rates. Furthermore, we design two algorithms, depending on whether the Lipschitz constant of $f$ is known or unknown.