Dynamic online convex optimization with long-term constraints via virtual queue

Ding, X; Chen, L; Zhou, P; Xu, Z; Wen, S; Lui, JCS; Jin, H

Dynamic online convex optimization with long-term constraints via virtual queue

Ding, X Chen, L Zhou, P Xu, Z Wen, S

Lui, JCS Jin, H

Permalink

Publisher:: Elsevier BV
Publication Type:: Journal Article
Citation:: Information Sciences, 2021, 577, pp. 140-161
Issue Date:: 2021-10-01

Closed Access

	Filename	Description	Size
	1-s2.0-S0020025521006630-main.pdf	Published version	1.34 MB	Adobe PDF	View/Open

Copyright Clearance Process

Recently Added
In Progress
Closed Access

This item is closed access and not available.

Full metadata record

Field	Value	Language
dc.contributor.author	Ding, X
dc.contributor.author	Chen, L
dc.contributor.author	Zhou, P
dc.contributor.author	Xu, Z
dc.contributor.author	Wen, S https://orcid.org/0000-0001-8077-7001
dc.contributor.author	Lui, JCS
dc.contributor.author	Jin, H
dc.date.accessioned	2022-04-18T19:59:16Z
dc.date.available	2022-04-18T19:59:16Z
dc.date.issued	2021-10-01
dc.identifier.citation	Information Sciences, 2021, 577, pp. 140-161
dc.identifier.issn	0020-0255
dc.identifier.uri	http://hdl.handle.net/10453/156344
dc.description.abstract	In this paper, we investigate the online convex optimization (OCO) with long-term constraints which is widely used in various resource allocations and recommendation systems. Different from the most existing works, our work adopts a dynamic benchmark to analyze the optimization performance since the dynamic benchmark is more common than the static benchmark in practical applications. Moreover, compared with many constrained OCO works ignoring the Slater condition, we study the effect of the Slater condition on the constraint violation bounds and obtain the better performance of the constraint violations when the Slater condition holds. More importantly, we propose a novel iterative optimization algorithm based on the virtual queues to achieve sublinear regret and constraint violations. Finally, we apply our dynamic OCO model to a resource allocation problem in cloud computing and the results of the experiments validate the effectiveness of our algorithm.
dc.language	en
dc.publisher	Elsevier BV
dc.relation.ispartof	Information Sciences
dc.relation.isbasedon	10.1016/j.ins.2021.06.072
dc.rights	info:eu-repo/semantics/closedAccess
dc.subject	01 Mathematical Sciences, 08 Information and Computing Sciences, 09 Engineering
dc.subject.classification	Artificial Intelligence & Image Processing
dc.title	Dynamic online convex optimization with long-term constraints via virtual queue
dc.type	Journal Article
utslib.citation.volume	577
utslib.for	01 Mathematical Sciences
utslib.for	08 Information and Computing Sciences
utslib.for	09 Engineering
pubs.organisational-group	/University of Technology Sydney
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology
pubs.organisational-group	/University of Technology Sydney/Strength - AAII - Australian Artificial Intelligence Institute
utslib.copyright.status	closed_access	*
dc.date.updated	2022-04-18T19:59:15Z
pubs.publication-status	Published
pubs.volume	577

Abstract:

In this paper, we investigate the online convex optimization (OCO) with long-term constraints which is widely used in various resource allocations and recommendation systems. Different from the most existing works, our work adopts a dynamic benchmark to analyze the optimization performance since the dynamic benchmark is more common than the static benchmark in practical applications. Moreover, compared with many constrained OCO works ignoring the Slater condition, we study the effect of the Slater condition on the constraint violation bounds and obtain the better performance of the constraint violations when the Slater condition holds. More importantly, we propose a novel iterative optimization algorithm based on the virtual queues to achieve sublinear regret and constraint violations. Finally, we apply our dynamic OCO model to a resource allocation problem in cloud computing and the results of the experiments validate the effectiveness of our algorithm.

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/156344