Processing math: 100%
Skip to yearly menu bar Skip to main content


Poster

Efficient Interpolation between Extragradient and Proximal Methods for Weak MVIs

Thomas Pethick · Ioannis Mavrothalassitis · Volkan Cevher

Hall 3 + Hall 2B #372
[ ]
Fri 25 Apr midnight PDT — 2:30 a.m. PDT

Abstract: We study nonmonotone games satisfying the weak Minty variational inequality (MVI) with parameter ρ(1L,), where L is the Lipschitz constant of the gradient operator. An error corrected version of the inexact proximal point algorithm is proposed, with which we establish the first O(1/ϵ) rate for the entire range ρ(1L,), thus removing a logarithmic factor compared with the complexity of existing methods. The scheme automatically selects the needed accuracy for the proximal computation, and can recover the relaxed extragradient method when ρ>12L and the relaxed proximal point algorithm (rPPA) when ρ>1L. Due to the error correction, the scheme inherits the strong properties of the _exact_ rPPA. Specifically, we show that linear convergence is automatically achieved under appropriate conditions. Tightness for the range of ρ is established through a lower bound for rPPA. Central to the algorithmic construction is a halfspace projection, where the key insight is that the allowed error tolerance can both be used to correct for the proximal approximation and to enlarge the problem class.

Live content is unavailable. Log in and register to view live content