Adaptive Delayed-Update Cyclic Algorithm for Variational Inequalities
Not on the map. Why?
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.
Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 26 of its 50 references that are in the map. First posted on arXiv 31 Mar 2026.
Builds on
26 of 50 references.
References · 26
- 2020Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimizationcited by 94
- 2019Adaptive Gradient Descent without Descentcited by 79
- 2018Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problemscited by 75
- 2020Halpern Iteration for Near-Optimal and Parameter-Free Monotone Inclusion and Strong Solutions to Variational Inequalitiescited by 60
- 2018Golden Ratio Algorithms for Variational Inequalitiescited by 38
- 2020Simple and optimal methods for stochastic variational inequalities, I: operator extrapolationcited by 35
- 2019A Universal Algorithm for Variational Inequalities Adaptive to Smoothness and Noisecited by 26
- 2023Adaptive Proximal Gradient Method for Convex Optimizationcited by 21
- 2023Adaptive proximal algorithms for convex optimization under local Lipschitz continuity of the gradientcited by 19
- 2020Adaptive Gradient Methods for Constrained Convex Optimization and Variational Inequalitiescited by 18
- 2023A simple uniformly optimal method without line search for convex optimizationcited by 18
- 2020Adaptive and Universal Algorithms for Variational Inequalities with Optimal Convergencecited by 12
14 more
- 2022Beyond the Golden Ratio for Variational Inequality Algorithmscited by 12
- 2021Coordinate Linear Variance Reduction for Generalized Linear Programmingcited by 10
- 2022Cyclic Block Coordinate Descent With Variance Reduction for Composite Nonconvex Optimizationcited by 9
- 2021A first-order primal-dual method with adaptivity to local smoothnesscited by 7
- 2016Cyclic Coordinate Update Algorithms for Fixed-Point Problems: Analysis and Applicationscited by 6
- 2024Projected gradient methods for nonconvex and stochastic smooth optimization: new complexities and auto-conditioned stepsizescited by 6
- 2016On stochastic mirror-prox algorithms for stochastic Cartesian variational inequalities: randomized block coordinate and optimal averaging schemescited by 5
- 2025Nesterov Finds GRAAL: Optimal and Adaptive Gradient Method for Convex Optimizationcited by 4
- 2021Cyclic Coordinate Dual Averaging with Extrapolationcited by 3
- 2023Accelerated Cyclic Coordinate Dual Averaging with Extrapolation for Composite Convex Optimizationcited by 3
- 2023On the convergence of proximal gradient methods for convex simple bilevel optimizationcited by 2
- 2024Auto-conditioned primal-dual hybrid gradient method and alternating direction method of multiplierscited by 2
- 2025An Adaptive and Parameter-Free Nesterov's Accelerated Gradient Method for Convex Optimizationcited by 2
- 2024A Block Coordinate and Variance-Reduced Method for Generalized Variational Inequalities of Minty Typecited by 1
Built on by
Not cited yet.