Reduced Network Cumulative Constraint Violation for Distributed Bandit Convex Optimization under Slater Condition Article Swipe

PDF

Kunpeng Zhang , Xinlei Yi , Jinliang Ding , Ming Cao , Karl Henrik Johansson , Tao Yang ·

YOU? · · 2024 · Open Access · · DOI: https://doi.org/10.48550/arxiv.2411.11574

This paper studies the distributed bandit convex optimization problem with time-varying inequality constraints, where the goal is to minimize network regret and cumulative constraint violation. To calculate network cumulative constraint violation, existing distributed bandit online algorithms solving this problem directly use the clipped constraint function to replace its original constraint function. However, the use of the clipping operation renders Slater condition (i.e, there exists a point that strictly satisfies the inequality constraints at all iterations) ineffective to achieve reduced network cumulative constraint violation. To tackle this challenge, we propose a new distributed bandit online primal-dual algorithm. If local loss functions are convex, we show that the proposed algorithm establishes sublinear network regret and cumulative constraint violation bounds. When Slater condition holds, the network cumulative constraint violation bound is reduced. In addition, if local loss functions are strongly convex, for the case where strongly convex parameters are unknown, the network regret bound is reduced. For the case where strongly convex parameters are known, the network regret and cumulative constraint violation bounds are further reduced. To the best of our knowledge, this paper is among the first to establish reduced (network) cumulative constraint violation bounds for (distributed) bandit convex optimization with time-varying constraints under Slater condition. Finally, a numerical example is provided to verify the theoretical results.

Related Topics

Computer Science

Mathematics

Geometry

Concepts

Constraint (computer-aided design) Regular polygon Mathematical optimization Computer science Convex optimization Mathematics Geometry

Metadata

Type: preprint
Language: en
Landing Page: http://arxiv.org/abs/2411.11574
PDF: https://arxiv.org/pdf/2411.11574
OA Status: green
Related Works: 10
OpenAlex ID: https://openalex.org/W4404571119

All OpenAlex metadata

Raw OpenAlex JSON

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

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

Digital Object Identifier
Title: Reduced Network Cumulative Constraint Violation for Distributed Bandit Convex Optimization under Slater Condition

Work title
Type: preprint

OpenAlex work type
Language: en

Primary language
Publication year: 2024

Year of publication
Publication date: 2024-11-18

Full publication date if available
Authors: Kunpeng Zhang, Xinlei Yi, Jinliang Ding, Ming Cao, Karl Henrik Johansson, Tao Yang

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

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

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/2411.11574

Direct OA link when available
Concepts: Constraint (computer-aided design), Regular polygon, Mathematical optimization, Computer science, Convex optimization, Mathematics, Geometry

Top concepts (fields/topics) attached by OpenAlex
Cited by: 0

Total citation count in OpenAlex
Related works (count): 10

Other works algorithmically related by OpenAlex

Full payload

id	https://openalex.org/W4404571119
doi	https://doi.org/10.48550/arxiv.2411.11574
ids.doi	https://doi.org/10.48550/arxiv.2411.11574
ids.openalex	https://openalex.org/W4404571119
fwci
type	preprint
title	Reduced Network Cumulative Constraint Violation for Distributed Bandit Convex Optimization under Slater Condition
biblio.issue
biblio.volume
biblio.last_page
biblio.first_page
topics[0].id	https://openalex.org/T12101
topics[0].field.id	https://openalex.org/fields/18
topics[0].field.display_name	Decision Sciences
topics[0].score	0.9987000226974487
topics[0].domain.id	https://openalex.org/domains/2
topics[0].domain.display_name	Social Sciences
topics[0].subfield.id	https://openalex.org/subfields/1803
topics[0].subfield.display_name	Management Science and Operations Research
topics[0].display_name	Advanced Bandit Algorithms Research
topics[1].id	https://openalex.org/T10603
topics[1].field.id	https://openalex.org/fields/22
topics[1].field.display_name	Engineering
topics[1].score	0.9817000031471252
topics[1].domain.id	https://openalex.org/domains/3
topics[1].domain.display_name	Physical Sciences
topics[1].subfield.id	https://openalex.org/subfields/2208
topics[1].subfield.display_name	Electrical and Electronic Engineering
topics[1].display_name	Smart Grid Energy Management
topics[2].id	https://openalex.org/T10579
topics[2].field.id	https://openalex.org/fields/17
topics[2].field.display_name	Computer Science
topics[2].score	0.9657999873161316
topics[2].domain.id	https://openalex.org/domains/3
topics[2].domain.display_name	Physical Sciences
topics[2].subfield.id	https://openalex.org/subfields/1705
topics[2].subfield.display_name	Computer Networks and Communications
topics[2].display_name	Cognitive Radio Networks and Spectrum Sensing
is_xpac	False
apc_list
apc_paid
concepts[0].id	https://openalex.org/C2776036281
concepts[0].level	2
concepts[0].score	0.7013667821884155
concepts[0].wikidata	https://www.wikidata.org/wiki/Q48769818
concepts[0].display_name	Constraint (computer-aided design)
concepts[1].id	https://openalex.org/C112680207
concepts[1].level	2
concepts[1].score	0.5818713903427124
concepts[1].wikidata	https://www.wikidata.org/wiki/Q714886
concepts[1].display_name	Regular polygon
concepts[2].id	https://openalex.org/C126255220
concepts[2].level	1
concepts[2].score	0.5670379996299744
concepts[2].wikidata	https://www.wikidata.org/wiki/Q141495
concepts[2].display_name	Mathematical optimization
concepts[3].id	https://openalex.org/C41008148
concepts[3].level	0
concepts[3].score	0.47354787588119507
concepts[3].wikidata	https://www.wikidata.org/wiki/Q21198
concepts[3].display_name	Computer science
concepts[4].id	https://openalex.org/C157972887
concepts[4].level	3
concepts[4].score	0.4587969183921814
concepts[4].wikidata	https://www.wikidata.org/wiki/Q463359
concepts[4].display_name	Convex optimization
concepts[5].id	https://openalex.org/C33923547
concepts[5].level	0
concepts[5].score	0.3645201623439789
concepts[5].wikidata	https://www.wikidata.org/wiki/Q395
concepts[5].display_name	Mathematics
concepts[6].id	https://openalex.org/C2524010
concepts[6].level	1
concepts[6].score	0.046276211738586426
concepts[6].wikidata	https://www.wikidata.org/wiki/Q8087
concepts[6].display_name	Geometry
keywords[0].id	https://openalex.org/keywords/constraint
keywords[0].score	0.7013667821884155
keywords[0].display_name	Constraint (computer-aided design)
keywords[1].id	https://openalex.org/keywords/regular-polygon
keywords[1].score	0.5818713903427124
keywords[1].display_name	Regular polygon
keywords[2].id	https://openalex.org/keywords/mathematical-optimization
keywords[2].score	0.5670379996299744
keywords[2].display_name	Mathematical optimization
keywords[3].id	https://openalex.org/keywords/computer-science
keywords[3].score	0.47354787588119507
keywords[3].display_name	Computer science
keywords[4].id	https://openalex.org/keywords/convex-optimization
keywords[4].score	0.4587969183921814
keywords[4].display_name	Convex optimization
keywords[5].id	https://openalex.org/keywords/mathematics
keywords[5].score	0.3645201623439789
keywords[5].display_name	Mathematics
keywords[6].id	https://openalex.org/keywords/geometry
keywords[6].score	0.046276211738586426
keywords[6].display_name	Geometry
language	en
locations[0].id	pmh:oai:arXiv.org:2411.11574
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/2411.11574
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/2411.11574
locations[1].id	doi:10.48550/arxiv.2411.11574
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.2411.11574
indexed_in	arxiv, datacite
authorships[0].author.id	https://openalex.org/A5100449420
authorships[0].author.orcid	https://orcid.org/0000-0001-5511-3174
authorships[0].author.display_name	Kunpeng Zhang
authorships[0].author_position	first
authorships[0].raw_author_name	Zhang, Kunpeng
authorships[0].is_corresponding	False
authorships[1].author.id	https://openalex.org/A5016417704
authorships[1].author.orcid	https://orcid.org/0000-0003-4299-0471
authorships[1].author.display_name	Xinlei Yi
authorships[1].author_position	middle
authorships[1].raw_author_name	Yi, Xinlei
authorships[1].is_corresponding	False
authorships[2].author.id	https://openalex.org/A5022740106
authorships[2].author.orcid	https://orcid.org/0000-0003-3735-0672
authorships[2].author.display_name	Jinliang Ding
authorships[2].author_position	middle
authorships[2].raw_author_name	Ding, Jinliang
authorships[2].is_corresponding	False
authorships[3].author.id	https://openalex.org/A5021403340
authorships[3].author.orcid	https://orcid.org/0000-0001-5472-562X
authorships[3].author.display_name	Ming Cao
authorships[3].author_position	middle
authorships[3].raw_author_name	Cao, Ming
authorships[3].is_corresponding	False
authorships[4].author.id	https://openalex.org/A5045975901
authorships[4].author.orcid	https://orcid.org/0000-0001-9940-5929
authorships[4].author.display_name	Karl Henrik Johansson
authorships[4].author_position	middle
authorships[4].raw_author_name	Johansson, Karl H.
authorships[4].is_corresponding	False
authorships[5].author.id	https://openalex.org/A5014234601
authorships[5].author.orcid	https://orcid.org/0000-0003-4090-8497
authorships[5].author.display_name	Tao Yang
authorships[5].author_position	last
authorships[5].raw_author_name	Yang, Tao
authorships[5].is_corresponding	False
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/2411.11574
open_access.oa_status	green
open_access.any_repository_has_fulltext	False
created_date	2025-10-10T00:00:00
display_name	Reduced Network Cumulative Constraint Violation for Distributed Bandit Convex Optimization under Slater Condition
has_fulltext	False
is_retracted	False
updated_date	2025-11-06T06:51:31.235846
primary_topic.id	https://openalex.org/T12101
primary_topic.field.id	https://openalex.org/fields/18
primary_topic.field.display_name	Decision Sciences
primary_topic.score	0.9987000226974487
primary_topic.domain.id	https://openalex.org/domains/2
primary_topic.domain.display_name	Social Sciences
primary_topic.subfield.id	https://openalex.org/subfields/1803
primary_topic.subfield.display_name	Management Science and Operations Research
primary_topic.display_name	Advanced Bandit Algorithms Research
related_works	https://openalex.org/W4391375266, https://openalex.org/W1979597421, https://openalex.org/W2007980826, https://openalex.org/W2061531152, https://openalex.org/W3002753104, https://openalex.org/W2077600819, https://openalex.org/W2142036596, https://openalex.org/W2072657027, https://openalex.org/W2349580982, https://openalex.org/W3153752017
cited_by_count	0
locations_count	2
best_oa_location.id	pmh:oai:arXiv.org:2411.11574
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/2411.11574
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/2411.11574
primary_location.id	pmh:oai:arXiv.org:2411.11574
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/2411.11574
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/2411.11574
publication_date	2024-11-18
publication_year	2024
referenced_works_count	0
abstract_inverted_index.a	64, 89, 205
abstract_inverted_index.If	96
abstract_inverted_index.In	129
abstract_inverted_index.To	25, 83, 173
abstract_inverted_index.at	72
abstract_inverted_index.if	131
abstract_inverted_index.is	16, 127, 151, 181, 208
abstract_inverted_index.of	54, 176
abstract_inverted_index.to	17, 45, 76, 185, 210
abstract_inverted_index.we	87, 102
abstract_inverted_index.For	153
abstract_inverted_index.all	73
abstract_inverted_index.and	21, 112, 165
abstract_inverted_index.are	100, 135, 145, 160, 170
abstract_inverted_index.for	138, 193
abstract_inverted_index.its	47
abstract_inverted_index.new	90
abstract_inverted_index.our	177
abstract_inverted_index.the	3, 14, 41, 52, 55, 69, 105, 121, 139, 147, 154, 162, 174, 183, 212
abstract_inverted_index.use	40, 53
abstract_inverted_index.This	0
abstract_inverted_index.When	117
abstract_inverted_index.best	175
abstract_inverted_index.case	140, 155
abstract_inverted_index.goal	15
abstract_inverted_index.loss	98, 133
abstract_inverted_index.show	103
abstract_inverted_index.that	66, 104
abstract_inverted_index.this	37, 85, 179
abstract_inverted_index.with	9, 198
abstract_inverted_index.(i.e,	61
abstract_inverted_index.among	182
abstract_inverted_index.bound	126, 150
abstract_inverted_index.first	184
abstract_inverted_index.local	97, 132
abstract_inverted_index.paper	1, 180
abstract_inverted_index.point	65
abstract_inverted_index.there	62
abstract_inverted_index.under	201
abstract_inverted_index.where	13, 141, 156
abstract_inverted_index.Slater	59, 118, 202
abstract_inverted_index.bandit	5, 33, 92, 195
abstract_inverted_index.bounds	169, 192
abstract_inverted_index.convex	6, 143, 158, 196
abstract_inverted_index.exists	63
abstract_inverted_index.holds,	120
abstract_inverted_index.known,	161
abstract_inverted_index.online	34, 93
abstract_inverted_index.regret	20, 111, 149, 164
abstract_inverted_index.tackle	84
abstract_inverted_index.verify	211
abstract_inverted_index.achieve	77
abstract_inverted_index.bounds.	116
abstract_inverted_index.clipped	42
abstract_inverted_index.convex,	101, 137
abstract_inverted_index.example	207
abstract_inverted_index.further	171
abstract_inverted_index.network	19, 27, 79, 110, 122, 148, 163
abstract_inverted_index.problem	8, 38
abstract_inverted_index.propose	88
abstract_inverted_index.reduced	78, 187
abstract_inverted_index.renders	58
abstract_inverted_index.replace	46
abstract_inverted_index.solving	36
abstract_inverted_index.studies	2
abstract_inverted_index.Finally,	204
abstract_inverted_index.However,	51
abstract_inverted_index.clipping	56
abstract_inverted_index.directly	39
abstract_inverted_index.existing	31
abstract_inverted_index.function	44
abstract_inverted_index.minimize	18
abstract_inverted_index.original	48
abstract_inverted_index.proposed	106
abstract_inverted_index.provided	209
abstract_inverted_index.reduced.	128, 152, 172
abstract_inverted_index.results.	214
abstract_inverted_index.strictly	67
abstract_inverted_index.strongly	136, 142, 157
abstract_inverted_index.unknown,	146
abstract_inverted_index.(network)	188
abstract_inverted_index.addition,	130
abstract_inverted_index.algorithm	107
abstract_inverted_index.calculate	26
abstract_inverted_index.condition	60, 119
abstract_inverted_index.establish	186
abstract_inverted_index.function.	50
abstract_inverted_index.functions	99, 134
abstract_inverted_index.numerical	206
abstract_inverted_index.operation	57
abstract_inverted_index.satisfies	68
abstract_inverted_index.sublinear	109
abstract_inverted_index.violation	115, 125, 168, 191
abstract_inverted_index.algorithm.	95
abstract_inverted_index.algorithms	35
abstract_inverted_index.challenge,	86
abstract_inverted_index.condition.	203
abstract_inverted_index.constraint	23, 29, 43, 49, 81, 114, 124, 167, 190
abstract_inverted_index.cumulative	22, 28, 80, 113, 123, 166, 189
abstract_inverted_index.inequality	11, 70
abstract_inverted_index.knowledge,	178
abstract_inverted_index.parameters	144, 159
abstract_inverted_index.violation,	30
abstract_inverted_index.violation.	24, 82
abstract_inverted_index.constraints	71, 200
abstract_inverted_index.distributed	4, 32, 91
abstract_inverted_index.establishes	108
abstract_inverted_index.ineffective	75
abstract_inverted_index.iterations)	74
abstract_inverted_index.primal-dual	94
abstract_inverted_index.theoretical	213
abstract_inverted_index.constraints,	12
abstract_inverted_index.optimization	7, 197
abstract_inverted_index.time-varying	10, 199
abstract_inverted_index.(distributed)	194
cited_by_percentile_year
countries_distinct_count	0
institutions_distinct_count	6
citation_normalized_percentile