The article is devoted to ridge functions, i.e., functions \(f\) of several variables, such that there is a direction vector \(a\) along which \(f\) may vary; along lines perpendicular to \(a\), the function is constant. In other words, \[ f\left(x\right)=g\left(a\cdot x\right),\quad x\in{\mathbb R}^d, \] where \(g\) is a univariate function called the profile.
Despite the fact that being a ridge functions is a serious restriction, this is a frequent assumption in statistics. Furthermore, approximation by ridge function has also been investigated and had applications.
The problem of tractability is one of the main points of interest throughout the article.
The authors investigate entropy numbers to show how “large” the ridge function classes are, to quantify the compactness of the ridge function classes in \(L_\infty\). It is shown that they are essentially as compact as the class of univariate Lipschitz functions.
The authors pay special attention to determination of the complexity of approximating ridge functions when the only available information is a limited amount of function values. The assumptions are the following: The domain of the ridge functions is \(d\)-dimensional Euclidean unit ball; the profiles are Lipschitz of order \(\alpha>0\) (including infinite smoothness \(\alpha=\infty\)); the ridge vectors are in an \(l_p^d\)-ball with \(0<p\leq 2\). In addition, the case when \(\left|g'\left(0\right)\right|\geq k\) for all admissible profiles \(g\) and some prescribed \(0<k\leq 1\) is investigated. In this case, the complexity of sampling ridge functions reduces drastically to the complexity of sampling univariate Lipschitz functions. The authors obtained lower and upper bounds for the deterministic worst-case error with regard to standard information. It is observed that the sampling problem’s degree of difficulty varies essentially, depending on \(\alpha\) and \(p\). As the authors note, surprisingly, they could see almost the entire hierarchy of tractability levels as introduced in [E. Novak and H. Woźniakowski, Tractability of multivariate problems. Volume I: Linear information. Zürich: European Mathematical Society (EMS) (2008; Zbl 1156.65001)] and [E. Novak and H. Woźniakowski, Tractability of multivariate problems. Volume II: Standard information for functionals. Zürich: European Mathematical Society (EMS) (2010; Zbl 1241.65025)].
The article is organized as follows. Section 1 is an introduction. Precise definitions and several interesting auxiliary results are given in Section 2. Section 3 is devoted to entropy numbers for the ridge function classes. Lower and upper bounds for sampling numbers are found in Section 4. Section 5 is devoted specifically to tractability, in particular, to polynomial tractability. Here, the authors make connections of their findings on sampling numbers to information-based complexity.
The article should be interesting for specialists in approximation theory, data analysis, algorithms, and many areas of applied mathematics.