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^{s c r i p t s c r i p t s t y l e T} x)

, where

g

is univariate and

a i n m a t h b b 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_{i} n f t y

-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.

Recommendations

Cites Work

Cited In (6)

Uses Software

This page was built for publication: The recovery of ridge functions on the hypercube suffers from the curse of dimensionality