Is there a "flaw" in the backpropagation algorithm? While trying to find a better backpropagation algorithm, I came across a paradox in my algorithm and then I found out this also happens in the usual backpropagation algorithm.

Our neural network looks like this:



In this simple example, we have no biases. The activiation function is the usual
$f(x)=\frac{1}{1+e^{-x}}$

Our training set is just one datapoint: input = 0.9 and target_output = 0.9. The learning factor is set to 0.1.

The paradox happens when w2 is randomly initialized to a negative value. First, let's take a look at the "normal" situation (where the paradox does not happen). Let's say w1 and w2 are both positive, but the output is less than 0.9. w1 and w2 are both initialized at 0.1. Then to reduce the error, both w1 and w2 are increased, so the the output will get closer to 0.9. This is visible in the next graph (x is the training iteration, each training iteration contains one backpropagation).



Now let's take a look at the situation that w1 is intialized at 0.1 and w2 is initialized with a negative value (-0.5). Initially, an increase in w1 would cause a more negative value for the output layer, which increases the error. However, that's only the case because w2 is negative. Although w1 will decrease in the beginning, it will start increasing as soon as w2 becomes positive. The blue line (w1) is clearly decreasing in the beginning in the below graph from my experiment:



This "wrong" learning in the beginning of the blue line w1, is a consequence of using the derivative of the error function to induce small learning steps. Would it be better to somehow anticipate a positive w2 that will be needed anyway and so increase w1 from the beginning instead? Can we make a better backpropagation algorithm?
There's no paradox.  This is not a flaw.  Nothing is going wrong here.  In both examples, you're making steady progress: the output steadily gets (monotonically) closer and closer to the target.

Looking at individual weights (like w1 or w2), there's no reason to expect them to vary monotonically during the learning process.  If we perfect foresight and we know what the final optimal values of the weights are, we'd know whether each weight needs to increase or decrease -- but we don't.

Remember that backpropagation is just gradient descent, used to minimize some loss function.  Gradient descent is a local method for optimization: it makes a locally greedy step.  It has no global knowledge and as a result if you look at any single weight (any single coordinate), it won't necessarily vary monotonically: it might increase and then decrease, for instance.

Can you improve on backpropagation?  Yes, you can.  A large part of the success of deep learning is that researchers have found improvements to gradient descent for training neural networks (e.g., learning rate, momentum, and more).  Nonetheless, they're still optimization methods that work by taking a locally optimal step, and so they can be subject to overshoot and to phenomena such as you noticed.  Multidimensional optimization is hard.  You're going to see this kind of thing happen in pretty much any iterative method for optimization.

Bottom line: This isn't a flaw, this is only to be expected, given the difficulty of multidimensional optimization.  You still get to optimal values in the end, and that's almost-miraculous in its own right -- you should be glad for that and not worry too much about the fact that it takes longer to get there than if we already knew what the optimal solution was before we began.