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

DOI10.1016/J.JAT.2011.02.009MaRDI QIDQ2275488zbMATHOpenAlexFDO

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

curse of dimensionalitymonotone functionsconvex functionsintegration problemminimal cost computing

Mathematics Subject Classification ID

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

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$.

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

• scientific article; zbMATH DE number 16685 (Why is no real title available?)
• scientific article; zbMATH DE number 44104 (Why is no real title available?)
• A geometric inequality and the complexity of computing volume
• Deterministic and stochastic error bounds in numerical analysis
• 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)

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

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)