High-Order Reduced-Gradient Methods for Composite Variational Inequalities

This paper can be seen as an attempt of rethinking the em Extra-Gradient Philosophy for solving Variational Inequality Problems. We show that the properly defined em Reduced Gradients can be used instead for finding approximate solutions to Composite Variational Inequalities by the higher-order schemes. Our methods are optimal since their performance is proportional to the lower worst-case complexity bounds for corresponding problem classes. They enjoy the provable hot-start capabilities even being applied to minimization problems. The primal version of our schemes demonstrates a linear rate of convergence under an appropriate uniform monotonicity assumption.