From "] Learning Deep Architectures for AI". see: http://www.iro.umontreal.ca/~lisa/pointeurs/TR1312.pdf (see section 3.1)
"The local generalization issue is directly connected to the literature on the curse of dimensionality, but the results we cite show that what matters for generalization is not dimensionality, but instead the number of “variations” of the function we wish to obtain after learning. For example, if the function represented by the model is piecewise-constant (e.g. decision trees), then the question that matters is the number of pieces required to approximate properly the target function. There are connections between the number of variations and the input dimension: one can readily design families of target functions for which the number of variations is exponential in the input dimension, such as the parity function with d inputs."
Anyone care to explicate? Or try to reword this paragraph. Or give examples.
(And is he saying that decision trees are piecewise-constant?)