I am reading a blog post that tries to explain backpropagation. In the build up the author shows how a naive method for computing gradients is sub-optimal.
Consider this:
Naive feedforward algorithm (not efficient!)
It is useful to first point out the naive quadratic time algorithm implied by the chain rule. Most authors skip this trivial version, which we think is analogous to teaching sorting using only quicksort, and skipping over the less efficient bubblesort.
The naive algorithm is to compute ∂ui/∂uj for every pair of nodes where ui is at a higher level than uj. Of course, among these V2 values (where V is the number of nodes) are also the desired ∂f/∂ui for all i since f is itself the value of the output node.
This computation can be done in feedforward fashion. If such value has been obtained for every uj on the level up to and including level t, then one can express (by inspecting the multivariate chain rule) the value ∂uℓ/∂uj for some uℓ at level t+1 as a weighted combination of values ∂ui/∂uj for each ui that is a direct input to uℓ. This description shows that the amount of computation for a fixed j is proportional to the number of edges E. This amount of work happens for all V values of j, letting us conclude that the total work in the algorithm is O(VE).
I understand the quadratic complexity, but how does this method work without having the training error first?
You must need the training error for updating any parameter, how can you then proceed in a feed forward manner?
