Fairness-Aware Federated Learning with Trajectory Shapley Value

Technical Summary: Fairness-Aware Federated Learning with Trajectory Shapley Value

Problem Statement
Federated Learning (FL) enables collaborative model training across distributed clients without sharing raw data, addressing privacy and communication constraints in domains such as renewable energy, healthcare, and autonomous systems. However, conventional aggregation schemes, particularly Federated Averaging (FedAvg), rely on fixed weights (typically uniform or proportional to dataset size). These static weights fail to account for time-varying client contributions, data heterogeneity, and partial participation. Consequently, the global model may suffer from bias, instability, and vulnerability to low-quality or malicious (Byzantine) clients who exert disproportionate influence.

Existing methods for client evaluation often utilize the Shapley Value (SV) from cooperative game theory to assign fair scores based on marginal contributions. However, exact SV computation is intractable for large networks. Approximations like Monte Carlo sampling can undervalue clients who join late or participate infrequently, while gradient-based methods (e.g., Cosine-Gradient Shapley Value) may overemphasize large-magnitude updates and lack validation-based information. There is a need for a contribution metric that is temporally consistent, robust to adversarial behavior, and capable of evaluating clients based on their influence on the optimization trajectory rather than just static loss reduction.

Methodology: Trajectory Shapley Value (TSV) and FedTSV
The authors propose Trajectory Shapley Value (TSV), a novel contribution metric, and FedTSV, an adaptive aggregation algorithm.

1. Trajectory Shapley Value (TSV):

   • Concept: Instead of focusing solely on static loss reduction, TSV evaluates how a client's coalition update aligns with the optimization trajectory of the global model.
   • Reference Update: At each communication round $t$, the server computes a reference update ($\Delta^t_{val}$) by performing $K$ steps of Stochastic Gradient Descent (SGD) on held-out validation data starting from the current global model $\theta_t$.
   • Utility Function: For any coalition $S$ of participating clients, the server computes their average update ($\Delta^t_S$). A bounded per-round utility $v_t(S)$ is defined based on the distance between the coalition update and the validation reference:
     $$v_t(S) = \left( 1 + \frac{\text{Dist}(\Delta^t_S, \Delta^t_{val})^2}{\sigma_t} \right)^{-1}$$
     where $\text{Dist}$ is a metric (e.g., Euclidean) and $\sigma_t$ is a normalization factor to ensure stability near stationary points.
   • Scoring: The utility $v_t(S)$ increases as the coalition update becomes geometrically closer to the validation descent direction. The Shapley Value is estimated per round using Monte Carlo sampling on this bounded utility and accumulated over time to form a cumulative contribution score.

2. FedTSV Algorithm:

   • Adaptive Weighting: The cumulative Shapley values are converted into non-negative, time-dependent aggregation weights ($\alpha^t_i$).
   • Mechanism: Clients with positive cumulative contributions receive higher weights, while those with negative contributions (indicating malicious or consistently poor alignment) are truncated to zero.
   • Robustness: This mechanism allows the server to dynamically respond to heterogeneous and adversarial participation in real time, down-weighting malicious clients without requiring prior knowledge of their status.
   • Complexity: The method requires only one client-training pass per round plus a server-side validation pass, maintaining computational feasibility.

Key Contributions
The paper outlines three primary contributions:

1. TSV Metric: Introduction of a novel contribution metric that evaluates clients through their influence on the optimization trajectory, offering a temporally consistent alternative to conventional SV-based methods.
2. FedTSV Algorithm: Development of an adaptive-weighting algorithm that leverages TSV to dynamically adjust aggregation weights, improving fairness and robustness in heterogeneous and adversarial environments.
3. Empirical Validation: Demonstration of FedTSV's effectiveness across image-classification benchmarks (MNIST and CIFAR-10) and various FL scenarios, highlighting its advantages for privacy-preserving distributed learning.

Experimental Results
The authors evaluated FedTSV against baselines including FedAvg, Cosine-Gradient Shapley Value (CGSV), and Leave-One-Out (LOO) methods on MNIST and CIFAR-10 datasets with 100 clients (70 IID, 10 non-IID, 20 malicious).

• Convergence and Accuracy: FedTSV consistently accelerated convergence and achieved higher global accuracy compared to baselines. On CIFAR-10, FedAvg saturated at lower accuracy levels (~0.65), whereas FedTSV maintained stable and superior performance.
• Robustness: FedTSV demonstrated greater stability against label corruption and statistical heterogeneity. The performance fluctuations of FedTSV were significantly smaller than other methods, particularly on the more complex CIFAR-10 landscape.
• Contribution Assessment: Visualization of client weights showed that FedTSV effectively separated client types: malicious clients received low scores, IID benign clients concentrated in the positive region, and non-IID benign clients fell in between. In contrast, FedAvg assigned uniform weights, while CGSV and LOO showed scattered distributions or inflated weights for adversarial clients.

Significance and Claims
The paper claims that FedTSV provides a principled foundation for fairness-aware federated optimization. By integrating trajectory-based update analysis with Shapley value principles, the method offers a mechanism that is both efficient and robust. The authors assert that FedTSV improves robustness in the presence of heterogeneous and adversarial clients while preserving computational efficiency.

The paper remains modest regarding theoretical guarantees, noting that the usual convergence proofs for FedAvg do not directly apply to the time-varying objective of FedTSV, and a rigorous convergence analysis is left for future work. Future research directions identified include investigating the theoretical foundations of FedTSV from a game-theoretic viewpoint, specifically focusing on incentive compatibility and fairness in long-term collaborative learning.