Search papers, labs, and topics across Lattice.
This paper establishes that the Optimistic Multiplicative-Weights Update (OMWU) algorithm converges asymptotically for smooth convex-concave saddle-point problems, addressing a long-standing question in optimization. The findings indicate that OMWU's convergence does not depend on strict conditions such as uniqueness or initialization proximity to a solution, which broadens its applicability. A novel boundary argument, aided by insights from ChatGPT, is introduced to demonstrate that every cluster point adheres to the inactive-coordinate KKT inequalities.
OMWU's convergence for saddle-point problems is confirmed without the need for strict initialization or uniqueness conditions, expanding its potential use cases in optimization.
Optimistic Gradient Descent Ascent (OGDA) and Optimistic Multiplicative-Weights Update (OMWU) are two very popular algorithms to solve convex/concave saddle-point problems, where OMWU is the non-Euclidean, entropic version of OGDA. It is known since the '80s that the last iterate of OGDA asymptotically converges to a saddle point in smooth problems. On the other hand, it is unknown if OMWU has the same property. In this paper, I show that OMWU converges asymptotically for smooth convex-concave saddle-point problems, with a small enough constant learning rate. The result does not require uniqueness, strict complementarity, an error bound, or initialization near a solution. The main new ingredient is a boundary argument showing that every cluster point satisfies the inactive-coordinate KKT inequalities. The boundary argument was discovered with assistance from ChatGPT and is documented in the appendix.
