Reproduce “Adaptive Delayed-Update Cyclic Algorithm for Variational Inequalities” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Yi Wei, Xufeng Cai, Jelena Diakonikolas
An adaptive delayed-update cyclic algorithm (ADUCA) is introduced for generalized Minty variational inequalities, demonstrating optimal O(1/epsilon) and O(log(1/epsilon)) global oracle complexity for monotone and strongly monotone operators, respectively, without requiring global Lipschitz constants or per-epoch line searches. Its delayed-update mechanism enhances suitability for parallel and distributed computing.
Key insights
- Using operator information delayed by one full cycle ($\tilde{F}_k$) enables an explicit, cycle-wise step size selection that is parameter-free and locally adaptive.
- The proposed adaptive step size rule, based on consecutive-iterate ($L_k$) and within-cycle ($\hat{L}_k$) variation, effectively manages errors inherent in partial cyclic updates.
- The delayed-update mechanism intrinsically reduces synchronization needs, making the algorithm well-suited for parallel and distributed computing architectures.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.