Twin Sorting Dynamic Programming Assisted User Association and Wireless Bandwidth Allocation for Hierarchical Federated Learning

• URL: http://arxiv.org/abs/2408.09076v1
• Date: Sat, 17 Aug 2024 02:29:32 GMT
• Title: Twin Sorting Dynamic Programming Assisted User Association and Wireless Bandwidth Allocation for Hierarchical Federated Learning
• Authors: Rung-Hung Gau, Ting-Yu Wang, Chun-Hung Liu,
• Abstract summary: We study user association and wireless bandwidth allocation for a hierarchical federated learning system. We design the twin sorting dynamic programming (TSDP) algorithm that obtains a globally optimal solution in time when there are two edge servers. In addition, we put forward the TSDP-assisted algorithm for user association when there are three or more edge servers.
• Score: 7.274131715810928
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this paper, we study user association and wireless bandwidth allocation for a hierarchical federated learning system that consists of mobile users, edge servers, and a cloud server. To minimize the length of a global round in hierarchical federated learning with equal bandwidth allocation, we formulate a combinatorial optimization problem. We design the twin sorting dynamic programming (TSDP) algorithm that obtains a globally optimal solution in polynomial time when there are two edge servers. In addition, we put forward the TSDP-assisted algorithm for user association when there are three or more edge servers. Furthermore, given a user association matrix, we formulate and solve a convex optimization problem for optimal wireless bandwidth allocation. Simulation results show that the proposed approach outperforms a number of alternative schemes.

Related papers

• FusionLLM: A Decentralized LLM Training System on Geo-distributed GPUs with Adaptive Compression [55.992528247880685]
  Decentralized training faces significant challenges regarding system design and efficiency. We present FusionLLM, a decentralized training system designed and implemented for training large deep neural networks (DNNs) We show that our system and method can achieve 1.45 - 9.39x speedup compared to baseline methods while ensuring convergence.
  arXiv  Detail & Related papers  (2024-10-16T16:13:19Z)
• Efficient Reinforcement Learning for Routing Jobs in Heterogeneous Queueing Systems [21.944723061337267]
  We consider the problem of efficiently routing jobs that arrive into a central queue to a system of heterogeneous servers. Unlike homogeneous systems, a threshold policy, that routes jobs to the slow server(s) when the queue length exceeds a certain threshold, is known to be optimal for the one-fast-one-slow two-server system. We propose ACHQ, an efficient policy gradient based algorithm with a low dimensional soft threshold policy parameterization.
  arXiv  Detail & Related papers  (2024-02-02T05:22:41Z)
• Federated Multi-Level Optimization over Decentralized Networks [55.776919718214224]
  We study the problem of distributed multi-level optimization over a network, where agents can only communicate with their immediate neighbors. We propose a novel gossip-based distributed multi-level optimization algorithm that enables networked agents to solve optimization problems at different levels in a single timescale. Our algorithm achieves optimal sample complexity, scaling linearly with the network size, and demonstrates state-of-the-art performance on various applications.
  arXiv  Detail & Related papers  (2023-10-10T00:21:10Z)
• Teal: Learning-Accelerated Optimization of WAN Traffic Engineering [68.7863363109948]
  We present Teal, a learning-based TE algorithm that leverages the parallel processing power of GPUs to accelerate TE control. To reduce the problem scale and make learning tractable, Teal employs a multi-agent reinforcement learning (RL) algorithm to independently allocate each traffic demand. Compared with other TE acceleration schemes, Teal satisfies 6--32% more traffic demand and yields 197--625x speedups.
  arXiv  Detail & Related papers  (2022-10-25T04:46:30Z)
• Predictive GAN-powered Multi-Objective Optimization for Hybrid Federated Split Learning [56.125720497163684]
  We propose a hybrid federated split learning framework in wireless networks. We design a parallel computing scheme for model splitting without label sharing, and theoretically analyze the influence of the delayed gradient caused by the scheme on the convergence speed.
  arXiv  Detail & Related papers  (2022-09-02T10:29:56Z)
• Decentralized Gossip-Based Stochastic Bilevel Optimization over Communication Networks [42.76623191830371]
  We propose a gossip-based distributed bilevel optimization algorithm. Agents can solve both networked and outer problems in a single time. Our algorithm achieves the state-of-the-art efficiency and test accuracy.
  arXiv  Detail & Related papers  (2022-06-22T06:38:54Z)
• Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
  We consider the task of minimizing the sum of smooth and strongly convex functions stored in a decentralized manner across the nodes of a communication network. We design two optimal algorithms that attain these lower bounds. We corroborate the theoretical efficiency of these algorithms by performing an experimental comparison with existing state-of-the-art methods.
  arXiv  Detail & Related papers  (2021-06-08T15:54:44Z)
• Joint User Pairing and Association for Multicell NOMA: A Pointer Network-based Approach [22.501227501613204]
  We consider a scenario where the user equipments (UEs) are located in a multicell network equipped with multiple base stations. We formulate the joint user pairing and association problem as an optimization problem using an emerging deep learning architecture called Pointer Network (PtrNet) The proposed joint user pairing and association scheme achieves near-optimal performance in terms of the aggregate data rate.
  arXiv  Detail & Related papers  (2020-04-15T23:42:19Z)
• Joint Parameter-and-Bandwidth Allocation for Improving the Efficiency of Partitioned Edge Learning [73.82875010696849]
  Machine learning algorithms are deployed at the network edge for training artificial intelligence (AI) models. This paper focuses on the novel joint design of parameter (computation load) allocation and bandwidth allocation.
  arXiv  Detail & Related papers  (2020-03-10T05:52:15Z)
• Multiple Access in Dynamic Cell-Free Networks: Outage Performance and Deep Reinforcement Learning-Based Design [24.632250413917816]
  In future cell-free (or cell-less) wireless networks, a large number of devices in a geographical area will be served simultaneously by a large number of distributed access points (APs) We propose a novel dynamic cell-free network architecture to reduce the complexity of joint processing of users' signals in presence of a large number of devices and APs. In our system setting, the proposed DDPG-DDQN scheme is found to achieve around $78%$ of the rate achievable through an exhaustive search-based design.
  arXiv  Detail & Related papers  (2020-01-29T03:00:22Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.