Accelerated Algorithms for Monotone Inclusion and Constrained Nonconvex-Nonconcave Min-Max Optimization
Dec 2, 2022
Speakers
Argyris Oikonomou
Speaker · 0 followers
Weiqiang Zheng
Speaker · 0 followers
About
We study monotone inclusions and monotone variational inequalities, as well as their generalizations to non-monotone settings. We first show that the Extra Anchored Gradient (EAG) algorithm, originally proposed by [Yoon and Ryu, 2021] for unconstrained convex-concave min-max optimization, can be applied to solve the more general problem of Lipschitz monotone inclusion. More specifically, we prove that the EAG solves Lipschitz monotone inclusion problems with an accelerated convergence rate of O(1/T), which is optimal among all first-order methods [Diakonikolas, 2020, Yoon and Ryu, 2021]. Our second result is an accelerated forward-backward splitting algorithm (AS), which not only achieves the accelerated O(1/T) convergence rate for all monotone inclusion problems, but also exhibits the same accelerated rate for a family of general (non-monotone) inclusion problems that concern negative comonotone operators. As a special case of our second result, AS enjoys the O(1/T) convergence rate for solving a non-trivial class of nonconvex-nonconcave min-max optimization problems. Our analyses are based on simple potential function arguments, which might be useful for analysing other accelerated algorithms.We study monotone inclusions and monotone variational inequalities, as well as their generalizations to non-monotone settings. We first show that the Extra Anchored Gradient (EAG) algorithm, originally proposed by [Yoon and Ryu, 2021] for unconstrained convex-concave min-max optimization, can be applied to solve the more general problem of Lipschitz monotone inclusion. More specifically, we prove that the EAG solves Lipschitz monotone inclusion problems with an accelerated convergence rate of O(…
Organizer
NeurIPS 2022
Account · 953 followers
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
Constraining Gaussian Processes to Systems of Linear Ordinary Differential Equations
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Env-Aware Anomaly Detection: Ignore Style Changes, Stay True to Content!
Watch later
Stefan Smeu, …
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
A Bregman Learning Framework for Sparse Neural Networks
Watch later
Leon Bungert, …
Total of 2 viewers voted for saving the presentation to eternal vault which is 0.2%
Parameters or Privacy: A Provable Tradeoff Between Overparameterization and Membership Inference
Watch later
Jasper Tan, …
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Metal3D: Accurate prediction of transition metal ion location via deep learning
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Quantile Constrained Reinforcement Learning: A Reinforcement Learning Framework Constraining Outage Probability
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%