A Modern Treatise on Variational Inequality Problems: Structures, Algorithms, and Iteration Complexities

Abstract

In this thesis, we study the variational inequality (VI) problem with the methodology of designing efficient (or optimal) algorithms and analyzing their (sample/gradient) iteration complexities. In particular, we aim to explore the hidden structures in VI that have not been (fully) studied before and use them as insights to guide the development of new optimal algorithms that align with the modern research trends in both VI and optimization. We start from the first-order methods, where acceleration has been established in algorithms such as extra-gradient method, optimistic gradient descent ascent method, and dual extrapolation method. These methods are known as optimal in the sense that they match the lower iteration complexity bounds established for first-order methods in (strongly) monotone VI. We observe that these acceleration schemes in VI, together with the acceleration schemes used in optimization such as Nesterov's acceleration, share a common structure: using additional sequence(s), which we refer to it as ``extra points'', to help improve the convergence of the main sequence. We then propose a general guideline, called the extra-point approach, to construct optimal first-order methods via a more systematic way, which provides flexibility in adopting a variety of extra points/sequences such that the lower bounds take effect. Moving towards high-order methods, research before has relied on using high-order Taylor approximation and an iterative binary-search in solving the subproblems. We show that both of them are not necessary in developing high-order methods, and the key lies in satisfying a high-order Lipschitz bound for any approximation operator used in the subroutine, as well as an appropriate order of regularization to eliminate the needs of binary-search. The proposed unifying framework largely relieves the demand on the complicated analysis derived for different methods and allows us to focus more on the problem structure to design a suitable approximation operator in the algorithm. We also investigate stochastic algorithms for VI, mainly focusing on the stochastic approximation (SA) approach. We propose stochastic extensions of two new first-order methods, which could be viewed as special instances following the aforementioned extra-point approach, and show that optimal iteration complexities can be established for them, in both situations where the stochastic errors are bounded separately or they are reduced together with the deterministic terms. Application is discussed using the example of black-box saddle point problem where even the function values can only be estimated with noises. Using a smoothing technique, we show that by constructing the stochastic zeroth-order gradients, the previous schemes can be readily applied with the guarantee on sample iteration complexities. Another aspect of stochasticity is discussed following the similar line of research, where we study the VI problems with the finite-sum structure. In addition, such finite-sum structure consists of both general vector mappings and gradient mappings. Developments in variance reduced algorithms for both finite-sum optimization and finite-sum VI have been found recently, but none has focused on finite-sum VI with optimization structures. We propose two algorithms for both monotone and strongly monotone VI that explicitly make use of such optimization structure and demonstrate that they indeed serve as a bridge between these two problem classes and are able to perform better than general variance reduced VI algorithms when such structure is actually present. We show that the saddle point reformulation of a finite-sum optimization with finite-sum constraints immediately take the aforementioned forms in VI, where applications are commonly seen in Neyman-Pearson classification in machine learning. Finally, the research in this thesis is extended to non-monotone VI and the solution methods for solving it. Without the monotonicity, another (weaker) global property of the VI problem, the existence of Minty solution, comes to play a central role in the convergence of accelerated projection-type methods. With a slightly worse iteration complexity than the monotone VI, we show that how a general high-order extra-gradient-type method using the concept of the aforementioned approximation can converge. Furthermore, when the existence of Minty solution is no longer assumed, very little can be said in general about the convergence of these projection-type methods. Alternatively, we use these methods as starting points and derive sufficient conditions that characterize various structures of VI where they can converge with guaranteed iteration complexity bounds. This approach allows us to extend our study to potentially broader VI problem classes that have no monotonicity nor Minty solutions.