Recovery of regular ridge functions on the ball

Abstract

We consider the problem of the uniform (in $L_{\infty }$) recovery of ridge functions $f(x)=\phi (⟨a,x⟩)$, $x\in B_2^n$, using noisy evaluations $y_1\approx f(x^1),\dots ,y_N\approx f(x^N)$. It is known that for classes of functions $\phi$ of finite smoothness the problem suffers from the curse of dimensionality: in order to provide good accuracy for the recovery it is necessary to make exponential number of evaluations. We prove that if $\phi$ is analytic in a neighborhood of $[-1,1]$ and the noise is very small, $\epsilon \le \exp (-c{\log }^{2}n)$, then there is an efficient algorithm that recovers $f$ with good accuracy using $O(n{\log }^{2}n)$ function evaluations.

References in corpus (2)

• Optimal rates and adaptation in the single-index model using aggregation
• The recovery of ridge functions on the hypercube suffers from the curse of dimensionality