Efficient Interpolation Between Extragradient And Proximal Methods For Weak MVIS

We study nonmonotone games satisfying the weak Minty variational inequality (MVI) with parameter ρ ∈ (− 1 /L, ∞), 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 ρ ∈ (− 1 /L, ∞), 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 ρ > − 1 /2L and the relaxed proximal point algorithm (rPPA) when ρ > − 1 /L. 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.