The curse of dimensionality for the class of monotone functions and for the class of convex functions

DOI10.1016/J.JAT.2011.02.009MaRDI QIDQ2275488zbMATH OpenOpenAlexFDO

Authors Aicke Hinrichs, Erich Novak, H. Woźniakowski

Publication date 9 August 2011

Published in Journal of Approximation Theory (Search for Journal in Brave)

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

zbMATH Keywords

convex functionscurse of dimensionalityintegration problemminimal cost computingmonotone functions

Mathematics Subject Classification ID

Approximate quadratures (41A55) Numerical quadrature and cubature formulas (65D32) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: We study the integration and approximation problems for monotone and convex bounded functions that depend on $d$ variables, where $d$ can be arbitrarily large. We consider the worst case error for algorithms that use finitely many function values. We prove that these problems suffer from the curse of dimensionality. That is, one needs exponentially many (in $d$) function values to achieve an error $epsilon$.

Review text

The authors study the integration problem and the approximation problem, in the \(L^p\) norm with \(p\in [1,\infty]\), for classes of monotone or convex \(d\)-variate bounded functions, here \(d\) is the numbers of variables. By curse of dimensionality, the authors define the minimal cost of computing an \(\varepsilon\)-approximation. The conclusion of the paper is that the curse of dimensionality holds for the \(L^p\)-approximation problem for both classes of monotone functions, respectively of convex functions.

Recommendations

• ``Curse of dimensionality for complexity of approximation for classes of functions satisfying Lipschitz condition
• scientific article; zbMATH DE number 6731408
• Monotone class theorems for multi-dimensional functions
• The relevance of convex analysis for the study of monotonicity
• Generalized convexity and generalized monotonocity
• G-monotonicity and G-convexity
• Functions of many variables, monotone on pseudoconvex sets
• The curse of dimensionality for the \(L_p\)-discrepancy with finite \(p\)
• Generalized monotonicity and generalized convexity
• Convexification of nonsmooth monotone functions

Cites work

• A geometric inequality and the complexity of computing volume
• Deterministic and stochastic error bounds in numerical analysis
• scientific article; zbMATH DE number 16685 (Why is no real title available?)
• scientific article; zbMATH DE number 44104 (Why is no real title available?)
• Integration of monotone functions of several variables
• Quadrature formulas for multivariate convex functions
• Tractability of multivariate problems. Volume I: Linear information
• Tractability of multivariate problems. Volume II: Standard information for functionals.
• Widths and shape-preserving widths of Sobolev-type classes of \(s\)-monotone functions

Cited in

(9)

• Integration of monotone functions of several variables
• ``Curse of dimensionality for complexity of approximation for classes of functions satisfying Lipschitz condition
• The difficulty of Monte Carlo approximation of multivariate monotone functions
• The curse of dimensionality for numerical integration of smooth functions. II
• The curse of dimensionality for numerical integration of smooth functions
• Digital inversive vectors can achieve polynomial tractability for the weighted star discrepancy and for multivariate integration
• scientific article; zbMATH DE number 2237872 (Why is no real title available?)
• Polynomial tractability for integration in an unweighted function space with absolutely convergent Fourier series
• Approximation of curve-based sleeve functions in high dimensions

This page was built for publication: The curse of dimensionality for the class of monotone functions and for the class of convex functions

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