  In this paper, we propose a general extra-gradient scheme for solving
monotone variational inequalities (VI), referred to here as Approximation-based
Regularized Extra-gradient method (ARE). The first step of ARE solves a VI
subproblem with an approximation operator satisfying a $p^{th}$-order Lipschitz
bound with respect to the original mapping, further coupled with the gradient
of a $(p+1)^{th}$-order regularization. The optimal global convergence is
guaranteed by including an additional extra-gradient step, while a
$p^{th}$-order superlinear local convergence is shown to hold if the VI is
strongly monotone. The proposed ARE is inclusive and general, in the sense that
a variety of solution methods can be formulated within this framework as
different manifestations of approximations, and their iteration complexities
would follow through in a unified fashion. The ARE framework relates to the
first-order methods, while opening up possibilities to developing higher-order
methods specifically for structured problems that guarantee the optimal
iteration complexity bounds.
