Many important learning algorithms, such as stochastic gradient methods, are often deployed to solve nonlinear problems on Riemannian manifolds. Motivated by these applications, we propose a family of Riemannian algorithms generalizing and extending the seminal stochastic approximation framework of Robbins and Monro. Compared to their Euclidean counterparts, Riemannian iterative algorithms are much less understood due to the lack of a global linear structure on the manifold. We overcome this difficulty by introducing an extended Fermi coordinate frame which allows us to map the asymptotic behavior of the proposed Riemannian Robbins-Monro (RRM) class of algorithms to that of an associated deterministic dynamical system under very mild assumptions on the underlying manifold. In so doing, we provide a general template of almost sure convergence results that mirrors and extends the existing theory for Euclidean Robbins-Monro schemes, albeit with a significantly more involved analysis that requires a number of new geometric ingredients. We showcase the flexibility of the proposed RRM framework by using it to establish the convergence of a retraction-based analogue of the popular optimistic / extra-gradient methods for solving minimization problems and games, and we provide a unified treatment for their convergence.
翻译:许多重要的学习算法,例如Stochatic 梯度方法,常常被运用于解决里曼尼方块的非线性问题。根据这些应用,我们提出一套里曼式算法,以概括和扩展Robbins和Monro的原始随机近似框架。与欧洲的对等方相比,里曼尼式迭代式算法由于在方块上缺乏全球线性结构而远不那么为人所理解。我们通过引入一个扩大的Fermi协调框架克服了这一困难,这个框架使我们能够根据这些应用,将拟议的里曼尼罗宾斯-蒙罗(RRM)类算法的无线性行为映射到相关确定性动态系统的无线性。在这样做时,我们提供了一个几乎可以肯定的趋同结果的总模板,它反映和扩展了Euclidean Robins-Monro 计划的现有理论,尽管涉及的更多分析,需要一系列新的地理测量要素。我们展示了拟议的RM框架的灵活性,方法是利用它来建立回式的趋同式模型的趋同方法,以便解决我们最起码的模拟的模拟的模拟的模拟的摩化和最接近性处理。