Entropy and sampling numbers of classes of ridge functions

DOI10.1007/S00365-014-9267-XMaRDI QIDQ745852zbMATH OpenOpenAlexFDO

Authors Sebastian Mayer, Tino Ullrich, Jan Vybíral

Publication date 14 October 2015

Published in Constructive Approximation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1311.2005

zbMATH Keywords

curse of dimensionalityentropy numbersinformation-based complexitypolynomial tractabilityrate of convergenceridge functionssampling approximationsampling numberstractabilityweak tractability

Mathematics Subject Classification ID

Approximation by polynomials (41A10) Rate of convergence, degree of approximation (41A25) Best approximation, Chebyshev systems (41A50) Multidimensional problems (41A63) Sobolev spaces and other spaces of ``smooth functions, embedding theorems, trace theorems (46E35) Numerical interpolation (65D05) Algorithms for approximation of functions (65D15)

Abstract: We study properties of ridge functions $f(x)=g(acdotx)$ in high dimensions $d$ from the viewpoint of approximation theory. The considered function classes consist of ridge functions such that the profile $g$ is a member of a univariate Lipschitz class with smoothness $alpha>0$ (including infinite smoothness), and the ridge direction $a$ has $p$-norm $|a{|}_{p}leq1$. First, we investigate entropy numbers in order to quantify the compactness of these ridge function classes in $L_{infty}$. 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 $alpha$ and $p$. Surprisingly, we see almost the entire hierarchy of tractability levels as introduced in the recent monographs by Novak and Wo'zniakowski.

Recommendations

• Geometric properties of the ridge function manifold
• The recovery of ridge functions on the hypercube suffers from the curse of dimensionality
• 0n the best approximation by ridge functions in the uniform norm
• Capturing ridge functions in high dimensions from point queries
• Best approximation by ridge functions in L_p-spaces

Cites work

• A lower estimate for entropy numbers
• Approximation of infinitely differentiable multivariate functions is intractable
• Asymptotic minimax estimation of regression in the additive model
• Capturing ridge functions in high dimensions from point queries
• Direct estimation of the index coefficient in a single-index model
• Entropy numbers of diagonal operators between symmetric Banach spaces
• Entropy numbers of spheres in Banach and quasi-Banach spaces
• Function spaces in Lipschitz domains and optimal rates of convergence for sampling
• Geometric properties of the ridge function manifold
• Harmonic analysis of neural networks
• scientific article; zbMATH DE number 44592 (Why is no real title available?)
• scientific article; zbMATH DE number 193625 (Why is no real title available?)
• scientific article; zbMATH DE number 477682 (Why is no real title available?)
• scientific article; zbMATH DE number 713342 (Why is no real title available?)
• scientific article; zbMATH DE number 1070548 (Why is no real title available?)
• scientific article; zbMATH DE number 1404611 (Why is no real title available?)
• scientific article; zbMATH DE number 1405266 (Why is no real title available?)
• scientific article; zbMATH DE number 962825 (Why is no real title available?)
• Identifying linear combinations of ridge functions
• Infinite-dimensional quadrature and approximation of distributions
• Learning functions of few arbitrary linear parameters in high dimensions
• Learning Theory
• Lower bounds for constant weight codes
• Minimax-optimal rates for sparse additive models over kernel classes via convex programming
• Optimal reconstruction of a function from its projections
• Ridgelets: a key to higher-dimensional intermittency?
• Sparse tensor discretizations of high-dimensional parametric and stochastic PDEs
• Statistics for high-dimensional data. Methods, theory and applications.
• The curse of dimensionality for numerical integration of smooth functions. II
• The elements of statistical learning. Data mining, inference, and prediction
• The Gelfand widths of \(\ell_p\)-balls for \(0 < p \leq 1\)
• Tractability of multivariate problems. Volume I: Linear information
• Tractability of multivariate problems. Volume II: Standard information for functionals.
• Weak and quasi-polynomial tractability of approximation of infinitely differentiable functions

Cited in

(19)

• The recovery of ridge functions on the hypercube suffers from the curse of dimensionality
• On recovery of regular ridge functions
• Stable recovery of entangled weights: towards robust identification of deep neural networks from minimal samples
• Recovery of regular ridge functions on the ball
• Robust and resource-efficient identification of two hidden layer neural networks
• On some aspects of approximation of ridge functions
• Counting via entropy: new preasymptotics for the approximation numbers of Sobolev embeddings
• Entropy numbers of functions on \([-1,1]\) with Jacobi weights
• On the entropy numbers between the anisotropic spaces and the spaces of functions with mixed smoothness
• Preasymptotic error bounds via metric entropy
• Gradient-based dimension reduction of multivariate vector-valued functions
• Gaussian quadrature and polynomial approximation for one-dimensional ridge functions
• Tractability of the approximation of high-dimensional rank one tensors
• Approximation of curve-based sleeve functions in high dimensions
• Tractability of sampling recovery on unweighted function classes
• Sampling and entropy numbers in the uniform norm
• Gelfand numbers related to structured sparsity and Besov space embeddings with small mixed smoothness
• Approximation of functions: optimal sampling and complexity
• Geometric properties of the ridge function manifold

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)