Source-linked AI summary
Motivating Workers in Federated Learning: A Stackelberg Game Perspective
Yunus Sarikaya, Ozgur Ercetin
TL;DR
Federated learning can be slowed by heterogeneous worker performance and waiting for the slowest machine in synchronous batches. This paper models worker CPU allocation and model-owner budgeting as a Stackelberg game, finding a trade-off between worker diversity and update latency that limits the useful number of workers.
Problem
Heterogeneous worker performance makes synchronous federated learning wait for the slowest machine, motivating analysis of CPU-resource allocation across workers.
Method
The paper uses a Stackelberg game model to analyze workers’ CPU allocation strategies and the model owner’s budget allocation in synchronous SGD.
Results
The analysis obtains an equilibrium solution and examines how budget and target error rate affect worker CPU utilization and learning convergence time.
Takeaways & Limitations
With a limited budget, the model owner should choose the number of workers carefully because added diversity eventually gives way to delay from waiting for SGD updates.
Abstract
from arXiv · showhide
Due to the large size of the training data, distributed learning approaches such as federated learning have gained attention recently. However, the convergence rate of distributed learning suffers from heterogeneous worker performance. In this paper, we consider an incentive mechanism for workers to mitigate the delays in completion of each batch. We analytically obtained equilibrium solution of a Stackelberg game. Our numerical results indicate that with a limited budget, the model owner should judiciously decide on the number of workers due to trade off between the diversity provided by the number of workers and the latency of completing the training.
I. INTRODUCTION
Federated learning distributes training across mobile workers, but heterogeneous performance and synchronous waiting create latency and participation challenges. The paper addresses these challenges with incentives and a Stackelberg formulation for CPU allocation under a finite budget.
- Motivation: Synchronous distributed training waits for the slowest worker in each batch, producing the straggler effect.Some workers can be five times slower than typical performance.
- Motivation: Worker heterogeneity affects task allocation, learning accuracy, latency, and energy consumption.
- Motivation: Mobile clients require incentives to participate and decide how much CPU resource to allocate to the model owner’s training task.
- Approach: The model owner offers per-worker incentives, while workers choose CPU power for local gradient computation.The owner distributes a finite budget to achieve fast convergence to a target error rate.
- Approach: The interaction is modeled as a Stackelberg game in which the model owner leads and mobile devices follow as service providers.
- Results: The equilibrium is obtained analytically and evaluated numerically on MNIST to study the worker count balancing error and latency.
II. SYSTEM MODEL
The system models synchronous federated learning with workers that compute and return mini-batch gradients, while the owner aggregates updates. Worker completion times are heterogeneous, and the owner chooses CPU-power prices subject to latency and budget considerations.
- Learning process: Workers receive model parameters, compute local mini-batch gradients, and return them for aggregation and model updates.
- Learning process: Synchronous SGD completes an iteration only after all workers return gradients, so its duration is max_i T_i,t.
- Worker model: Worker computation time is modeled as exponentially distributed with mean P_i, while P_i denotes CPU power.
- Incentives: The owner negotiates CPU power prices q_i, and worker i receives revenue q_iP_i.
- Owner objective: The owner minimizes a cost combining expected iteration time and payments, with V controlling the optimization trade-off and B limiting the available budget.
- Incentives: Worker energy cost is κc_i(P_i)^2, and workers maximize utility subject to a maximum CPU-power limit Pmax.
III. STACKELBERG GAME FORMULATION AND EQUILIBRIUM SOLUTION
The paper formulates owner–worker interaction as a two-level Stackelberg game. Workers choose CPU power in response to prices, and the model owner chooses prices while respecting the available budget.
- Game structure: Workers are followers who determine CPU power P_i as a function of per-unit prices q_i.
- Game structure: The model owner is the leader who decides the per-unit CPU-power prices q_i.
- Lower-level subgame: The lower-level subgame fixes the price vector q and defines workers’ CPU-power decisions under Pmax.
- Upper-level subgame: After worker responses are obtained, the upper-level subgame determines the model owner’s pricing problem under the available budget B.
- Equilibrium solution: Backward induction solves the worker subgame first, then substitutes its Nash equilibrium into the owner’s upper-level subgame.
A. Solution to Lower-level Subgame
The lower-level solution derives each worker’s optimal CPU power from utility maximization. Strict concavity ensures that the resulting Nash equilibrium exists and is unique.
- Optimization: The worker’s optimal CPU power is obtained by differentiating its utility with respect to P_i and setting the first-order condition to zero.
- Equilibrium: Each worker’s utility is strictly concave in CPU power, guaranteeing existence and uniqueness of the Nash equilibrium.
B. Solution to Upper-level Subgame
The model owner’s upper-level problem lacks a general closed-form solution in the heterogeneous case, so the paper uses an efficient update algorithm and gives boundary and homogeneous-case results.
- For heterogeneous workers, high non-linearity in the maximum-time equation prevents a general closed-form solution.
- Lemma 2 provides an efficient update algorithm for reaching the equilibrium point in the heterogeneous case.
- When V is sufficiently large, the optimal solution is realized at the budget boundary.
- For homogeneous workers with equal costs, Theorem 1 gives the optimal upper-level subgame solution.
IV. NUMERICAL RESULTS
The simulations evaluate latency and target-error behavior on MNIST while varying workers and budget. They show that worker count has a diversity–waiting-delay trade-off, with optimal worker count increasing with budget and stricter target error.
- MNIST simulations use vectorized 28 x 28 images, a single-layer soft-max model, and averaged realizations to evaluate error-rate latency.The simulations stop when a predefined target error rate is reached and record elapsed time.
- Latency initially decreases as the number of workers increases because greater diversity improves error and reduces required iterations.
- After a certain worker count, latency increases because diversity benefits diminish while waiting for all workers’ updates dominates.
- Increasing the model owner’s budget decreases target-error latency by allocating more CPU power per worker and shortening each iteration.
- For a given budget and target error rate, an optimal number of workers exists because both diversity and per-iteration completion time increase with worker count.
- The optimal worker count increases with budget and as the target error rate decreases.More budget supports CPU purchases from more workers, while stricter targets increase iterations and make data diversity more effective.
V. CONCLUSION
The paper models synchronous federated learning with multiple workers and budget allocation, finding a trade-off between worker diversity and update-waiting delay. It also identifies extensions involving learning methods and dynamic system conditions.
- The paper analyzes CPU allocation and budget allocation among multiple workers in synchronous SGD.
- The analysis examines how budget and target error rate affect worker CPU utilization and learning convergence time.
- Higher worker counts increase learning diversity, but beyond a maximum, waiting for SGD updates dominates the delay.
- Efficient resource allocation algorithms are important for practical learning systems.
- A proposed extension is a dynamic game that accounts for changing channel and worker CPU conditions.
- The optimal worker count may depend on the learning method, including AdaGrad and ADAM.
APPENDIX A
The appendix derives an optimal solution to the worker allocation problem using a Lagrangian formulation and Karush-Kuhn-Tucker conditions. It relates worker parameters to completion-time behavior and characterizes boundary solutions.
- The worker allocation problem is solved with the Lagrangian method because its constraint is linear.
- The Lagrangian multiplier α is defined as part of the optimization formulation.
- The derivation obtains optimal allocations by differentiating the Lagrangian with respect to q_i.
- The analysis uses the relation λ_i = q_i when deriving the optimality conditions.
- As λ_i increases, the maximum completion time is expected to decrease because λ_i is the inverse of mean completion time.
- For sufficiently large V, α is positive, and complementary slackness places the solution at the boundary.
APPENDIX B
The appendix considers a symmetric case in which workers share equal cost and incentive parameters. Under equal λ_i values, the resulting q_i values are also equal.
- When c_i = c_j = c for all workers, the derivation obtains a corresponding relation among the worker parameters.
- Setting λ_i = λ_j = λ for all workers provides a trivial symmetric solution to the stated relation.
- Equal λ_i values result in equal q_i values across workers.