TY - JOUR
T1 - The recovery of ridge functions on the hypercube suffers from the curse of dimensionality
AU - Doerr, Benjamin
AU - Mayer, Sebastian
N1 - Publisher Copyright:
© 2020 Elsevier Inc.
PY - 2021/4/1
Y1 - 2021/4/1
N2 - A multivariate ridge function is a function of the form f(x)=g(aTx), where g is univariate and a∈Rd. 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∞-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.
AB - A multivariate ridge function is a function of the form f(x)=g(aTx), where g is univariate and a∈Rd. 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∞-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.
KW - High-dimensional function approximation
KW - Information-based complexity
KW - Lower bounds
KW - Randomized algorithms
KW - Ridge functions
U2 - 10.1016/j.jco.2020.101521
DO - 10.1016/j.jco.2020.101521
M3 - Article
AN - SCOPUS:85094573648
SN - 0885-064X
VL - 63
JO - Journal of Complexity
JF - Journal of Complexity
M1 - 101521
ER -