Dynamic Regret and Tightened Constraint Violation for Communication-Efficient Distributed Online Bilevel Optimization
Abstract
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 𝒪(Tmax{θ1,1−θ1}+Tθ1 PT+H1,T+E1,T), where~θ1 ∈ (0,1), PT is the outer-level path variation, H1,T is the inner-level path variation, and E1,T is the gradient path variation alongside a network cumulative constraint violation bound of 𝒪(T1−θ1/2), which is further reduced to 𝒪(T1−θ1) 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 𝒪(Tmax{θ1,1−θ1}+Tθ1 PT) 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.
Related
- Communication-Efficient Differentially Private Gradient Tracking for Distributed Optimization via Local Updates
- Distributed Consensus, Optimization, and Learning under Communication Constraints
- Safe Multi-Objective Reinforcement Learning: Zero Constraint Violation and Primal-Averaging Convergence
- Topology Design for Distributed Consensus with Relay-Assisted Communication
- Communication and Privacy Trade-Offs in Distributed Storage With Shared Secret Keys
BibTeX
@misc{li2026dynamic,
title = {{Dynamic Regret and Tightened Constraint Violation for Communication-Efficient Distributed Online Bilevel Optimization}},
author = {Fan Li and Xinlei Yi and Guanghui Wen and Yang Shi and Tao Yang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.26911},
eprint = {2610.26911},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.26911},
}
RIS
TY - UNPB
TI - Dynamic Regret and Tightened Constraint Violation for Communication-Efficient Distributed Online Bilevel Optimization
AU - Fan Li
AU - Xinlei Yi
AU - Guanghui Wen
AU - Yang Shi
AU - Tao Yang
PY - 2026
DA - 2026/10/17
PB - arXiv
DO - 10.48550/arxiv.2610.26911
UR - https://arxiv.org/abs/2610.26911
AB - 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 𝒪(T^max{θ_1,1−θ_1}+T^θ_1 P_T+H_1,T+E_1,T), where~θ_1 ∈ (0,1), P_T is the outer-level path variation, H_1,T is the inner-level path variation, and E_1,T is the gradient path variation alongside a network cumulative constraint violation bound of 𝒪(T^1−θ_1/2), which is further reduced to 𝒪(T^1−θ_1) 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 𝒪(T^max{θ_1,1−θ_1}+T^θ_1 P_T) 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.
ER -