{"ID":2838878,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2511.16007","arxiv_id":"2511.16007","title":"Single-loop variance reduction methods in Bregman setups for finite-sum structured variational inequalities","abstract":"In this paper, we address variational inequalities (VI) with a finite sum structure by proposing a novel single-loop variance-reduced algorithm that incorporates the Bregman distance. Under the monotone setting, we establish the almost sure convergence of the proposed algorithm and prove that it achieves the optimal complexity of $\\mathcal{O}\\left(\\frac{\\sqrt{M}}{\\varepsilon }\\right)$ for finding an $\\varepsilon$-gap. Furthermore, under the non-monotone setting, we derive a complexity of $\\mathcal{O}\\left(\\frac{1}{\\varepsilon^2 }\\right)$ of the algorithm. Our proposed method yields complexity results that either match or improve the state-of-the-art complexity bounds reported in existing literature. Notably, this work is the first to rigorously establish the linear convergence rate of the algorithm for solving finite-sum variational inequalities in Bregman setups. Finally, we report two numerical experiments to validate the effectiveness and practical performance of our method.","short_abstract":"In this paper, we address variational inequalities (VI) with a finite sum structure by proposing a novel single-loop variance-reduced algorithm that incorporates the Bregman distance. Under the monotone setting, we establish the almost sure convergence of the proposed algorithm and prove that it achieves the optimal co...","url_abs":"https://arxiv.org/abs/2511.16007","url_pdf":"https://arxiv.org/pdf/2511.16007v1","authors":"[\"Wang Zhong-bao\",\"Zhang Zhong-cheng\"]","published":"2025-11-20T03:07:01Z","proceeding":"math.OC","tasks":"[\"math.OC\"]","methods":"[]","has_code":false}