I keep coming across this term when reading about reinforcement learning, for example in this sentence:
If the problem is modelled with care, some Reinforcement Learning algorithms can converge to the global optimum
(source)
or here:
For any fixed policy Pi, the TD algorithm described above has been proved to converge to VPi
(source)
My understanding of the word converge is that it means several things coming together to the same point, but how can a single thing (the algorithm) do that?
An iterative algorithm is said to converge when, as the iterations proceed, the output gets closer and closer to some specific value. More precisely, no matter how small an error range you choose, if you continue long enough the function will eventually stay within that error range around the final value.
In some circumstances, an algorithm will not converge, having an output that always varies by some amount. It could even diverge, where its output will undergo larger and larger value swings, never approaching a useful result. More precisely, no matter how long you continue, the function value will never settle down within a range of any "final" value.
The "converge to a global optimum" phrase in your first sentence is a reference to algorithms which may converge, but not to the "optimal" value (e.g. a hill-climbing algorithm which, depending on the function and initial conditions, may converge to a local maximum, never reaching the global maximum).
The concept of convergence is a well defined mathematical term. It essentially means that "eventually" a sequence of elements get closer and closer to a single value. We call this single value the "limit".
The formal definition goes something like this:
Given (infinite) sequence of real numbers X0, X1, X2, ... Xn ... we say Xn converges to a given number L if for every positive error that you think, there is a Xm such that every element Xn that comes after Xm differs from L by less than that error.
Example:
Imagine a sequence as such:
Does Xn converge to zero? Yes! Why?
Think of an error E (for example, E = 0.0025). Is there a element in the sequence that after that every element is below 0.025? Yes! That element is X3 = 0.001. After X2, every XN is below 0.0025. Can this be done to every E > 0? Yes. For every positive error that we choose, we can see how many zeroes it has before its first decimal point and the sequence will be lower that it starting from the element that has the same number of zeroes.
This means that Xn = 1/(10^5) converges to 0. As in "it can get closer and closer to zero" as much as we want.
"Technically" what converges is not the algorithm, but a value the algorithm is manipulating or iterating. For example, lets say we are writing an algorithm that prints all the digits of PI.
The algorithm starts printing numbers like:
We could ask ourselves: does the algorithm print numbers every increasingly close to PI? In other words, does the sequence X0, X1, ... XN ... that our algorithm prints converges to PI?
If so, we say our algorithm converges to PI.
Usually, when we write an algorithm, we are interested in knowing if the solution the algorithm provides is the correct one for the problem it solves. This can sometimes come in the form of a convergence.
In general, algorithms have what we call metrics. A metric is a number that we give to a given result that the algorithm produces. For instance, in A.I / Machine Learning iterative algorithms it is very common for us to keep track of the "error" that the algorithm is generating based on the input. This error is a metric.
In those iterative algorithms, every step generates a different error. And what the algorithm tries to do is to minimize that error so it ever gets smaller and smaller. We say that the algorithm converges if it sequence of errors converges.
In those cases, the global optimum is usually defined as the setup that has the lowest error possible. In that case, the "algorithm converges to the global optimum" means that "the algorithm generates errors in a sequence that converges to the lowest error possible".
If the "global optimum" is our "correct solution", stating that our algorithm converges is the same as stating that our algorithm is correct.
Also, keep in mind that stating that an algorithm converges requires a proof (as we did for our 0.001, 0.0001, ..., example).
An example of this could be in the case of a classifier. Suppose we want to classify if numbers are odd or even using a machine learning algorithm, and that we have the following dataset:
Our algorithm for every set of numbers spits for each of them if they are even or odd. For that, we can define a metric error as being the number of times it got wrong divided by the total number of elements that were given.
So, if our algorithm spits the following:
Our error metric would be 3/5 = 0.6. Now lets say we run the algorithm again and it now spits:
Our error metric would be 1/5 = 0.2.
Lets say it runs more and more times, and our sequence of errors look something like this:
0.6, 0.2, 0.1, 0.01, 0.000456, 0.00000543, 0.000000000444 ....
So the big question is: will our algorithm ever be zero? Will it ever converge to zero? Will our algorithm every converge? Can we prove that eventually it will get it right (or as close to right as possible)?
Hopefully so :)
