Deterministic computation of quantiles in a Lipschitz framework

In this article, our focus lies on computing the quantiles of a random variable $f(X)$, where X is a [0,1]ᵈ-valued random variable, d ∈ N^, and f:[0,1]ᵈ→ R is a deterministic Lipschitz function. We are particularly interested in scenarios where the cost of a single function call is high, while assuming the law of X is known. In this context, we propose a deterministic algorithm to obtain exact deterministic lower and upper bounds for the quantile of $f(X)$ at a given level α ∈ (0,1). With a fixed budget of N function calls, we demonstrate that our algorithm achieves exponential convergence rate for $d=1$ (~ ρN with ρ ∈ (0,1)) and polynomial convergence rate for $d>1$ (~ N-1/d-1) and show the optimality of those rates within the class of deterministic algorithms. Furthermore, we design two algorithms based on whether the Lipschitz constant of f is known or unknown.