This is less of a question and more of a "here's my take let me know if you agree" (so I guess it might turn into a big-list?).
Dimensionality reduction refers to a collection of techniques that input data and return a lower-dimensional version, with some distortion. PCA and Johnson-Lindenstrauss are the most common examples.
From an algorithmic perspective, the tradeoff is clear: lower dimensionality yields faster runtimes and reduced storage space, but compromises precision. I call this the dimension-distortion tradeoff.
From a statistical/information-theoretic perspective, the situation seems less clear. It is commonly believed that dimensionality reduction (PCA in particular) has a denoising effect and thus should actually improve the performance. On the other hand, dimensionality reduction does discard information, which might cause the performance to degrade. Thus, one must address the statistical question: is the information I'm discarding noise or potentially useful (and even if useful, might the benefits of lower dimension still outweigh the losses)?
There appear to be very few formal analyses of the statistical benefits of dimensionality reduction. One that I'm aware of is in our ALT'13 paper (with Gottlieb and Krauthgramer). The setting there is fairly general -- metric spaces.
Are there other formal analyses of the statistical benefits of dimensionality reduction? Perhaps other tradeoffs besides those mentioned above?