算法收敛性的证明。
很多优化算法,以及机器学习算法都可以抽象成
或者如果数据带有噪音,再加入一个Martingale过程的扰动
前者是确定性动态系统,而后者是随机动态系统。算法的收敛就取决于寻找对应的李雅普诺夫函数了。
具体例子,比如TCP协议重的congestion control(堵塞控制)。congestion control的目标可以看作是受约束的用户utility maximization(效用最大化)。而congestion control的过程就可以看作是用算法寻找utility maximization的问题的最优点。
一篇比较新的paper:
A second order primal-dual method for nonsmooth convex composite optimization
以及比较早的
The O.D.E. Method for Convergence of Stochastic Approximation and Reinforcement Learning
Stability of primal–dual gradient dynamics and applications to network optimization