Why Was Backprop Invented? I'm currently researching artificial neural networks and I keep wondering why do we use "backpropagation" to train a neural network.
An ANN is basically just a very large and complex function $f(\mathbf{input};\mathbf{w})$ where $\mathbf{input}$ and $\mathbf{w}$ are vectors $\mathbb{R}^n$ which contain the initial input sequence and all weights of all hidden and output layers of the network.
Therefore, why don't we just optimize $E(\mathbf{expected}, f(\mathbf{input};\mathbf{w}))$ with respect to $\mathbf{w}$ using almost any function optimization method? 
Why was the "back propagation of errors" and the layered structure invented and used?
 A: You can indeed use any function optimization method to train a neural network. For a small network, when the Hessian is tractable, one can use second-order optimization methods (though this is still compatible with backprop likely).
As another example, evolutionary optimization techniques have been shown to be reasonably effective in certain cases as well, e.g:


*

*Evolution Strategies as a Scalable Alternative to Reinforcement Learning

*Deep Neuroevolution: Genetic Algorithms are a Competitive Alternative for Training Deep Neural Networks for Reinforcement Learning
However, time has so far shown us that stochastic gradient descent is the most effective optimization method.
Part of the reason for this is that backprop is highly computationally efficient. Conceptually, as you say, backprop is nothing more than applying the chain rule through the network. But how do we actually compute such gradients?
One of the revolutions enabling deep learning is the use of automatic differentiation algorithms to compute gradients. Its efficiency as an algorithm relies on backprop. In fact, it is worth noting that backprop is a special case of reverse mode automatic differentiation, from the optimization literature; all the benefits of that approach thus carry over to backprop as well.
Think about a deep network for a moment, i.e. $f_1(f_2(f_3(\ldots f_n(x|\theta_n)\ldots|\theta_3)|\theta_2)|\theta_1)=y$. What is the gradient of the loss wrt to $\theta_n$ (i.e. $\nabla_{\theta_n} \mathcal{L}$)? We only have 3 options to compute gradients:


*

*Backprop (automatic/algorithmic): starting at the end-node (the loss function), we progressively pass gradients back through the computation graph, computing the gradients of the local parameters as we go.

*Symbolic: this is tractable (even great) for small models, but will be horrific for large ones. Furthermore, the expressions output by computer algebra systems in practice tend to be highly inefficient unless optimized by a practitioner, by hand (not feasible for large models).

*Numeric: this means finite differences. Unfortunately, this is also absurdly inefficient for large models. Suppose the set of parameters $\Theta=\{ 
\theta_{ij}\;\forall\;i,j \}$ has size $|\Theta|$ in the millions (relatively common these days). Let $f(x|\Theta)$ be the model and define a perturbation $ 
\Delta_{ij} = (0,\ldots,0,\epsilon_{ij},0,\ldots,0)\in\mathbb{R}^{|\Theta|} $; treat $\Theta$ as a vector so that $\Delta_{ij}+\Theta$ is sensible.
Well, then we have to do $ \nabla_{\theta_{ij}}\mathcal{L}\approx [\mathcal{L}(\Theta+\Delta_{ij}) - \mathcal{L}(\Theta-\Delta_{ij})]/(2\epsilon_{ij}) $. 
Ok, so to get the gradient wrt one parameter, we have to compute the loss function twice. This means we need to compute the loss (and run the model) $2|\Theta|B$ times every time we want the gradient (and then perform the $|\Theta|$ update operations on the weights, where $B$ is the number of inputs we use to approximate the gradient). This is ludicrously costly. (By comparison, using backprop, we basically run the model $B$ times (NOT $|\Theta|$ times $B$), then do a single backward pass updating the weights as we go (same update as above). So we can save potentially tens of millions of loss evaluations (each of which is many millions of operations) per model update by using backprop.
One reason for the efficiency of backprop is the reuse of information in the computation graph. The in-order graph traversal guarantees we never do any wasted computation (e.g. evaluate the same gradient twice in order to update two different nodes that both depend on the same downstream node). If we used symbolic differentiation (or did things by hand), we would get large expressions that would be repeatedly evaluated at every node (in fact we are essentially guaranteed that this will happen, since the chain rule says that the gradients at higher/earlier nodes are compositions of gradients from lower/later nodes in the graph). Instead of evaluating these (sub)expressions anew at every node, we can instantly evaluate them by simply substituting in the numeric value computed at the previous layer directly.
I didn't even mention really dirty problems with symbolic and numerical gradient evaluators, namely stability and accuracy issues (e.g. catastrophic cancellation).
Further micro-optimizations are also possible with this approach. For instance, properly ordering the Jacobian matrix multiplications can save a lot of time. (Matrix multiplication is associative, but this does not mean every ordering of the multiplication has the same cost!).

If you're thinking, "ok fine, so among ways to get the gradient, autodiff backprop seems to be the best thing we have right now... but what's wrong with non-gradient-based techniques then?", well, besides empirical/experimental reasons, one can think of it like this: the gradient very cheaply encapsulates a large amount of information that non-derivative-based techniques simply ignore. With modern techniques, a backward pass is say 1-5 times costlier than a forward pass. In return, we get a huge vector $\nabla_\Theta \mathcal{L}$ where every component carries useful information. The cost-to-gain ratio is quite extraordinary. Assuming the model is differentiable, there is no reason to ignore it. (Second-order methods are not plausible, however, because one needs to store a matrix of size $|\Theta|\times|\Theta|$, which is currently impossible; nevertheless, there are efforts in this direction, such as KFAC).
Why then are the evolutionary strategies above still useful? Essentially because they can be used to optimize models that are not differentiable, and/or where the gradient of the loss is so noisy/unstable that simple direct gradient descent is untenable. Reinforcement learning is a common arena for this to occur, since the reward function is not a differentiable loss function. Nevertheless, a stochastic gradient wrt the reward can still be estimated (e.g. likelihood ratio estimators). 

I went on a bit of a tangent, so let me summarize:

Therefore, why don't we just optimize $\mathcal{L}(y,f(x|\Theta))$ with respect to $\Theta$ using almost any function optimization method?

Because of computational efficiency.

Why was the "back propagation of errors" and the layered structure invented and used?

The layered structure is biologically inspired (hence the name neural networks). However, from a mathematical perspective, the idea is that we are composing simple linear and non-linear functions to get a powerful, expressive model. Composition is a vastly more powerful operation than e.g. multiplication or addition. So I would think of layering as composition. 
As for backprop, it is simply a special case of the highly effective algorithm from the optimization literature known as reverse mode automatic differentiation (though it was discovered independently, not derived from it, to my knowledge). The use of a computation graph and backprop is also largely motivated by computational efficiency considerations.
