# A Block Coordinate and Variance-Reduced Method for Generalized Variational Inequalities of Minty Type

arXiv: https://arxiv.org/abs/2411.00979 · HTML: https://mlsanity.com/paper/2411.00979/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Nov 2024.

## Built on by (most cited first, 1 of 1)

- [Adaptive Delayed-Update Cyclic Algorithm for Variational Inequalities](https://mlsanity.com/paper/2603.29128/) (2026)

## Abstract (arXiv)

Block coordinate methods have been extensively studied for minimization problems, where they come with significant complexity improvements whenever the considered problems are compatible with block decomposition and, moreover, block Lipschitz parameters are highly nonuniform. For the more general class of variational inequalities with monotone operators, essentially none of the existing methods transparently shows potential complexity benefits of using block coordinate updates in such settings. Motivated by this gap, we develop a new randomized block coordinate method and study its oracle complexity and runtime. We prove that in the setting where block Lipschitz parameters are highly nonuniform -- the main setting in which block coordinate methods lead to high complexity improvements in any of the previously studied settings -- our method can lead to complexity improvements by a factor order-m, where m is the number of coordinate blocks. The same method further applies to the more general problem with a finite-sum operator with m components, where it can be interpreted as performing variance reduction. Compared to the state of the art, the method leads to complexity improvements up to a factor √m, obtained when the component Lipschitz parameters are highly nonuniform.