Adaptive Delayed-Update Cyclic Algorithm for Variational Inequalities
This addresses a theoretical bottleneck in optimization algorithms for researchers and practitioners, though it is incremental as it builds on existing cyclic methods.
The paper tackled the challenge of setting step sizes in cyclic block coordinate methods for variational inequalities by developing ADUCA, a parameter-free algorithm that achieves near-optimal oracle complexity, scaling with 1/ε for monotone operators or log²(1/ε) for strongly monotone ones.
Cyclic block coordinate methods are a fundamental class of first-order algorithms, widely used in practice for their simplicity and strong empirical performance. Yet, their theoretical behavior remains challenging to explain, and setting their step sizes -- beyond classical coordinate descent for minimization -- typically requires careful tuning or line-search machinery. In this work, we develop $\texttt{ADUCA}$ (Adaptive Delayed-Update Cyclic Algorithm), a cyclic algorithm addressing a broad class of Minty variational inequalities with monotone Lipschitz operators. $\texttt{ADUCA}$ is parameter-free: it requires no global or block-wise Lipschitz constants and uses no per-epoch line search, except at initialization. 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 $\texttt{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.