Hybrid Quantum–Classical Benders' Decomposition for Federated Learning Scheduling in Distributed Networks

Abstract

Scheduling multiple federated learning (FL) models within a distributed network, especially in large-scale scenarios, poses significant challenges since it involves solving NP-hard mixed-integer nonlinear programming (MINLP) problems. However, it's imperative to optimize participant selection and learning rate determination for these FL models to avoid excessive training costs and prevent resource contention. While some existing methods focus solely on optimizing a single global FL model, others struggle to achieve optimal solutions as the problem grows more complex. In this paper, exploiting the potential of quantum computing, we introduce the Hybrid Quantum-Classical Benders' Decomposition (HQCBD) algorithm to effectively tackle the joint MINLP optimization problem for multi-model FL training. HQCBD combines quantum and classical computing to solve the joint participant selection and learning scheduling problem. It decomposes the optimization problem into a master problem with binary variables and small subproblems with continuous variables, then leverages the strengths of both quantum and classical computing to solve them respectively and iteratively. Furthermore, we propose the Hybrid Quantum-Classical Multiple-cuts Benders' Decomposition (MBD) algorithm, which utilizes the inherent capabilities of quantum algorithms to produce multiple cuts in each round, to speed up the proposed HQCBD algorithm. Extensive simulation on the commercial quantum annealing machine demonstrates the effectiveness and robustness of the proposed methods (both HQCBD and MBD), with improvements of up to 70.3% in iterations and 81% in computation time over the classical Benders' decomposition algorithm on classical CPUs, even at modest scales.