Distributed online convex optimization with time-varying coupled inequality constraints
This paper considers distributed online optimization with time-varying coupled inequality constraints. The global objective function is composed of local convex cost and regularization functions and the coupled constraint function is the sum of local convex functions. A distributed online primal-dua...
Saved in:
Main Authors: | , , , |
---|---|
Other Authors: | |
Format: | Article |
Language: | English |
Published: |
2023
|
Subjects: | |
Online Access: | https://hdl.handle.net/10356/164461 |
Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Institution: | Nanyang Technological University |
Language: | English |
id |
sg-ntu-dr.10356-164461 |
---|---|
record_format |
dspace |
spelling |
sg-ntu-dr.10356-1644612023-01-26T08:41:19Z Distributed online convex optimization with time-varying coupled inequality constraints Yi, Xinlei Li, Xiuxian Xie, Lihua Johansson, Karl H. School of Electrical and Electronic Engineering Engineering::Electrical and electronic engineering Distributed Optimization Dynamic Mirror Descent This paper considers distributed online optimization with time-varying coupled inequality constraints. The global objective function is composed of local convex cost and regularization functions and the coupled constraint function is the sum of local convex functions. A distributed online primal-dual dynamic mirror descent algorithm is proposed to solve this problem, where the local cost, regularization, and constraint functions are held privately and revealed only after each time slot. Without assuming Slater's condition, we first derive regret and constraint violation bounds for the algorithm and show how they depend on the stepsize sequences, the accumulated dynamic variation of the comparator sequence, the number of agents, and the network connectivity. As a result, under some natural decreasing stepsize sequences, we prove that the algorithm achieves sublinear dynamic regret and constraint violation if the accumulated dynamic variation of the optimal sequence also grows sublinearly. We also prove that the algorithm achieves sublinear static regret and constraint violation under mild conditions. Assuming Slater's condition, we show that the algorithm achieves smaller bounds on the constraint violation. In addition, smaller bounds on the static regret are achieved when the objective function is strongly convex. Finally, numerical simulations are provided to illustrate the effectiveness of the theoretical results. Ministry of Education (MOE) This work was supported in part by the Knut and Alice Wallenberg Foundation, in part by the Swedish Foundation for Strategic Research, in part by the Swedish Research Council, and in part by the Ministry of Education of Republic of Singapore under Grant MoE Tier 1 RG72/19. 2023-01-26T08:41:19Z 2023-01-26T08:41:19Z 2020 Journal Article Yi, X., Li, X., Xie, L. & Johansson, K. H. (2020). Distributed online convex optimization with time-varying coupled inequality constraints. IEEE Transactions On Signal Processing, 68, 731-746. https://dx.doi.org/10.1109/TSP.2020.2964200 1053-587X https://hdl.handle.net/10356/164461 10.1109/TSP.2020.2964200 2-s2.0-85079771660 68 731 746 en RG72/19 IEEE Transactions on Signal Processing © 2020 IEEE. All rights reserved. |
institution |
Nanyang Technological University |
building |
NTU Library |
continent |
Asia |
country |
Singapore Singapore |
content_provider |
NTU Library |
collection |
DR-NTU |
language |
English |
topic |
Engineering::Electrical and electronic engineering Distributed Optimization Dynamic Mirror Descent |
spellingShingle |
Engineering::Electrical and electronic engineering Distributed Optimization Dynamic Mirror Descent Yi, Xinlei Li, Xiuxian Xie, Lihua Johansson, Karl H. Distributed online convex optimization with time-varying coupled inequality constraints |
description |
This paper considers distributed online optimization with time-varying coupled inequality constraints. The global objective function is composed of local convex cost and regularization functions and the coupled constraint function is the sum of local convex functions. A distributed online primal-dual dynamic mirror descent algorithm is proposed to solve this problem, where the local cost, regularization, and constraint functions are held privately and revealed only after each time slot. Without assuming Slater's condition, we first derive regret and constraint violation bounds for the algorithm and show how they depend on the stepsize sequences, the accumulated dynamic variation of the comparator sequence, the number of agents, and the network connectivity. As a result, under some natural decreasing stepsize sequences, we prove that the algorithm achieves sublinear dynamic regret and constraint violation if the accumulated dynamic variation of the optimal sequence also grows sublinearly. We also prove that the algorithm achieves sublinear static regret and constraint violation under mild conditions. Assuming Slater's condition, we show that the algorithm achieves smaller bounds on the constraint violation. In addition, smaller bounds on the static regret are achieved when the objective function is strongly convex. Finally, numerical simulations are provided to illustrate the effectiveness of the theoretical results. |
author2 |
School of Electrical and Electronic Engineering |
author_facet |
School of Electrical and Electronic Engineering Yi, Xinlei Li, Xiuxian Xie, Lihua Johansson, Karl H. |
format |
Article |
author |
Yi, Xinlei Li, Xiuxian Xie, Lihua Johansson, Karl H. |
author_sort |
Yi, Xinlei |
title |
Distributed online convex optimization with time-varying coupled inequality constraints |
title_short |
Distributed online convex optimization with time-varying coupled inequality constraints |
title_full |
Distributed online convex optimization with time-varying coupled inequality constraints |
title_fullStr |
Distributed online convex optimization with time-varying coupled inequality constraints |
title_full_unstemmed |
Distributed online convex optimization with time-varying coupled inequality constraints |
title_sort |
distributed online convex optimization with time-varying coupled inequality constraints |
publishDate |
2023 |
url |
https://hdl.handle.net/10356/164461 |
_version_ |
1756370572163416064 |