The recovery of ridge functions on the hypercube suffers from the curse of dimensionality

Abstract

A multivariate ridge function is a function of the form $f(x)=g(a^{T}x)$, where $g$ is univariate and $a\in {\mathbb{R}}^d$. We show that the recovery of an unknown ridge function defined on the hypercube $[-1,1{]}^d$ with Lipschitz-regular profile $g$ suffers from the curse of dimensionality when the recovery error is measured in the $L_{\infty }$-norm, even if we allow randomized algorithms. If a limited number of components of $a$ is substantially larger than the others, then the curse of dimensionality is not present and the problem is weakly tractable provided the profile $g$ is sufficiently regular.