pipette
ENEnglish

Dynamic Regret and Tightened Constraint Violation for Communication-Efficient Distributed Online Bilevel Optimization

Fan Li, Xinlei Yi, Guanghui Wen, Yang Shi, and Tao Yang

Preprint

En palabras de los autores

This paper investigates the distributed online bilevel optimization problem with time-varying inequality constraints. In this setting, a multi-agent network is confronted with a hierarchical decision-making task characterized by coupling between the inner and outer optimization levels. We first propose a communication-efficient single-loop distributed online primal--dual algorithm based on communication compression, which tracks both the inner-level solution and the Hessian-inverse-vector product using only one update per-round. We show that this algorithm achieves a dynamic network regret bound of , where~, is the outer-level path variation, is the inner-level path variation, and is the gradient path variation alongside a network cumulative constraint violation bound of , which is further reduced to under Slater's condition. Furthermore, to eliminate the dependence of regret on the inner-level and gradient path variation, we propose a novel adaptive multi-loop distributed online algorithm to control the inner-level approximation accuracy at each round. By dynamically adjusting the number of inner-level updates based on a gradient-norm tolerance condition, this algorithm yields an improved dynamic network regret bound of which depends solely on the outer-level path variation while maintaining the same network cumulative constraint violation bound. Finally, numerical simulations verify the effectiveness of the proposed algorithms.

Resultado principalEl resumen no menciona limitaciones.

Apareció: miércoles, 21 de octubre. arXiv. Preprint, todavía sin revisión por pares.