论文标题
使用Wasserstein Divergence收敛递归随机算法
Convergence of Recursive Stochastic Algorithms using Wasserstein Divergence
论文作者
论文摘要
本文基于迭代的随机操作者理论开发了一个统一的框架，以分析恒定步骤的汇聚递归随机算法（RSA）的收敛性。 RSA使用随机化来有效计算期望，因此它们的迭代形成随机过程。我们分析的关键思想是将RSA提升为适当的高维空间，然后将其表示为等效的马尔可夫链。我们研究了马尔可夫链的分布的收敛性，而不是确定马尔可夫链的收敛性（可能不会在恒定步骤中收敛）。为了研究这一点，我们定义了Wasserstein Divergence的新概念。我们表明，如果迭代在马尔可夫链中的分布满足了瓦斯恒星差异方面的收缩特性，那么马尔可夫链就承认了一个不变的分布。我们表明，可以使用此框架来理解大型恒定步骤的RSA家族的融合，我们提供了几个详细的示例。
This paper develops a unified framework, based on iterated random operator theory, to analyze the convergence of constant stepsize recursive stochastic algorithms (RSAs). RSAs use randomization to efficiently compute expectations, and so their iterates form a stochastic process. The key idea of our analysis is to lift the RSA into an appropriate higher-dimensional space and then express it as an equivalent Markov chain. Instead of determining the convergence of this Markov chain (which may not converge under constant stepsize), we study the convergence of the distribution of this Markov chain. To study this, we define a new notion of Wasserstein divergence. We show that if the distribution of the iterates in the Markov chain satisfy a contraction property with respect to the Wasserstein divergence, then the Markov chain admits an invariant distribution. We show that convergence of a large family of constant stepsize RSAs can be understood using this framework, and we provide several detailed examples.
