Entropy and sampling numbers of classes of ridge functions

. We show that they are essentially as compact as the class of univariate Lipschitz functions. Second, we examine sampling numbers and face two extreme cases. In case

p = 2

, sampling ridge functions on the Euclidean unit ball faces the curse of dimensionality. It is thus as difficult as sampling general multivariate Lipschitz functions, a result in sharp contrast to the result on entropy numbers. When we additionally assume that all feasible profiles have a first derivative uniformly bounded away from zero in the origin, then the complexity of sampling ridge functions reduces drastically to the complexity of sampling univariate Lipschitz functions. In between, the sampling problem's degree of difficulty varies, depending on the values of

a l p h a

and

p

. Surprisingly, we see almost the entire hierarchy of tractability levels as introduced in the recent monographs by Novak and Wo'zniakowski.

Review text

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 \textit{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 [\textit{E. Novak} and \textit{H. Woźniakowski}, Tractability of multivariate problems. Volume I: Linear information. Zürich: European Mathematical Society (EMS) (2008; Zbl 1156.65001)] and [\textit{E. Novak} and \textit{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.

Recommendations

Cites work

Cited in

(19)

This page was built for publication: Entropy and sampling numbers of classes of ridge functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q745852)