Accelerated Multiplicative Weights Update Avoids Saddle Points almost always
Yi Feng, Ioannis Panageas, Xiao Wang
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.