Single-loop variance reduction methods in Bregman setups for finite-sum structured variational inequalities Article Swipe

PDF

Zhongbao Wang ·

YOU? · · 2025 · Open Access · · DOI: https://doi.org/10.48550/arxiv.2511.16007

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.

Related Topics

Poverty Reduction

Defense Threat Reduction Agency

Inflation Reduction Act

Drag Reduction System

Orchestrated Objective Reduction

Bias–Variance Tradeoff

Nonlinear Dimensionality Reduction

Harm Reduction

Multivariate Analysis Of Variance

Carbonyl Reduction

Concepts

No concepts available.

Metadata

Type: preprint
Landing Page: http://arxiv.org/abs/2511.16007
PDF: https://arxiv.org/pdf/2511.16007
OA Status: green
OpenAlex ID: https://openalex.org/W4416550250

All OpenAlex metadata

Raw OpenAlex JSON

OpenAlex ID: https://openalex.org/W4416550250

Canonical identifier for this work in OpenAlex
DOI: https://doi.org/10.48550/arxiv.2511.16007

Digital Object Identifier
Title: Single-loop variance reduction methods in Bregman setups for finite-sum structured variational inequalities

Work title
Type: preprint

OpenAlex work type
Publication year: 2025

Year of publication
Publication date: 2025-11-20

Full publication date if available
Authors: Zhongbao Wang

List of authors in order
Landing page: https://arxiv.org/abs/2511.16007

Publisher landing page
PDF URL: https://arxiv.org/pdf/2511.16007

Direct link to full text PDF
Open access: Yes

Whether a free full text is available
OA status: green

Open access status per OpenAlex
OA URL: https://arxiv.org/pdf/2511.16007

Direct OA link when available
Cited by: 0

Total citation count in OpenAlex

Full payload

id	https://openalex.org/W4416550250
doi	https://doi.org/10.48550/arxiv.2511.16007
ids.doi	https://doi.org/10.48550/arxiv.2511.16007
ids.openalex	https://openalex.org/W4416550250
fwci
type	preprint
title	Single-loop variance reduction methods in Bregman setups for finite-sum structured variational inequalities
biblio.issue
biblio.volume
biblio.last_page
biblio.first_page
is_xpac	False
apc_list
apc_paid
language
locations[0].id	pmh:oai:arXiv.org:2511.16007
locations[0].is_oa	True
locations[0].source.id	https://openalex.org/S4306400194
locations[0].source.issn
locations[0].source.type	repository
locations[0].source.is_oa	True
locations[0].source.issn_l
locations[0].source.is_core	False
locations[0].source.is_in_doaj	False
locations[0].source.display_name	arXiv (Cornell University)
locations[0].source.host_organization	https://openalex.org/I205783295
locations[0].source.host_organization_name	Cornell University
locations[0].source.host_organization_lineage	https://openalex.org/I205783295
locations[0].license
locations[0].pdf_url	https://arxiv.org/pdf/2511.16007
locations[0].version	submittedVersion
locations[0].raw_type	text
locations[0].license_id
locations[0].is_accepted	False
locations[0].is_published	False
locations[0].raw_source_name
locations[0].landing_page_url	http://arxiv.org/abs/2511.16007
locations[1].id	doi:10.48550/arxiv.2511.16007
locations[1].is_oa	True
locations[1].source.id	https://openalex.org/S4306400194
locations[1].source.issn
locations[1].source.type	repository
locations[1].source.is_oa	True
locations[1].source.issn_l
locations[1].source.is_core	False
locations[1].source.is_in_doaj	False
locations[1].source.display_name	arXiv (Cornell University)
locations[1].source.host_organization	https://openalex.org/I205783295
locations[1].source.host_organization_name	Cornell University
locations[1].source.host_organization_lineage	https://openalex.org/I205783295
locations[1].license
locations[1].pdf_url
locations[1].version
locations[1].raw_type	article
locations[1].license_id
locations[1].is_accepted	False
locations[1].is_published
locations[1].raw_source_name
locations[1].landing_page_url	https://doi.org/10.48550/arxiv.2511.16007
indexed_in	arxiv, datacite
authorships[0].author.id	https://openalex.org/A5108063887
authorships[0].author.orcid	https://orcid.org/0000-0003-4665-124X
authorships[0].author.display_name	Zhongbao Wang
authorships[0].author_position	first
authorships[0].raw_author_name	Zhong-bao, Wang
authorships[0].is_corresponding	True
has_content.pdf	False
has_content.grobid_xml	False
is_paratext	False
open_access.is_oa	True
open_access.oa_url	https://arxiv.org/pdf/2511.16007
open_access.oa_status	green
open_access.any_repository_has_fulltext	False
created_date	2025-11-23T00:00:00
display_name	Single-loop variance reduction methods in Bregman setups for finite-sum structured variational inequalities
has_fulltext	False
is_retracted	False
updated_date	2025-11-28T17:08:19.954046
primary_topic
cited_by_count	0
locations_count	2
best_oa_location.id	pmh:oai:arXiv.org:2511.16007
best_oa_location.is_oa	True
best_oa_location.source.id	https://openalex.org/S4306400194
best_oa_location.source.issn
best_oa_location.source.type	repository
best_oa_location.source.is_oa	True
best_oa_location.source.issn_l
best_oa_location.source.is_core	False
best_oa_location.source.is_in_doaj	False
best_oa_location.source.display_name	arXiv (Cornell University)
best_oa_location.source.host_organization	https://openalex.org/I205783295
best_oa_location.source.host_organization_name	Cornell University
best_oa_location.source.host_organization_lineage	https://openalex.org/I205783295
best_oa_location.license
best_oa_location.pdf_url	https://arxiv.org/pdf/2511.16007
best_oa_location.version	submittedVersion
best_oa_location.raw_type	text
best_oa_location.license_id
best_oa_location.is_accepted	False
best_oa_location.is_published	False
best_oa_location.raw_source_name
best_oa_location.landing_page_url	http://arxiv.org/abs/2511.16007
primary_location.id	pmh:oai:arXiv.org:2511.16007
primary_location.is_oa	True
primary_location.source.id	https://openalex.org/S4306400194
primary_location.source.issn
primary_location.source.type	repository
primary_location.source.is_oa	True
primary_location.source.issn_l
primary_location.source.is_core	False
primary_location.source.is_in_doaj	False
primary_location.source.display_name	arXiv (Cornell University)
primary_location.source.host_organization	https://openalex.org/I205783295
primary_location.source.host_organization_name	Cornell University
primary_location.source.host_organization_lineage	https://openalex.org/I205783295
primary_location.license
primary_location.pdf_url	https://arxiv.org/pdf/2511.16007
primary_location.version	submittedVersion
primary_location.raw_type	text
primary_location.license_id
primary_location.is_accepted	False
primary_location.is_published	False
primary_location.raw_source_name
primary_location.landing_page_url	http://arxiv.org/abs/2511.16007
publication_date	2025-11-20
publication_year	2025
referenced_works_count	0
abstract_inverted_index.a	9, 15, 61
abstract_inverted_index.In	0
abstract_inverted_index.an	52
abstract_inverted_index.by	13
abstract_inverted_index.in	85, 109
abstract_inverted_index.is	91
abstract_inverted_index.it	42
abstract_inverted_index.of	35, 47, 63, 66, 101, 125
abstract_inverted_index.or	78
abstract_inverted_index.to	94, 118
abstract_inverted_index.we	3, 29, 59, 113
abstract_inverted_index.Our	69
abstract_inverted_index.and	39, 122
abstract_inverted_index.for	50, 104
abstract_inverted_index.our	126
abstract_inverted_index.sum	11
abstract_inverted_index.the	22, 26, 31, 36, 44, 56, 67, 80, 92, 97, 102, 120
abstract_inverted_index.two	115
abstract_inverted_index.(VI)	7
abstract_inverted_index.rate	100
abstract_inverted_index.sure	33
abstract_inverted_index.that	20, 41, 75
abstract_inverted_index.this	1, 89
abstract_inverted_index.with	8
abstract_inverted_index.work	90
abstract_inverted_index.Under	25
abstract_inverted_index.first	93
abstract_inverted_index.match	77
abstract_inverted_index.novel	16
abstract_inverted_index.prove	40
abstract_inverted_index.under	55
abstract_inverted_index.almost	32
abstract_inverted_index.bounds	83
abstract_inverted_index.derive	60
abstract_inverted_index.either	76
abstract_inverted_index.finite	10
abstract_inverted_index.linear	98
abstract_inverted_index.method	71
abstract_inverted_index.paper,	2
abstract_inverted_index.report	114
abstract_inverted_index.yields	72
abstract_inverted_index.Bregman	23, 110
abstract_inverted_index.address	4
abstract_inverted_index.finding	51
abstract_inverted_index.improve	79
abstract_inverted_index.method.	127
abstract_inverted_index.optimal	45
abstract_inverted_index.results	74
abstract_inverted_index.setups.	111
abstract_inverted_index.solving	105
abstract_inverted_index.Finally,	112
abstract_inverted_index.Notably,	88
abstract_inverted_index.achieves	43
abstract_inverted_index.existing	86
abstract_inverted_index.monotone	27
abstract_inverted_index.proposed	37, 70
abstract_inverted_index.reported	84
abstract_inverted_index.setting,	28, 58
abstract_inverted_index.validate	119
abstract_inverted_index.algorithm	19, 38, 103
abstract_inverted_index.distance.	24
abstract_inverted_index.establish	30, 96
abstract_inverted_index.numerical	116
abstract_inverted_index.practical	123
abstract_inverted_index.proposing	14
abstract_inverted_index.structure	12
abstract_inverted_index.}\right)$	49, 65
abstract_inverted_index.algorithm.	68
abstract_inverted_index.complexity	46, 62, 73, 82
abstract_inverted_index.finite-sum	106
abstract_inverted_index.rigorously	95
abstract_inverted_index.convergence	34, 99
abstract_inverted_index.experiments	117
abstract_inverted_index.literature.	87
abstract_inverted_index.performance	124
abstract_inverted_index.single-loop	17
abstract_inverted_index.variational	5, 107
abstract_inverted_index.Furthermore,	54
abstract_inverted_index.incorporates	21
abstract_inverted_index.inequalities	6, 108
abstract_inverted_index.non-monotone	57
abstract_inverted_index.effectiveness	121
abstract_inverted_index.state-of-the-art	81
abstract_inverted_index.variance-reduced	18
abstract_inverted_index.$\varepsilon$-gap.	53
abstract_inverted_index.$\mathcal{O}\left(\frac{1}{\varepsilon^2	64
abstract_inverted_index.$\mathcal{O}\left(\frac{\sqrt{M}}{\varepsilon	48
cited_by_percentile_year
corresponding_author_ids	https://openalex.org/A5108063887
countries_distinct_count	0
institutions_distinct_count	1
citation_normalized_percentile