论文标题
加速的倍增权重更新几乎总是会避免鞍点
Accelerated Multiplicative Weights Update Avoids Saddle Points almost always
论文作者
论文摘要
我们认为非凸优化问题具有简单的乘积。解决此类问题的一种常用算法是乘法权重更新（MWU），这是一种在游戏理论，机器学习和多代理系统中广泛使用的算法。尽管众所周知，MWU避免了鞍点，但仍有一个未解决的问题：“ MWU是否有加速版本可以避免鞍点？”在本文中，我们为上述问题提供了积极的答案。我们提供了基于Riemannian加速梯度下降的加速MWU，并证明了Riemannian加速梯度下降，因此加速MWU，几乎总是避免鞍点。
We consider non-convex optimization problems with constraint that is a product of simplices. A commonly used algorithm in solving this type of problem is the Multiplicative Weights Update (MWU), an algorithm that is widely used in game theory, machine learning and multi-agent systems. Despite it has been known that MWU avoids saddle points, there is a question that remains unaddressed:"Is there an accelerated version of MWU that avoids saddle points provably?" In this paper we provide a positive answer to above question. We provide an accelerated MWU based on Riemannian Accelerated Gradient Descent, and prove that the Riemannian Accelerated Gradient Descent, thus the accelerated MWU, almost always avoid saddle points.
