Hier finden Sie wissenschaftliche Publikationen aus den Fraunhofer-Instituten.

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

: Doerr, B.; Mayer, S.


Journal of complexity 63 (2020), Art. 101521
ISSN: 0885-064X
Journal Article
Fraunhofer SCAI ()

A multivariate ridge function is a function of the form f(x) = g(aTx), where g is univariate and a E 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 L8-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.