Convergence of Proximal Point and Extragradient-Based Methods Beyond Monotonicity: the Case of Negative Comonotonicity
Jul 24, 2023
Speakers
Eduard Gorbunov
Speaker · 0 followers
Adrien Taylor
Speaker · 0 followers
Samuel Horváth
Speaker · 0 followers
Gauthier Gidel
Speaker · 0 followers
About
Algorithms for min-max optimization and variational inequalities are often studied under monotonicity assumptions. Motivated by non-monotone machine learning applications, we follow the line of works (Diakonikolas et al., 2021; Lee Kim, 2021; Pethick et al., 2022; Bohm,2022) aiming at going beyond monotonicity by considering the weaker negative comonotonicity assumption. In this work, we provide tight complexity analyses for the Proximal Point (PP), Extragradient (EG), and Optimistic Gradient (OG) methods in this setup, closing several questions on their working guarantees beyond monotonicity. In particular, we derive the first non-asymptotic convergence rates for PP under negative comonotonicity and star-negative comonotonicity and show their tightness via constructing worst-case examples; we also relax the assumptions for the last-iterate convergence guarantees for EG and OG and prove the tightness of the existing best-iterate guarantees for EG and OG via constructing counter-examples.Algorithms for min-max optimization and variational inequalities are often studied under monotonicity assumptions. Motivated by non-monotone machine learning applications, we follow the line of works (Diakonikolas et al., 2021; Lee Kim, 2021; Pethick et al., 2022; Bohm,2022) aiming at going beyond monotonicity by considering the weaker negative comonotonicity assumption. In this work, we provide tight complexity analyses for the Proximal Point (PP), Extragradient (EG), and Optimistic Gradient (O…
Like the format? Trust SlidesLive to capture your next event!
Professional recording and live streaming, delivered globally.
Sharing
Recommended Videos
Presentations on similar topic, category or speaker
Towards Learning to Imitate from a Single Video Demonstration
Watch later
Glen Berseth, …
Designing useful human input for robot learning
Watch later
Hiera: A Hierarchical Vision Transformer without the Bells-and-Whistles
Watch later
Constraint Reasoning Embedded Structured Prediction
Watch later
Nan Jiang, …
Model-Aware Contrastive Learning: Towards Escaping the Dilemmas
Watch later
FlexGen: High-Throughput Generative Inference of Large Language Models with a Single GPU
Watch later
Ying Sheng, …