In chapter 2 of Michael Nielsen's Neural Networks and Deep Learning it says backpropagation relies on
The first assumption we need is that the cost function can be written as an average $C = \frac{1}{n} \sum_{x} C_x$ over cost functions $C_x$ for individual training examples, $x$.
I can accept this is because propagation only allows us to compute $\frac{\partial C_x}{\partial w}$ and $\frac{\partial C_x}{\partial b}$ for a single training example $x$. But are all cost functions in the literature really an average of cost for individual training examples? If a cost function is not defined this way, is backpropagation completely useless?
The second assumption we make about the cost is that it can be written as a function of the outputs from the neural network
How else would you define a cost function? At some level doesn't it have to be a function of the outputs from the neural network? How else would you measure the error between a training sample's label and what your neural network is doing?