In gradient descent, how do we know we found the smallest minimum?

Question

Let's say we start at a wrong "hill" (the highest one), it will find the minimum in that area, but not the whole area? To me it seems, at the moment, that it depends a lot on what m and b we choose at the start.

Answer 1

In short, you don't. Gradient descent only gives you convergence to some local minimum. The first sentence of the wikipedia definition says it gives you a local minimum. In real life examples there often is only a single local minimum and even if there are several, gradient descent will often converge to the gloval minimum but there is no guarantee. As your graph shows, if you try it is not that hard to come up with examples where you get a local minimum which is not the global minimum.