Deterministic computation of quantiles in a Lipschitz framework
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929565924851712 |
|---|---|
| author | Gu, Yurun Rey, Clément |
| author_facet | Gu, Yurun Rey, Clément |
| contents | 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 $α\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}( ρ^N)$ with $ρ\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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_10638 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Deterministic computation of quantiles in a Lipschitz framework Gu, Yurun Rey, Clément Probability 65C20, 62E17, 65D15, 68W25, 68Q25 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 $α\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}( ρ^N)$ with $ρ\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. |
| title | Deterministic computation of quantiles in a Lipschitz framework |
| topic | Probability 65C20, 62E17, 65D15, 68W25, 68Q25 |
| url | https://arxiv.org/abs/2405.10638 |