Decentralized Bilevel Optimization over Graphs: Loopless Algorithmic Update and Transient Iteration Complexity
<|reference_start|>Decentralized Bilevel Optimization over Graphs: Loopless Algorithmic Update and Transient Iteration Complexity: Stochastic bilevel optimization (SBO) is becoming increasingly essential in machine learning due to its versatility in handling nested structures. To address large-scale SBO, decentralized approaches have emerged as effective paradigms in which nodes communicate with immediate neighbors without a central server, thereby improving communication efficiency and enhancing algorithmic robustness. However, current decentralized SBO algorithms face challenges, including expensive inner-loop updates and unclear understanding of the influence of network topology, data heterogeneity, and the nested bilevel algorithmic structures. In this paper, we introduce a single-loop decentralized SBO (D-SOBA) algorithm and establish its transient iteration complexity, which, for the first time, clarifies the joint influence of network topology and data heterogeneity on decentralized bilevel algorithms. D-SOBA achieves the state-of-the-art asymptotic rate, asymptotic gradient/Hessian complexity, and transient iteration complexity under more relaxed assumptions compared to existing methods. Numerical experiments validate our theoretical findings.<|reference_end|>
@article{kong2024decentralized,
    title={Decentralized Bilevel Optimization over Graphs: Loopless Algorithmic
  Update and Transient Iteration Complexity},
    author={Boao Kong, Shuchen Zhu, Songtao Lu, Xinmeng Huang, Kun Yuan},
    journal={arXiv preprint arXiv:2402.03167},
    year={2024},
    archivePrefix={arXiv},
    eprint={2402.03167},
    primaryClass={math.OC cs.LG stat.ML}
}