A question on computational complexity of a numerical differentiation (equation (5.77)) in Bishop's Pattern Recognition and Machine Learning

Question

In page 249 of Christopher M. Bishop's book "Pattern Recognition and Machine Learning", it is said

Again, the implementation of such algorithms can be checked by using numerical differentiation in the form $$\frac{\partial y_k}{\partial x_i}=\frac{y_k(x_i+\epsilon)-y_k(x_i-\epsilon)}{2\epsilon}+O(\epsilon^2)\tag{5.77}$$ which involves $2D$ forward propagations for a network having $D$ inputs.

But I can see no relation of the computational complexity with $D$. According to the first paragraph of section 5.3.3 of the same book, my understanding is that the computation of (5.77) should involves $2W$ forward propagations for a network having $W$ weights, one for computing $y_k(x_i+\epsilon)$ while another for $y_k(x_i-\epsilon)$. Am I right? If the book is indeed correct, why does the numerical differentiation involve $2D$ forward propagations? Thanks a lot.

Answer 1

its talking about units of 1 full computation ie calculating an output for a given input.

To do the numerical differentiation for each input feature you shift each feature by +/- epsilon (leaving other input features same) and calculate the resulting output so you calculate over 2 x D input patterns. eg with x_i = (1,0,0) then eg (1+e, 0,0) (1-e,0,0), (0, 1+e,0), (0,1-e,0) , (0, 0, 1+e), (0,0, 1-e).