The overshooting and correcting pattern (and 'fractal' therein) can be understood analogously by considering the binary search tree. The tree is fractal (i.e.

The overshooting and correcting pattern (and 'fractal' therein) can be understood analogously by considering the binary search tree. The tree is fractal (i.e. sub trees) and each step may overshoot until the solution is found. This analogy can be made rigorous by looking at bisection search on a convex function instead of a simple binary search tree. The same pattern holds. "Fractal" patterns occur because the problem is invariant under scaling. What is interesting is the initial half of small steps. I have not read the original paper to give a professional view on the mathematics, but it may just be that initial small steps are priming the optimizer to find the right scale. Unfortunately, it may just be that the findings are not something fundamental to gradient descent or optimization in general, but just an observed property of the smooth convex cost function considered under this particular algorithmic investigation.