A Unifying Framework of Accelerated First-Order Approach to Strongly Monotone Variational Inequalities

MaRDI QIDQ6363954zbMATH OpenFDO

Authors Kevin X. D. Huang, Shuzhong Zhang

Publication date 28 March 2021

Mathematics Subject Classification ID

Numerical methods for variational inequalities and related problems (65K15) Convex programming (90C25) Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) (90C33)

Abstract: In this paper, we propose a unifying framework incorporating several momentum-related search directions for solving strongly monotone variational inequalities. The specific combinations of the search directions in the framework are made to guarantee the optimal iteration complexity bound of $mathcalOleft(kappaln(1/epsilon)ight)$ to reach an $epsilon$-solution, where $kappa$ is the condition number. This framework provides the flexibility for algorithm designers to train -- among different parameter combinations -- the one that best suits the structure of the problem class at hand. The proposed framework includes the following iterative points and directions as its constituents: the extra-gradient, the optimistic gradient descent ascent (OGDA) direction (aka "optimism"), the "heavy-ball" direction, and Nesterov's extrapolation points. As a result, all the afore-mentioned methods become the special cases under the general scheme of extra points. We also specialize this approach to strongly convex minimization, and show that a similar extra-point approach achieves the optimal iteration complexity bound of $mathcalO(sqrtkappaln(1/epsilon))$ for this class of problems.

This page was built for publication: A Unifying Framework of Accelerated First-Order Approach to Strongly Monotone Variational Inequalities

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6363954)