I want to know when we speak about the convergence of an algorithm, what are the conditions that we should check. For example, I was looking for the convergence of the policy iteration algorithm in reinforcement learning and I didn't know which characteristics can show its convergence. It seems that monotonicity of algorithm and uniqueness and existence of answer shows its convergence, but when I was looking for my answer in different papers, I didn't know which lemma's are responsible for showing the convergence of policy iteration algorithm.
1
-
$\begingroup$ "Algorithm" is far too broad: what kind of an algorithm? Monotonicity of what? $\endgroup$– whuber ♦Commented Dec 19, 2018 at 1:44
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
You can always check the convergence of an algorithm by increasing the number of iterations or tuning the convergence criterion to be more precise. This rarely helps anything. We are usually more interested in whether the algorithm converged to a local extremum rather than the global one. A way to check that is by permuting the starting conditions for whatever solver you have: they should all lead to the same optimum. Another possibility is that the algorithm diverges rather than converges. This is usually evidenced by ludicrous estimates: but it seems to be worth repeating: you have to actually look at the output of whatever estimate you have and ask if it makes sense. Sometimes, there are certain smoothness conditions at the global maximum (or minimum) that need to hold for the solution to be unique. A singular Hessian or expected information will evidence some violation along these lines.
For MCMC routines, varying the seed, the number of iterations, and the length of burn in sometimes has an impact on estimates.
Can anything more be said in general, without knowing what algorithm you're using? Not really.
