  A core principle in statistical learning is that smoothness of target
functions allows to break the curse of dimensionality. However, learning a
smooth function seems to require enough samples close to one another to get
meaningful estimate of high-order derivatives, which would be hard in machine
learning problems where the ratio between number of data and input dimension is
relatively small. By deriving new lower bounds on the generalization error,
this paper formalizes such an intuition, before investigating the role of
constants and transitory regimes which are usually not depicted beyond
classical learning theory statements while they play a dominant role in
practice.
