How does using PCA speed up supervised learning? In his popular course, Andrew Ng mentions using PCA to speed up supervised learning (Lecture 14.7). The basic idea is dimensionality reduction, wherein the extremely high-dimensional input features $\{x^{(1)},\ldots, x^{(k)}\} \in R^{N}$ are mapped to $\{z^{(1)},\ldots, z^{(k)}\} \in R^{M}$, where $M \ll N$.
Intuitively, the argument that training for lower-dimensional data should be quicker feels correct, but I could not find a good explanation or proof for this intuition.
My specific question is about the influence of de-correlation of input features that PCA performs towards speeding up learning. My intuition is that decorrelated features should be quicker to learn since the covariance matrix of the transformed $z^{i}$ features is a diagonal matrix.
For example, in a neural network, the weights for learning correlation between transformed features $z^{i}$ do not require much training since they are already de-correlated.
In other words, suppose I choose not to reduce dimensions after PCA (let's just say the eigenvalues are comparable), my supervised training would still be faster due to de-correlated transformed features. Is this intuition correct?

 A: Yes, your intuition is correct. In "Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift", Sergey Ioffe and Christian Szegedy write

It has been long known (LeCun et al., 1998b; Wiesler & Ney, 2011) that the network training converges faster if its inputs are whitened – i.e., linearly transformed to have zero means and unit variances, and decorrelated.

So you might expect to find that the network trains faster if you de-correlate the inputs in addition to applying zero mean and unit variances. PCA will improve the convergence even if the dimension is not reduced, because the effect of correlation is not present.
The following citations provides more detail.

*

*LeCun, Y., Bottou, L., Orr, G., and Muller, K. "Efficient
backprop." In Orr, G. and K., Muller (eds.), Neural Networks: Tricks of the trade. Springer, 1998b.


*Wiesler, Simon and Ney, Hermann. "A convergence analysis of log-linear training." In Shawe-Taylor, J., Zemel,
R.S., Bartlett, P., Pereira, F.C.N., and Weinberger, K.Q.
(eds.), Advances in Neural Information Processing Systems 24, pp. 657–665, Granada, Spain, December 2011
