analiza aiqbench
This paper introduces GOMA, a novel optimization framework that achieves optimal convergence rates in both deterministic and stochastic min-max settings without relying on variance reduction or growing batches. By combining two-time-scale updates with an anchoring term, the method improves upon classical extragradient approaches which are often limited by high gradient query costs. This advancement is significant for researchers developing efficient algorithms for online learning and game theory applications where computational efficiency per iteration is critical.
Accelerated and Stable Convergence with Anchored Generalized Optimistic Method
arXiv:2606.21528v2 Announce Type: replace-cross Abstract: We study first-order methods for solving monotone variational inequalities arising in min-max optimization. Classical approaches such as the extragradient method rely on two gradient queries per iteration, which limits their analysis and applicability in the online and stochastic settings. We propose a family of Generalized Optimistic Methods with Anchoring (GOMA), which combine two-time-scale optimistic updates with an anchoring term inspired by Halpern iteration. In the deterministic setting, GOMA achieves the optimal accelerated last-iterate rate $O(1/k^2)$ on the squared gradient norm for monotone Lipschitz operators. In the stochastic setting with unbounded variance, a simplified single-call variant of GOMA achieves a last-iterate convergence rate of $O(1/\sqrt{k})$ on the squared gradient norm. To the best of our knowledge, this is the first such guarantee for stochastic monotone Lipschitz variational inequalities in the unconstrained setting without variance reduction or growing batches.
Abstract:We study first-order methods for solving monotone variational inequalities arising in min-max optimization. Classical approaches such as the extragradient method rely on two gradient queries per iteration, which limits their analysis and applicability in the online and stochastic settings. We propose a family of Generalized Optimistic Methods with Anchoring (GOMA), which combine two-time-scale optimistic updates with an anchoring term inspired by Halpern iteration. In the deterministic setting, GOMA achieves the optimal accelerated last-iterate rate $O(1/k^2)$ on the squared gradient norm for monotone Lipschitz operators. In the stochastic setting with unbounded variance, a simplified single-call variant of GOMA achieves a last-iterate convergence rate of $O(1/\sqrt{k})$ on the squared gradient norm. To the best of our knowledge, this is the first such guarantee for stochastic monotone Lipschitz variational inequalities in the unconstrained setting without variance reduction or growing batches.
Optimization and Control (math.OC); Computer Science and Game Theory (cs.GT); Machine Learning (cs.LG)
arXiv:2606.21528 [math.OC]
(or arXiv:2606.21528v2 [math.OC] for this version)
https://doi.org/10.48550/arXiv.2606.21528 Focus to learn more arXiv-issued DOI via DataCite
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Text integral sub licența deschisă a publicației · 239 cuvinte
Subiecte conexe
Quantum Machine Learning Overcomes Hardware Flaws with New Correction Method
Quantum Zeitgeist · 2 iun. 2026
Game Design Creativity evals
LessWrong · 12 oct. 2026
Expenditure Horizon: Measuring Optimization Ability, with an Application to NanoGPT
METR · 21 iul. 2026
Angles of attack for continual learning safety
LessWrong · 16 iun. 2026