A Crowdsourcing Framework for On-Device Federated Learning

Shashi Raj Pandey; Nguyen H. Tran; Mehdi Bennis; Yan Kyaw Tun; Aunas Manzoor; Choong Seon Hong

Source-linked AI summary

A Crowdsourcing Framework for On-Device Federated Learning

Shashi Raj Pandey, Nguyen H. Tran, Mehdi Bennis, Yan Kyaw Tun, Aunas Manzoor, Choong Seon Hong

arXiv:1911.01046v2Nov 4, 2019cs.LGcs.GTcs.NIstat.ML

TL;DR

Federated learning must coordinate local computation, client participation, and communication efficiency without centralizing users’ training data. The paper proposes a crowdsourcing framework with incentive mechanisms, a two-stage Stackelberg game, and admission control; simulations report up to 22% gain in offered reward over a heuristic baseline.

Problem
FL must motivate participating mobile clients while maintaining communication efficiency during model-parameter exchange for high-quality global learning.
Method
The paper designs a crowdsourcing framework using a communication-efficient cost model, a two-stage Stackelberg game, and an admission-control strategy.
Results
Up to 22% gain in the offered reward is achieved over a heuristic approach, while the linear-complexity solution attains the same performance as the mixed-boolean formulation.
Takeaways & Limitations
The framework provides an incentive-based approach for coordinating client participation and communication-efficient FL under heterogeneous local responses.

Abstract

from arXiv · show

Federated learning (FL) rests on the notion of training a global model in a decentralized manner. Under this setting, mobile devices perform computations on their local data before uploading the required updates to improve the global model. However, when the participating clients implement an uncoordinated computation strategy, the difficulty is to handle the communication efficiency (i.e., the number of communications per iteration) while exchanging the model parameters during aggregation. Therefore, a key challenge in FL is how users participate to build a high-quality global model with communication efficiency. We tackle this issue by formulating a utility maximization problem, and propose a novel crowdsourcing framework to leverage FL that considers the communication efficiency during parameters exchange. First, we show an incentive-based interaction between the crowdsourcing platform and the participating client's independent strategies for training a global learning model, where each side maximizes its own benefit. We formulate a two-stage Stackelberg game to analyze such scenario and find the game's equilibria. Second, we formalize an admission control scheme for participating clients to ensure a level of local accuracy. Simulated results demonstrate the efficacy of our proposed solution with up to 22% gain in the offered reward.

I. INTRODUCTION

The paper frames federated learning as a decentralized approach that keeps training data on mobile devices while requiring communication-efficient coordination and incentives for participation. It proposes a crowdsourcing framework combining incentive design, Stackelberg-game analysis, and admission control to support high-quality global learning.

Motivation: Federated learning keeps training data on user devices while clients compute local updates that a coordinating server aggregates into a global model.The process iterates until the global model reaches a target accuracy.
Motivation: Communication-efficient FL must manage interleaved local computation and server communication while motivating users to contribute private data without sharing it.The paper identifies both communication efficiency and client participation as central challenges.
Contributions: The paper formalizes an incentive mechanism and communication-efficient cost model for mobile clients participating in FL.The framework accounts for communications per iteration while maintaining acceptable global-model accuracy.
Contributions: A two-stage Stackelberg game models clients minimizing participation costs and the MEC server offering rewards to build a high-quality centralized model.The paper analyzes the game’s equilibria and proposes a linear-complexity solution algorithm.
Results: Up to 22% gain in the offered reward is achieved over a heuristic approach, while the linear-complexity solution attains the same performance as the mixed-boolean formulation.The reported case studies assess both optimality and reward performance.
Contributions: An admission-control strategy estimates threshold accuracy and the required number of participating clients for communication-efficient, high-quality FL.The strategy uses a probabilistic model and closed-form solutions for different configurations.

III. SYSTEM MODEL

The system model decomposes federated learning into local client subproblems and a server-side global problem over unevenly partitioned data. Clients iteratively solve local problems to relative accuracies, exchange parameter updates, and receive aggregated global changes, while the framework models the accuracy–resource–communication trade-off.

System architecture: Mobile clients with unevenly partitioned datasets communicate through an application platform with an MEC server that aggregates parameters and returns global updates.The server acts as the central coordinating entity in each global iteration.
Optimization model: The global learning objective is represented as a finite-sum problem over local client objectives and recast into a distributed dual optimization framework.The dual formulation supports distributed training and uses the duality gap as a quality certificate for local solutions.
Local computation: Each client solves its local subproblem with an arbitrary solver to attain a local relative accuracy θk and produces a local parameter update.The framework permits methods such as SGD, SAG, and SVRG for local optimization.
Aggregation: Clients broadcast local parameter changes during communication rounds, and the MEC server averages them before distributing the resulting global change for the next local iteration.This iterative process continues until the target global accuracy is reached.
Trade-offs: Higher local accuracy can improve global accuracy but requires clients to spend more local computational resources, creating an accuracy–cost trade-off.The model uses client-specific parameters linked to local data size and subproblem condition number, while communication time depends on wireless conditions and connectivity.
Economic interaction: The crowdsourcing framework uses economic interaction to motivate better client accuracy and models the MEC server–client interaction as a two-stage Stackelberg game.The interaction environment is designed to address heterogeneous client responses and communication efficiency.

B. Cost Model

The cost model accounts for both local computation and communication needed to attain a specified relative accuracy. It captures a trade-off between these costs and relates communication expenditure to wireless conditions and interaction frequency.

Cost components: Training on local data incurs computing and communication costs for participating clients.The computing cost depends on local iterations, while communication cost arises from parameter exchanges with the MEC server.
Computing cost: Computing cost measures local iterations required to attain relative accuracy θk in one communication round.
Communication cost: Communication cost measures expenditure from repeated MEC interactions needed to maintain relative accuracy θk.The number of global iterations increases when local accuracy is poorer.
Communication cost: Tk depends on wireless conditions and network connectivity for each round of parameter exchange.It is characterized using bandwidth, transmission power, channel gain, and Gaussian noise power.
Cost trade-off: The cost model exposes a trade-off between communication and computing costs weighted by νk.A higher νk places greater emphasis on communication-related interaction rounds.

IV. INCENTIVE MECHANISM FOR CLIENT’S PARTICIPATION IN THE DECENTRALIZED LEARNING FRAMEWORK

This section motivates a crowdsourcing framework for decentralized learning and introduces the need for an incentive mechanism. The mechanism is intended to support federated learning participation by mobile clients.

The framework applies crowdsourcing to realize federated learning with decentralized learning models.
An incentive mechanism is presented as necessary for realizing the decentralized learning setting.
The section moves from the motivation for federated learning crowdsourcing toward the proposed solution approach.

A. Incentive Mechanism: A Two-Stage Stackelberg Game Approach

The paper models MEC-server incentives and client participation as a two-stage Stackelberg game. Clients choose local-accuracy strategies after observing the reward, while the server selects rewards to optimize utility and uses admission control to manage participation.

Game formulation: The MEC server acts as leader and participating clients act as followers in a two-stage Stackelberg game.The server designs incentives, and clients respond by selecting local consensus accuracy strategies.
Clients (Stage II): Clients maximize individual utility by balancing reward-based valuation against participation cost.Their valuation is modeled as vk(θk) = (1−θk), with feasible strategies restricted to θk < 1.
Clients (Stage II): The client cost function has a unique optimum because Ck(θk) is strictly convex.For a given reward rate r and communication time Tk, Lemma 2 states that the solution θ∗k is unique.
MEC Server (Stage I): The MEC server chooses a reward rate after observing clients’ best responses to maximize its utility.Its utility reflects satisfaction from achieving global-model accuracy while accounting for incentive expenditure.
MEC utility: The MEC utility is modeled as a bounded, strictly concave function of iterations required to achieve accuracy ǫ.Parameters a and b control the utility curve’s iteration requirement and flexibility in accuracy.
Admission control: Admission control adjusts participation to improve utility and maintain the minimum participation needed for distributed optimization.The framework states that at least two participating clients are required and may increase rewards to maintain this level.

B. Stackelberg Equilibrium: Algorithm and Solution Approach

The framework models client responses and MEC-server incentives as a two-stage Stackelberg interaction, then uses threshold-based admission control and a linear-complexity solution approach to manage accuracy and communication efficiency.

Threshold-based coordination: The server selects incentives to improve the global model while maintaining a worst-case local relative-accuracy threshold among participating clients.The threshold represents a consensus maximum local accuracy level, with participating clients maintaining at least θth relative accuracy.
Client response: Higher rewards motivate clients to perform more local iterations, producing lower relative accuracy values that represent higher local accuracy during communication rounds.For gk(r) > 2, increased rewards lead to more computation and can reduce the number of global iterations needed to reach a target accuracy.
Client response: Client responses depend on communication conditions and preferences: reluctant clients consume more reward, sensitive clients react more strongly to channel quality, and rational clients balance both costs.The normalized preference weight νk determines the relative emphasis on computation and communication expenditure.
Admission control: The server uses binary admission variables to retain clients meeting θth and drop participants whose response fails the accuracy criterion.zk = 1 when θk(r) < θth, while zk = 0 when θth ≤ θk(r) < 1.
Solution approach: Algorithm 2 solves the equivalent Stage-I problem with linear complexity instead of exhaustive search over 2^K client configurations.The mixed-boolean formulation may require exponential effort under exhaustive search, whereas the proposed approach has linear complexity.
Equilibrium analysis: The client best responses and server strategy form Stackelberg equilibria represented by pairs {r*, θ*}.Lemma 2 establishes a unique client response θ*k(r) for a given reward rate and channel-dependent communication time Tk.

V. SIMULATION RESULTS AND ANALYSIS

Numerical simulations evaluate the proposed algorithm for logistic regression against exhaustive-search OPT and a worst-response Baseline, while varying system parameters and comparing utilities.

Simulation design: The simulations use a strongly convex logistic-regression model to compare Algorithm 2 with exhaustive-search OPT and a worst-response Baseline.OPT solves problem (23) by exhaustive search, while Baseline uses the worst participating-client response to attain local consensus accuracy.
Simulation design: The evaluation varies parameters and compares the incentive mechanism with the baseline and corresponding MEC utilities.Smaller local-consensus values are treated as especially relevant because they reflect FL effectiveness.
Simulation settings: The illustrative scenario fixes four participating clients, β = 10, δ = 10, and νk uniformly distributed on [0.1,0.5].The MEC utility is U(x(ǫ)) = 1 − 10^−(ax(ǫ)+b), with a = 0.3 and b = 0.

1) Settings:

The reward-rate analysis varies the local consensus threshold θth from 0.2 to 0.6 to examine how stricter accuracy requirements affect incentives.

Settings: Increasing the local consensus accuracy requirement from 0.4 to 0.2 significantly increases the reward rate.Higher local accuracy requires more local iterations, so clients receive greater incentives to compensate for their costs.
Settings: The analysis varies θth across the range 0.2 to 0.6.The simulations use the threshold as the parameter controlling the local consensus accuracy requirement.

2) Reward rate:

Algorithm 2 matches exhaustive-search OPT and outperforms the Baseline in reward efficiency, with the largest reward variation occurring at lower threshold values.

Reward comparison: Algorithm 2 and OPT achieve the same performance, while Baseline is less efficient.The two proposed schemes obtain up to 22% gain in offered reward against Baseline.
Reward comparison: Reward variation is prominent for lower values of θth, and the corresponding MEC utility follows the offered-reward trend.The utility comparison complements the reward-rate evaluation of Algorithm 2.
Parameter sensitivity: Distributed client parameters γk affect the offered reward required for improved local accuracy.Using identical local-subproblem algorithms yields a lower offered reward than uniformly distributed γk on.

3) Parametric choice:

The framework selects an admission threshold θth and evaluates how client parameters, utility settings, participation, and δ affect rewards and local accuracy. Randomized client parameters can improve offered rewards, while θth generally rises with participation and stricter accuracy requirements.

Parametric choice: Up to 71% gain in offered reward against the Baseline is observed with randomized γk, validating the proposal’s efficacy for FL.The result is reported for randomized γk under different MEC utility-model configurations.
Admission control: The MEC server chooses θth to maximize utility while constraining the threshold between θmin and θmax.Accepted participation depends on the threshold and the client-response distribution.
Admission control: Newton-Raphson iteratively obtains θ*(t) from an initial guess based on the uniform response distribution.The method is selected to achieve quadratic convergence with an appropriate initial guess.
Threshold accuracy estimation: θth increases with the number of participating clients for all δ values when (a,b) = (0.35,-1), while the threshold is lower for (a,b) = (0.45,-1.05).The analysis varies participation up to 50 clients and uses responses uniformly distributed on [0.1,0.9].
Threshold accuracy estimation: Smaller δ imposes a stricter local accuracy level for attaining a high-quality centralized model.The same qualitative impact of δ is reported across the examined parameter settings.

VII. CONCLUSION

The paper presents a crowdsourcing framework that combines incentive-based federated learning with communication efficiency and admission control. It analyzes client and MEC-server interaction through a Stackelberg game and evaluates the framework with simulations and case studies.

Conclusion: The framework uses a two-stage Stackelberg game to jointly study utility maximization by participating clients and the MEC server.The analysis derives best responses and proves the existence of a Stackelberg equilibrium.
Conclusion: The framework incorporates communication efficiency during model-parameter exchange and admission control for achieving a corresponding local consensus accuracy.The admission-control strategy uses a probabilistic model to estimate threshold accuracy and required participation.
Conclusion: Future work targets resource-constrained devices, task offloading, discriminatory pricing, and cooperative data trading.The proposed extensions include replacing the central MEC server with a participating client and studying additional incentive mechanisms.

APPENDIX A KKT SOLUTION

The appendix solves the utility maximization problem using Lagrangian duality and KKT conditions. It characterizes the optimal solution through first-order and complementary-slackness conditions.

KKT solution: The utility maximization problem is convex, so its optimum can be obtained through Lagrangian duality.The appendix introduces the Lagrangian for the problem.
KKT solution: KKT conditions are formed by differentiating the Lagrangian with respect to x(ε) and the multiplier λ.The multiplier satisfies λ ≥ 0 for the associated constraint.
KKT solution: Solving the KKT system yields the optimal solution to the utility maximization problem.The appendix states the solution after solving the resulting conditions.