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

rate of convergencecurse of dimensionalitytractabilityentropy numbersweak tractabilityinformation-based complexitypolynomial tractabilityridge functionssampling approximationsampling numbers

Mathematics Subject Classification ID

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

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

• 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?)
• 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
• Identifying linear combinations of ridge functions
• Infinite-dimensional quadrature and approximation of distributions
• Learning Theory
• Learning functions of few arbitrary linear parameters in high dimensions
• 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 Gelfand widths of \(\ell_p\)-balls for \(0 < p \leq 1\)
• The curse of dimensionality for numerical integration of smooth functions. II
• The elements of statistical learning. Data mining, inference, and prediction
• 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

(18)

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

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)