Curse of dimensionality

Remarks

Example: let $F_d$ be the functions $f$ on $[0, 1]^d$ with $\abs{f} \le 1$ and $\abs{f(x) - f(y)} \le \norm{x - y}_\infty$, and let $S_d$ be the integral. Take an algorithm with $n \le 2^{d-1}$ values, and let $P$ be the points it uses for the input $0$. The function $g(x) = \min\big(1, \operatorname{dist}_\infty(x, P)\big)$ lies in $F_d$ and vanishes on $P$, so the algorithm uses the same points and outputs the same number for $g$, $-g$ and $0$. The set where $g < \frac14$ is covered by $n$ cubes of side $\frac12$, of total volume at most $n 2^{-d} \le \frac12$, so $\int g \ge \frac14 \cdot \frac12 = \frac18$. Hence the error is at least $\frac18$ for $g$ or for $-g$, and $n(\varepsilon, d) > 2^{d-1}$ for $\varepsilon < \frac18$: the problem suffers from the curse.

Non-example: let $F_d$ be the functions $f(x) = h(x_1)$ that depend only on the first coordinate, where $h \colon [0, 1] \to \R$ satisfies $\abs{h} \le 1$ and $\abs{h(s) - h(t)} \le \abs{s - t}$. A quadrature rule in the first variable alone reaches error $\varepsilon$ with a number of points independent of $d$, so no exponential lower bound holds.

In the information-based complexity literature the error is often normalized by the error of the zero algorithm; this changes constants but not the idea.