Adaptive Delayed-Update Cyclic Algorithm for Variational Inequalities

Cyclic block coordinate methods are widely used in practice for their simplicity and strong empirical performance. Yet, their theoretical behavior is challenging to explain, and setting their step sizes$-$beyond classical coordinate descent for minimization$-$requires careful tuning or line-search machinery. In this work, we develop $\text{ADUCA}$ (Adaptive Delayed-Update Cyclic Algorithm), a cyclic algorithm addressing a broad class of Minty variational inequalities with monotone Lipschitz operators. $\text{ADUCA}$ is parameter-free and locally adaptive: it requires no global or block-wise Lipschitz constants, it uses no per-epoch line search, and it adapts to local problem geometry. A key feature of the algorithm is using operator information delayed by a full cycle, which makes the algorithm compatible with parallel and distributed implementations, and attractive due to weakened synchronization requirements across blocks. We prove that $\text{ADUCA}$ attains (near) optimal global oracle complexity as a function of target error $ϵ>0$, scaling with $1/ϵ$ for monotone operators, or with ${\log }^2(1/ϵ)$ for operators that are strongly monotone.