# Adaptive Delayed-Update Cyclic Algorithm for Variational Inequalities

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 26 of its 50 references that are in the map.
- First posted on arXiv 31 Mar 2026.

## Builds on (most cited first, 26 of 26)

- [Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization](https://mlsanity.com/paper/2011.00364/) (2020)
- [Adaptive Gradient Descent without Descent](https://mlsanity.com/paper/1910.09529/) (2019)
- [Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems](https://mlsanity.com/paper/1808.02901/) (2018)
- [Halpern Iteration for Near-Optimal and Parameter-Free Monotone Inclusion and Strong Solutions to Variational Inequalities](https://mlsanity.com/paper/2002.08872/) (2020)
- [Golden Ratio Algorithms for Variational Inequalities](https://mlsanity.com/paper/1803.08832/) (2018)
- [Simple and optimal methods for stochastic variational inequalities, I: operator extrapolation](https://mlsanity.com/paper/2011.02987/) (2020)
- [A Universal Algorithm for Variational Inequalities Adaptive to Smoothness and Noise](https://mlsanity.com/paper/1902.01637/) (2019)
- [Adaptive Proximal Gradient Method for Convex Optimization](https://mlsanity.com/paper/2308.02261/) (2023)
- [Adaptive proximal algorithms for convex optimization under local Lipschitz continuity of the gradient](https://mlsanity.com/paper/2301.04431/) (2023)
- [Adaptive Gradient Methods for Constrained Convex Optimization and Variational Inequalities](https://mlsanity.com/paper/2007.08840/) (2020)
- [A simple uniformly optimal method without line search for convex optimization](https://mlsanity.com/paper/2310.10082/) (2023)
- [Adaptive and Universal Algorithms for Variational Inequalities with Optimal Convergence](https://mlsanity.com/paper/2010.07799/) (2020)
- [Beyond the Golden Ratio for Variational Inequality Algorithms](https://mlsanity.com/paper/2212.13955/) (2022)
- [Coordinate Linear Variance Reduction for Generalized Linear Programming](https://mlsanity.com/paper/2111.01842/) (2021)
- [Cyclic Block Coordinate Descent With Variance Reduction for Composite Nonconvex Optimization](https://mlsanity.com/paper/2212.05088/) (2022)
- [A first-order primal-dual method with adaptivity to local smoothness](https://mlsanity.com/paper/2110.15148/) (2021)
- [Cyclic Coordinate Update Algorithms for Fixed-Point Problems: Analysis and Applications](https://mlsanity.com/paper/1611.02456/) (2016)
- [Projected gradient methods for nonconvex and stochastic smooth optimization: new complexities and auto-conditioned stepsizes](https://mlsanity.com/paper/2412.14291/) (2024)
- [On stochastic mirror-prox algorithms for stochastic Cartesian variational inequalities: randomized block coordinate and optimal averaging schemes](https://mlsanity.com/paper/1610.08195/) (2016)
- [Nesterov Finds GRAAL: Optimal and Adaptive Gradient Method for Convex Optimization](https://mlsanity.com/paper/2507.09823/) (2025)
- [Cyclic Coordinate Dual Averaging with Extrapolation](https://mlsanity.com/paper/2102.13244/) (2021)
- [Accelerated Cyclic Coordinate Dual Averaging with Extrapolation for Composite Convex Optimization](https://mlsanity.com/paper/2303.16279/) (2023)
- [On the convergence of proximal gradient methods for convex simple bilevel optimization](https://mlsanity.com/paper/2305.03559/) (2023)
- [Auto-conditioned primal-dual hybrid gradient method and alternating direction method of multipliers](https://mlsanity.com/paper/2410.01979/) (2024)
- [An Adaptive and Parameter-Free Nesterov's Accelerated Gradient Method for Convex Optimization](https://mlsanity.com/paper/2505.11670/) (2025)
- [A Block Coordinate and Variance-Reduced Method for Generalized Variational Inequalities of Minty Type](https://mlsanity.com/paper/2411.00979/) (2024)

## Abstract (arXiv)

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 textttADUCA (Adaptive Delayed-Update Cyclic Algorithm), a cyclic algorithm addressing a broad class of Minty variational inequalities with monotone Lipschitz operators. textttADUCA 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 textttADUCA attains (near) optimal global oracle complexity as a function of target error ε >0, scaling with 1/ε for monotone operators, or with log2(1/ε) for operators that are strongly monotone.