Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2511.16007 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917095510376448 |
|---|---|
| author | Zhong-bao, Wang Zhong-cheng, Zhang |
| author_facet | Zhong-bao, Wang Zhong-cheng, Zhang |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_16007 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Single-loop variance reduction methods in Bregman setups for finite-sum structured variational inequalities Zhong-bao, Wang Zhong-cheng, Zhang Optimization and Control 90C15 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. |
| title | Single-loop variance reduction methods in Bregman setups for finite-sum structured variational inequalities |
| topic | Optimization and Control 90C15 |
| url | https://arxiv.org/abs/2511.16007 |