Extragradient-Type Methods for Large-Scale Variational Inequalities

The thesis focuses on developing efficient extragradient-type methods for solving a class of nonlinear inclusions, establishing connections with variational inequalities and the large-scale optimization stemming from modern machine learning applications. This thesis consists of five chapters. Chapter 1 is the introduction, presenting motivation, related work, and preliminary results on extragradient-type schemes. Chapter 2 aims at further studying and improving upon the convergence properties of the classical extragradient methods. Specifically, we generalize and extend the extragradient scheme to solve co-monotone inclusions. We establish a sublinear averaged iterate convergence rate of the squared operator norm. While dealing with the high-dimensional datasets, we develop a randomized block-coordinate extragradient method, named RPEG, and establish the best-iterate convergence results. In Chapter 3, we introduce a new class of self-tuning algorithms to solve a root-finding problem involving a maximal monotone and Lipschitz continuous operator, with applications in convex optimization, minimax saddle point problems and variational inequalities. Our methods are adaptive to the unknown, problem specific parameters, such as the Lipschitz constant and the variance of the stochastic operator. Unlike prior work, our approach does not rely on restrictive assumptions, such as a bounded domain, boundedness of the operator or a light-tailed distribution. We illustrate the effectiveness of the proposed algorithms through numerical experiments on saddle point problems. Our results suggest that the adaptive step sizes automatically take advantage of the structure of the noise and observe improved convergence in certain settings, such as when the strong growth condition holds. Chapter 4 aims to study a smooth operator exhibiting the weak Minty variational condition. Stochastic extragradient-type schemes for weak Minty variational inequalities (MVI) pose significant challenges due to bias introduced by randomness in the extrapolation step as well as the inability to employ diminishing extrapolation step sizes. Current convergence analyses of SEG methods usually rely on large batch sizes or restrictive assumptions of stochastic gradients, i.e., Lipschitz continuity of stochastic operators in mean or uniform boundedness of the variances, limiting their practicality. Alternatively, we introduce the adaptive sampling optimistic gradient(ASOptimistic) method by incorporating an augmented inner product test into the optimistic gradient scheme to dynamically adjust the sample size, which focuses on improving sample efficiency and searching for a descent direction with high probability. Specifically, we establish a sublinear best-iterate convergence rate of squared operator norm under the assumptions of Lipschitz continuity and weak MVI. Under the error bound condition, we obtain a linear last iterate convergence of distance to the solution set, matching the best convergence result in the deterministic regime. Preliminary numerical results will be presented, demonstrating that EG-type algorithms can extend the advantages of adaptive sampling strategies beyond monotonicity to solve a much wider range of optimization problems. Finally, we summarize our contribution and outline potential future research directions in Chapter 5.