One-Point Sampling for Distributed Bandit Convex Optimization with Time-Varying Constraints
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866909590958899200 |
|---|---|
| author | Zhang, Kunpeng Xu, Lei Yi, Xinlei Wen, Guanghui Xie, Lihua Chai, Tianyou Yang, Tao |
| author_facet | Zhang, Kunpeng Xu, Lei Yi, Xinlei Wen, Guanghui Xie, Lihua Chai, Tianyou Yang, Tao |
| contents | This paper considers the distributed bandit convex optimization problem with time-varying constraints. In this problem, the global loss function is the average of all the local convex loss functions, which are unknown beforehand. Each agent iteratively makes its own decision subject to time-varying inequality constraints which can be violated but are fulfilled in the long run. For a uniformly jointly strongly connected time-varying directed graph, a distributed bandit online primal-dual projection algorithm with one-point sampling is proposed. We show that sublinear dynamic network regret and network cumulative constraint violation are achieved if the path-length of the benchmark also increases in a sublinear manner. In addition, an $\mathcal{O}({T^{3/4 + g}})$ static network regret bound and an $\mathcal{O}( {{T^{1 - {g}/2}}} )$ network cumulative constraint violation bound are established, where $T$ is the total number of iterations and $g \in ( {0,1/4} )$ is a trade-off parameter. Moreover, a reduced static network regret bound $\mathcal{O}( {T^{2/3 + 4g /3}} )$ is established for strongly convex local loss functions. Finally, a numerical example is presented to validate the theoretical results. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_16211 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | One-Point Sampling for Distributed Bandit Convex Optimization with Time-Varying Constraints Zhang, Kunpeng Xu, Lei Yi, Xinlei Wen, Guanghui Xie, Lihua Chai, Tianyou Yang, Tao Systems and Control Signal Processing This paper considers the distributed bandit convex optimization problem with time-varying constraints. In this problem, the global loss function is the average of all the local convex loss functions, which are unknown beforehand. Each agent iteratively makes its own decision subject to time-varying inequality constraints which can be violated but are fulfilled in the long run. For a uniformly jointly strongly connected time-varying directed graph, a distributed bandit online primal-dual projection algorithm with one-point sampling is proposed. We show that sublinear dynamic network regret and network cumulative constraint violation are achieved if the path-length of the benchmark also increases in a sublinear manner. In addition, an $\mathcal{O}({T^{3/4 + g}})$ static network regret bound and an $\mathcal{O}( {{T^{1 - {g}/2}}} )$ network cumulative constraint violation bound are established, where $T$ is the total number of iterations and $g \in ( {0,1/4} )$ is a trade-off parameter. Moreover, a reduced static network regret bound $\mathcal{O}( {T^{2/3 + 4g /3}} )$ is established for strongly convex local loss functions. Finally, a numerical example is presented to validate the theoretical results. |
| title | One-Point Sampling for Distributed Bandit Convex Optimization with Time-Varying Constraints |
| topic | Systems and Control Signal Processing |
| url | https://arxiv.org/abs/2504.16211 |