# Accelerated Multiplicative Weights Update Avoids Saddle Points almost always

arXiv: https://arxiv.org/abs/2204.11407 · HTML: https://mlsanity.com/paper/2204.11407/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 21 references that are in the map.
- First posted on arXiv 25 Apr 2022.

## Builds on (most cited first, 11 of 11)

- [How to Escape Saddle Points Efficiently](https://mlsanity.com/paper/1703.00887/) (2017)
- [Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decomposition](https://mlsanity.com/paper/1503.02101/) (2015)
- [Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descent](https://mlsanity.com/paper/1711.10456/) (2017)
- [First-order methods almost always avoid saddle points: the case of vanishing step-sizes](https://mlsanity.com/paper/1906.07772/) (2019)
- [Gradient Descent Only Converges to Minimizers: Non-Isolated Critical Points and Invariant Regions](https://mlsanity.com/paper/1605.00405/) (2016)
- [Escaping from saddle points on Riemannian manifolds](https://mlsanity.com/paper/1906.07355/) (2019)
- [Efficiently escaping saddle points on manifolds](https://mlsanity.com/paper/1906.04321/) (2019)
- [Heavy-ball Algorithms Always Escape Saddle Points](https://mlsanity.com/paper/1907.09697/) (2019)
- [Towards Riemannian Accelerated Gradient Methods](https://mlsanity.com/paper/1806.02812/) (2018)
- [Multiplicative Weights Update as a Distributed Constrained Optimization Algorithm: Convergence to Second-order Stationary Points Almost Always](https://mlsanity.com/paper/1810.05355/) (2018)
- [SNAP: Finding Approximate Second-Order Stationary Solutions Efficiently for Non-convex Linearly Constrained Problems](https://mlsanity.com/paper/1907.04450/) (2019)

## Abstract (arXiv)

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.