{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,8,7]],"date-time":"2024-08-07T07:39:19Z","timestamp":1723016359282},"publisher-location":"California","reference-count":0,"publisher":"International Joint Conferences on Artificial Intelligence Organization","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022,7]]},"abstract":"<jats:p>We consider nonconvex optimization problem 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, avoid saddle points.<\/jats:p>","DOI":"10.24963\/ijcai.2022\/252","type":"proceedings-article","created":{"date-parts":[[2022,7,15]],"date-time":"2022-07-15T22:55:56Z","timestamp":1657925756000},"page":"1811-1817","source":"Crossref","is-referenced-by-count":1,"title":["Accelerated Multiplicative Weights Update Avoids Saddle Points Almost Always"],"prefix":"10.24963","author":[{"given":"Yi","family":"Feng","sequence":"first","affiliation":[{"name":"Shanghai University of Finance and Economics"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ioannis","family":"Panageas","sequence":"additional","affiliation":[{"name":"UC Irvine"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xiao","family":"Wang","sequence":"additional","affiliation":[{"name":"Shanghai University of Finance and Economics"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"10584","event":{"number":"31","sponsor":["International Joint Conferences on Artificial Intelligence Organization (IJCAI)"],"acronym":"IJCAI-2022","name":"Thirty-First International Joint Conference on Artificial Intelligence {IJCAI-22}","start":{"date-parts":[[2022,7,23]]},"theme":"Artificial Intelligence","location":"Vienna, Austria","end":{"date-parts":[[2022,7,29]]}},"container-title":["Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence"],"original-title":[],"deposited":{"date-parts":[[2022,7,18]],"date-time":"2022-07-18T07:08:37Z","timestamp":1658128117000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ijcai.org\/proceedings\/2022\/252"}},"subtitle":[],"proceedings-subject":"Artificial Intelligence Research Articles","short-title":[],"issued":{"date-parts":[[2022,7]]},"references-count":0,"URL":"https:\/\/doi.org\/10.24963\/ijcai.2022\/252","relation":{},"subject":[],"published":{"date-parts":[[2022,7]]}}}