Adaptive approximation of monotone functions - ANITI - Artificial and Natural Intelligence Toulouse Institute Access content directly
Preprints, Working Papers, ... Year : 2023

Adaptive approximation of monotone functions


We study the classical problem of approximating a non-decreasing function $f: \mathcal{X} \to \mathcal{Y}$ in $L^p(\mu)$ norm by sequentially querying its values, for known compact real intervals $\mathcal{X}$, $\mathcal{Y}$ and a known probability measure $\mu$ on $\mathcal{X}$. For any function~$f$ we characterize the minimum number of evaluations of $f$ that algorithms need to guarantee an approximation $\hat{f}$ with an $L^p(\mu)$ error below $\epsilon$ after stopping. Unlike worst-case results that hold uniformly over all $f$, our complexity measure is dependent on each specific function $f$. To address this problem, we introduce GreedyBox, a generalization of an algorithm originally proposed by Novak (1992) for numerical integration. We prove that GreedyBox achieves an optimal sample complexity for any function $f$, up to logarithmic factors. Additionally, we uncover results regarding piecewise-smooth functions. Perhaps as expected, the $L^p(\mu)$ error of GreedyBox decreases much faster for piecewise-$C^2$ functions than predicted by the algorithm (without any knowledge on the smoothness of $f$). A simple modification even achieves optimal minimax approximation rates for such functions, which we compute explicitly. In particular, our findings highlight multiple performance gaps between adaptive and non-adaptive algorithms, smooth and piecewise-smooth functions, as well as monotone or non-monotone functions. Finally, we provide numerical experiments to support our theoretical results.
Fichier principal
Vignette du fichier
main.pdf (3.46 Mo) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

hal-04203136 , version 1 (13-09-2023)





Pierre Gaillard, Sébastien Gerchinovitz, Étienne de Montbrun. Adaptive approximation of monotone functions. 2023. ⟨hal-04203136⟩
45 View
13 Download



Gmail Facebook X LinkedIn More