The Curse of Dimensionality for Monotone and Convex Functions of Many Variables
Establishes fundamental lower bounds for high-dimensional monotone and convex function approximation, showing that even these structured classes are intractable in the worst case.
The paper proves that integration and approximation of monotone and convex bounded functions of many variables suffer from the curse of dimensionality, requiring exponentially many function evaluations in the dimension to achieve a given error.
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 $ε$.