Gradient Descent

Question

Can we use Gradient descent to find Global/local maxima? What types of problem needed to maximize the function? Can we do it with GD? Can anybody explain my question with an example relevant to machine learning?

Thanks in advance.

Answer 1

Theoretically, it is possible to find a global minimum using gradient descent.

In reality, however, it rarely happens - it is also pretty much impossible to prove you have the global minimum!

Imagine we have a 2d loss surface; a loss curve as in the figures below. In order to reach the global minimum (the lowest point on the curve), you would need to make steady progress towards the minimum and also reduce the size of the steps that you take on the way, as to not overshoot the minimum (left figure). If you slow down too fast, you never quite reach the minimum (middle figure). If you get it just right, you make it to the global minimum (right figure). The size of those jumps is controlled by the learning rate, which is multiplied with the loss in each iteration of back-propagation.

For this theoretical achievement, the theory requires the loss curve to be convex - meaning it has a shape similar to those in the figures. Here is a recent paper that explores this in more detail. The title says it all: Gradient Descent Finds Global Minima of Deep Neural Networks

There are methods to increase your chances of success, usually involving using a dynamic learning rate, which is adjusted to the rate at which the model learns i.e. how well it improves on a validation data set whilst learning from the training set. As the figure on the right above shows, it is desirable to reduce the learning rate as the loss curve flattens out.

In reality, the "loss surface" on which we are searching for are not 2-dimensional, but have much higher orders e.g. 200. Things such as random initialisation of your model could make the difference between which one you finally land in.

This is perhaps why using ensemble methods (groups of models) generally performs better than a single model. It explores the loss landscape more thoroughly and increases the odds of finding better minima.

---

Local Minima

If a model seems to covnerge (verified by e.g. loss on the validation set stops improving), but the results on the test set appear to be far from optimal or what is should be possible, then it could be the case the the algorithm has ended up in a local minumum, unable to escape.

You can imagine that the updates to the parameters became so small that it is no longer "active" or energetic enough to jump out of the small minimum. Common approaches to get around this situation (or to prevent it) include:

• using an update rule for weights that carries some momentum (for example the Adam optimizer)
• using simulated annealing, which is a fancy way of saying that we perform larger jumps to different areas on the loss curve, exploring more of it and not limiting ourselves to local minima. Here is a small graphic (from Wikipedia) that shows it in action:

Here is a superb blog post about these optimisers and simulated annealing as another way to "jump" out of local minima.

---