FLOSS: Federated Learning with Opt-Out and Straggler Support

1. Problem Statement

Federated Learning (FL) allows models to be trained across distributed clients without sharing raw data, preserving privacy. However, FL systems face significant challenges regarding missing data, which degrades model performance and introduces statistical bias. The paper identifies two primary sources of missing data:

1. Stragglers: Devices with heterogeneous capabilities (e.g., poor network connectivity, low battery) that fail to upload gradients within a time limit.
2. User Opt-Out: Modern privacy agreements allow users to withdraw consent for data sharing at any time. Users may opt out due to dissatisfaction with model predictions or concerns over sensitive data.

The Core Issue:
While missing data that is "Missing Completely at Random" (MCAR) is manageable, the missingness in FL is often Missing at Random (MAR) or Missing Not at Random (MNAR).

• MAR: Missingness depends on observable factors (e.g., rural users with poor networks are more likely to be stragglers).
• MNAR: Missingness depends on the unobserved data itself (e.g., a user opts out because the model makes a specific, sensitive prediction on their data).

Standard FL aggregation (averaging gradients from available users) assumes random missingness. When data is systematically missing (MAR/MNAR), the resulting model updates are biased, leading to reduced accuracy and potential unfairness, even as the number of participating devices increases.

2. Methodology: FLOSS

The authors propose FLOSS, a system that mitigates bias from missing data using Inverse Probability Weighting (IPW) and Missing Data Graphical Models (m-DAGs).

A. Formal Modeling with m-DAGs

The authors use Missing Data Directed Acyclic Graphs (m-DAGs) to formalize the causal relationships between variables:

• Variables: $X$ (features), $Y$ (outcomes), $G(\theta)$ (gradients), $D$ (user/device info), $R$ (responsiveness indicator, 1 if present, 0 if missing), and $S$ (user satisfaction).
• Causal Structure: The model posits that user responsiveness ($R$) is influenced by device attributes ($D$) and user satisfaction ($S$). Crucially, satisfaction ($S$) is influenced by the model's performance on the user's specific data ($X, Y$).
• MNAR Identification: Because $R$ depends on $S$, and $S$ depends on $X/Y$, the missingness is MNAR. Standard IPW cannot be applied directly because the probability of missingness depends on unobserved variables.

B. The Shadow Variable Solution

To handle MNAR data without violating privacy (i.e., without seeing $X$ or $Y$), FLOSS introduces a Shadow Variable ($Z$), a subset of observed user info ($D$).

• Assumption: $Z$ influences the data processed ($X, Y$) and thus satisfaction ($S$), but does not directly influence the decision to drop out ($R$) once satisfaction is accounted for.
• Mechanism: By leveraging the relationship between $Z$, $S$, and $R$, the system can estimate the probability of a user being present, $p(R=1 | D', S_{miss})$, even when $S$ is partially missing. This is achieved by solving a system of moment equations (Eq. 1 in the paper) to find parameters $\beta$.

C. Reweighted Device Selection

Once the probability of participation ($\pi$) is estimated for each user, FLOSS modifies the FL training loop:

1. Prompting: The server prompts users for participation and satisfaction feedback (Figure 1b).
2. Weight Estimation: The server calculates $\pi$ for responsive users using the shadow variable method.
3. Weighted Sampling: Instead of uniform random sampling, the server selects $k$ users for the next round with probability proportional to $1/\pi$.
4. Aggregation: Gradients from selected users are aggregated. By weighting users inversely to their probability of being observed, the system effectively reconstructs the distribution of the full population, minimizing the true unobserved risk.

3. Key Contributions

1. Formal Framework: The paper provides the first formal m-DAG model for missing data in FL that explicitly accounts for user opt-out policies and stragglers, distinguishing between MAR and MNAR scenarios.
2. Privacy-Preserving Correction: It proposes a method to correct MNAR bias using Inverse Probability Weighting without requiring the central server to access raw user data or violating opt-out agreements. It relies only on observed metadata ($D$) and satisfaction feedback ($S$).
3. Shadow Variable Technique: It adapts causal inference techniques (shadow variables) to the FL setting, allowing the estimation of missingness probabilities even when the missingness mechanism depends on unobserved outcomes.
4. Algorithm Implementation: The paper presents Algorithm 1, a complete pseudocode for the FLOSS system, integrating differential privacy (noisy/clipped gradients) and weighted sampling.

4. Experimental Results

The authors implemented a prototype in Python (with a future migration to the Flower framework) and conducted simulations on a binary classification task.

• Setup: They compared four scenarios:
  1. No missing data (Baseline).
  2. MNAR data with no correction.
  3. MNAR data with "Oracle" correction (assuming perfect knowledge of missingness probabilities).
  4. MNAR data with FLOSS correction.
• Findings:
  • Bias Impact: Uncorrected MNAR data significantly degraded model accuracy compared to the baseline, even with a large number of clients.
  • FLOSS Efficacy: The FLOSS-corrected model (red line) closely matched the performance of the "No missing data" baseline (blue line) and the Oracle correction (green line).
  • Scalability: Simply adding more clients did not fix the accuracy gap in the uncorrected scenario. FLOSS successfully closed this gap, demonstrating that correcting for systematic missingness is more critical than increasing sample size.

5. Significance and Conclusion

Significance:

• Real-World Applicability: As privacy regulations (GDPR, CCPA) and user awareness grow, opt-out rates in FL will increase. FLOSS provides a necessary mechanism to maintain model utility in this environment.
• Fairness: By correcting selection bias, FLOSS indirectly improves algorithmic fairness, ensuring that marginalized groups (who may be more likely to opt-out or be stragglers) are not underrepresented in the final model.
• Theoretical Advancement: It bridges the gap between causal inference (missing data theory) and distributed machine learning, offering a rigorous mathematical approach to a practical engineering problem.

Conclusion:
FLOSS demonstrates that it is possible to build robust Federated Learning systems that tolerate both infrastructure failures (stragglers) and user privacy choices (opt-outs) without compromising model accuracy. By reweighting gradient aggregation based on estimated participation probabilities, FLOSS mitigates the bias introduced by systematic missing data, paving the way for more reliable and fair privacy-preserving AI.