The Curse of Dimensionality for Monotone and Convex Functions of Many Variables

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

Cited by in corpus (4)

• The Curse of Dimensionality for Numerical Integration of Smooth Functions II
• The Curse of Dimensionality for Numerical Integration of Smooth Functions
• Polynomial tractability for integration in an unweighted function space with absolutely convergent Fourier series
• Digital inversive vectors can achieve strong polynomial tractability for the weighted star discrepancy and for multivariate integration