The recovery of ridge functions on the hypercube suffers from the curse of dimensionality
Provides a theoretical lower bound for a fundamental problem in approximation theory, showing inherent difficulty for general ridge functions.
The paper proves that recovering ridge functions on the hypercube suffers from the curse of dimensionality in the L∞ norm, even with randomized algorithms, unless the coefficient vector has a limited number of dominant components and the profile is sufficiently regular.
A multivariate ridge function is a function of the form $f(x) = g(a^{\scriptscriptstyle 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.