Last-Iterate Convergence of Optimistic Multiplicative Weights Update

-

B9 R2325

This talk will show how OMWU converges asymptotically for smooth convex-concave saddle-point problems, with a small enough constant learning rate.

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, and the literature presents only wrong proofs on this problem.

In this talk, I show that OMWU converges asymptotically for smooth convex-concave saddle-point problems, with a small enough constant learning rate. This result does not require uniqueness, strict complementarity, an error bound, or initialization near a solution. The main new ingredient of the proof was discovered with assistance from ChatGPT, and I will describe the LLM-assisted proof process as well.

Presenters

Brief Biography

Professor Francesco Orabona is a leading researcher in parameter-free online optimization. He joined KAUST from Boston University's Department of Electrical & Computer Engineering. Orabona earned his B.Sc. and M.S. in electrical engineering in 2003 from the University of Naples "Federico II", Italy, and his Ph.D. in electrical engineering in 2007 from the University of Genoa, Italy. 

Prior to joining KAUST, he held positions at several institutions including, Stony Brook University, Yahoo Research, the Toyota Technological Institute at Chicago (TTIC), the University of Milan and the Idiap Research Institute in Switzerland.

He has served as an area chair for several leading conferences, including the Conference on Neural Information Processing Systems (NeurIPS), the International Conference on Machine Learning (ICML), the Conference on Learning Theory (COLT) and the International Conference on Learning Representations (ICLR). Since 2022, he has been an associate editor of the IEEE Transactions on Information Theory.

Related People

Related Researchers