How can a deep neural network learn anything?

When training a network, gradients are back-propagated throughout the entire network, updating parameters such as weights and biases.

So the last layer $n$ sees features proposed by the previous layer $n-1$, and decides, based on their performance as measured by the loss, to give a little more weight to this one and a little less to that one -- changing its output.

Simultaneously, layer $n-1$ does the same thing, and also changes its parameters, meaning that the features layer $n$ will see at the next round are not exactly the same that were used to compute an update.

But wait, layer $n - 2$ also changes its parameters... and so on till the first layer.

So, at the next round, layer 1 has changed and produces slightly different features, which are then provided to layer 2, which has also changed, and so on. When features reach layer $n$, how can they have anything in common with the features that have been used to optimize it?

Furthermore, in practice, the first layers typically have much less parameters than the last ones. It seems to me that all downstream layers depend on those first convolutions, and that any change in them deeply affects all downstream features based on them.

Now, it would be reasonable to say, "Stop thinking too hard. These are gradients. If you take a step small enough, maybe a very very small step indeed, features will change only oh so slightly. The cost will go down, this is mathematical."

But, in deep learning, the learning rate is taken as large as can be during the first phase, precisely when features are shaped.

How, in these conditions, can a network learn anything?

You're absolutely right, it makes no sense, and it's a huge problem.

The loss function is locally linear. You are effectively saying that $L(w+h) = L(w)+h\cdot dL(w)$, where $L$ is your loss function, $w$ your vector of weights, and $dL$ is the gradient vector. In this sense, the contribution of changes of each weight produces an approximately linear change in $L$ as a function of the step-size. $dL$ and in particular $dL_i$, the individual components, definitely depends on weights in a nonlinear way. This helps to decouple the range of the output from the range of how $L$ changes as the weights change. Due to the sensitivity you point out, there are also strategies which assign smaller learning rates to earlier layers, especially for the purposes of fine-tuning a network.

Even though we choose a larger learning rate initially, this learning rate is still tuned to how sensitive $L$ is, so that the above linear relationship is roughly held.

In theory the above is right, but in practice the situation is considerably more complex. For example in a recent paper The Shattered Gradients Problem: If resnets are the answer, then what is the question? Balduzzi, et. al, evidence is presented exactly to your point, that vanilla deep learning networks have gradients that are extremely sensitivity to both weights and input images, even with batch normalization. It is shown that residual networks considerably improve this sensitivity, which makes a convincing case for why they work so well.

At the same time, initially almost anything is better than random guessing. For example if you're training a network to tell "1" apart from "7", then it's clear that "1"'s have more vertical features, vs 7's have a ton of diagonal and horizontal features, so that even first level convolutions that correlate slightly with vertical vs diagonal features will contribute to improving the model.

A recent paper addresses this topic: "Doing the impossible: Why neural networks can be trained at all" by Nathan Hodas, Panos Stinis

As deep neural networks grow in size, from thousands to millions to billions of weights, the performance of those networks becomes limited by our ability to accurately train them. A common naive question arises: if we have a system with billions of degrees of freedom, don’t we also need billions of samples to train it? Of course, the success of deep learning indicates that reliable models can be learned with reasonable amounts of data. Similar questions arise in protein folding, spin glasses and biological neural networks. With effectively infinite potential folding/spin/wiring configurations, how does the system find the precise arrangement that leads to useful and robust results? Simple sampling of the possible configurations until an optimal one is reached is not a viable option even if one waited for the age of the universe. On the contrary, there appears to be a mechanism in the above phenomena that forces them to achieve configurations that live on a low-dimensional manifold, avoiding the curse of dimensionality. In the current work we use the concept of mutual information between successive layers of a deep neural network to elucidate this mechanism and suggest possible ways of exploiting it to accelerate training. We show that adding structure to the neural network that enforces higher mutual information between layers speeds training and leads to more accurate results. High mutual information between layers implies that the effective number of free parameters is exponentially smaller than the raw number of tunable weights.

This is why learning rates, despite being "as large as can be" are still quite small. On the order of $10^{-3}$ and $10^{-4}$ is common. But you are right that this can be an issue.

Batch normalization is one partial solution to this problem which often allows for faster training: Normalizing the activations after each layer so that they have the same mean and variance reduces the problem of "covariate shift" -- in other words, the fact that after an iteration of SGD, the features output at a certain layer might've changed in an unpredictable way, making it hard for the subsequent layers to do their job.

So to summarize: a combination of small step sizes and batch norm.