Using gradient information in minimizing error function, in Bishop's Pattern Recognition

The way I understand this passage is as follows.

Assume the error function $E({bf w})$ could be approximated well by a quadratic function in ${bf w}$ $${bf w^Tb} +frac{1}{2} {bf w^T H w}.$$ The minimum of such function would be uniquely determined by knowing all the coefficients contained in ${bf b, H}$, of which there are $W(W+3)/2=O(W^2)$ of those.

Now we have two ways of collecting $O(W^2)$ "pieces of information" to retrieve the $O(W^2)$ coefficients of the error function.

We could just do $O(W^2)$ point evaluations of $E({bf w})$ at different ${bf w}$. Each point evaluation further requires $O(W)$ computations which could be seen like this. Both in the sum-of-squares and the cross-entropy error functions, you need to perform $N$ evaluations (for each term in the sum) of an expression involving $y_n({bf w,x})$, and evaluating $y_n({bf w,x})$ is $O(W)$. Assuming that the data set is fixed, $N$ is just a constant, so evaluating $E({bf w})$ at a point is $N cdot O(W)=O(W)$. So altogether to retrieve all the coefficients one needs $O(W^2) cdot O(W) = O(W^3)$ computations.

Another way would be to collect $W$ units of information at a time by computing the gradient vector $nabla E$ (instead of a point evaluation which gives one number, one unit of information). So to collect $O(W^2)$ pieces of information we need to restore the function, this time we need $O(W)$ evaluations of the gradient vector since $W cdot O(W) = O(W^2)$. The interesting part is that backpropagation allows to compute the gradient vector still in $O(W)$ computations (intuitively, one may have though that if we computed one number in $O(W)$, we'd compute a vector of length $W$ in $O(W^2)$ steps; but this is the magic of backpropagation). So now miraculously, using $O(W)$ computations you are computing a vector $nabla E$ instead of a number $E({bf w})$, and to collect $O(W^2)$ information you perform $O(W)$ computations instead of $O(W^2)$. Each computation is still $O(W)$, so the total cost is now $O(W^2)$ computations.

In this section of the book, Bishop tries to argue about why should we care about an algorithm that only considers the gradient of the error function $nabla E$, as opposed to an algorithm that considers the Hessian of the error function matrix $nabla^2 E$.

To do so, he talks in terms of the information provided by each of these two quantities. With information, he is referring to what $nabla E$ or $nabla^2 E$ can tell us about the surface of the error function $E$. (The analysis of these two are considered in a prior section).

Now, in order to fully obtain the information from $nabla^2 E$, we have to consider a quadratic number of terms $O(W^2)$, i.e., we need to compute $forall i,jin{1,ldots,W}frac{partial E}{partial {bf w}_ipartial {bf w}_j}$. In a simple, yet inefficient program, this would constitute to do a double for loop to obtain each of the elements for $nabla^2E$:

# .. Initialize H as an empty WxW matrix
# .. Consider a vector w, with W weights
for i in range(W):
    for j in (W):
        # Compute the partial w.r.t. i and j of E(w) and
        # update the i,jth entry of H
        H[i,j] = partial(E, w, i, j)

Next, For a given vector $bf w$, we would like to update this $bf w$ with the information now provided by $nabla^2 E$. Again, in a computer program, this constitutes to update each entry of the weight vector ${bf w}$ by means of considering each entry in $nabla^2E$, i.e., three for-loops:

# .. Consider H (now filled with information)
# .. Consider a vector w, with W weights
for i in range(W):
    for j in range(W):
        for k in range(W):
           update_w(E, w, k, i, j)

Where update_w updates the k-th entry of the vector $bf w$ based on the information provided by the i,k-th entry of $nabla^2 E$.

This last program considers a cubic number of terms. Hence we can see that its complexity is $O(W^3)$.

Note that in order to update $bf w$ we did not consider the information provided by $nabla E$. By considering the information from $nabla E$ and neglecting what $nabla^2 E$ has of information, using a similar argument we arrive at an algorithm that has complexity $O(W^2)$ as opposed to $O(W^3)$

The information in gradient the author is referring to is basically applying newton's method iteratively, which uses Hessian matrix H and produces excellent local convergence (even direct convergence in case of quadratic cost function).

The application of Newton’s method for training large neural networks is limited by the significant computational burden it imposes. The number of elements in the Hessian is squared in the number of parameters, so with k parameters (and for even very small neural networks the number of parameters k can be in the millions), Newton’s method would require the inversion of a k × k matrix—with computational complexity of O(k^3). The following image is screenshot from Deeplearning book by Goodfellow et al. You can read more about newton's method from it. Link to chapter: http://www.deeplearningbook.org/contents/optimization.html