机器学习领域如何判定算法是否收敛（算法是否稳定）

最近在看ML的资料的时候看到有关算法收敛的讨论，然后有些资料并没有说明如何判定算法是否收敛，甚至有些资料中会将算法收敛和算法稳定性放在同等位置上来进行讨论，为此本文就这个问题进行一些讨论。

几年前参加实验室大师兄小利师兄的博士论文答辩的时候有答辩评委提出了这么一个问题，那就是该所提算法是否收敛，并且在论文中是如何讨论该算法的收敛性的，这个问题当时要师兄懵上了一会，最后师兄说这个算法的性能表现的趋势图在3000steps的时候已经逼近于某数值，然后证明该所提算法收敛。也正是这个时候才要我认识到这么一个问题，那就是如何判定某算法的收敛性。

经过我的调研后发现在ML领域对算法的收敛性的证明或说明有两种方法：

第一种：假设在理想状态或环境，给出一个简单的例子，比如强化学习领域给出一个5个状态的MDP，然后用表格表示法来表示，然后使用一些数学公式来进行推导和证明。该种方法在深度学习时代之前有一定的使用比例，但是在深度学习时代后就比较少了，该种方法往往需要使用大量的数学公式，但是最后得到的结论往往也只能适用于所举例的那种简单理想环境，与论文中真正的实验环境相距甚远，实际意义有限，难度较大，更多意义上是为了给论文增加所谓的“理论证明”而使论文更容易发表；

第二种：直接给出算法训练过程的性能表现的图，根据训练过程的图来指出算法在一定的训练steps后趋近于某一点，并且逼近过程比较平稳，从而给出算法收敛的证明。该种算法目前是ML领域最为可靠也最广被使用的方法，该方法简单，说明性强，适应几乎所有类型算法，而且该种方法更直观和形象。

对于算法稳定性，我认为并不能完全等价于算法收敛性的，算法收敛性指的是算法最终的性能表现是否收敛，而算法稳定性既指算法收敛同时也包括了算法训练过程中的波动情况，很大程度上来说算法稳定性等同于算法收敛性，但是二者并不是完全等价。