🤖 machine learning

WHERE to Generate Matters: Budget-Aware Synthetic Augmentation for Label Skewed Federated Learning

The paper proposes FedEAS, a budget-aware synthetic augmentation policy for label-skewed federated learning that dynamically assigns per-client generation budgets based on local label distributions to significantly reduce computational costs while recovering most of the accuracy gains of full class balancing.

Original authors: Sangwoo Lee, Sunghwan Park, Jaewoo Lee

Published 2026-07-09

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Sangwoo Lee, Sunghwan Park, Jaewoo Lee

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a group of friends trying to learn how to recognize different types of animals by sharing what they've seen in their own backyards. This is Federated Learning: everyone learns locally, then shares their "lessons" to build one smart, global brain.

However, there's a problem: Label Skew.

Alice lives in a farm and has seen 1,000 cows but zero zebras.
Bob lives in a zoo and has seen 1,000 zebras but zero cows.
Charlie has a balanced mix.

When they try to teach each other, Alice keeps thinking "everything is a cow," and Bob thinks "everything is a zebra." The group's final brain gets confused and performs poorly.

The Old Way: "Fill the Bucket"

To fix this, previous methods tried a strategy called Full Class Balancing.
Imagine a teacher telling Alice: "You need to see as many zebras as you have cows." So, Alice has to generate (or imagine) 1,000 fake zebras.

The Problem: This is incredibly expensive. It takes a huge amount of computer power and time to create all those fake animals. It's like trying to fill a swimming pool with a single teaspoon; you end up wasting a lot of effort on animals Alice already knows well, just to make the numbers match perfectly.

The New Way: FedEAS (The "Smart Budget" Strategy)

The paper introduces FedEAS, a new policy that asks two simple questions before generating any fake data:

How much fake data does this person actually need?
Where should that fake data go?

Instead of a "one-size-fits-all" rule, FedEAS gives everyone a personalized budget based on how unbalanced their backyard is.

The Analogy: The "Hungry vs. Full" Dinner Party

Think of the group as a dinner party where everyone brings a dish.

Alice (The Skewed Client): She brought 100 plates of steak but no salad. She is "starving" for salad.
Bob (The Balanced Client): He brought a perfect mix of steak and salad. He is "full."

The Old Method (Full Balancing): The host tells Alice to cook 100 more salads to match her steak, and tells Bob to cook 100 more salads just to be fair. The kitchen burns out, and the table is now covered in 200 extra salads that nobody really needed.

The FedEAS Method:

Check the Entropy (The "Hunger Meter"): The system checks how unbalanced Alice's plate is. Since she has almost no salad, her "hunger meter" is high. Bob's meter is low because he's balanced.
Assign the Budget:
- Alice gets a large budget. She is allowed to cook a few salads to fill the gap.
- Bob gets almost zero budget. He doesn't need to cook anything; he's already good.
Fill the Gaps Only: Alice only cooks the specific salad she is missing. She doesn't cook more steak (which she already has plenty of).

The Results: Doing More with Less

The paper claims this "Smart Budget" approach is a game-changer:

Massive Savings: FedEAS achieves almost the same learning success as the "fill the bucket" method but uses 94% less computer power. It's like getting a full meal for the price of a snack.
Speed: Because it generates so much less data, the whole learning process runs 3.7 times faster.
Smarter Allocation: Even if you give the "Smart Budget" method and the "Uniform" method (where everyone gets the same small amount of fake food) the exact same total budget, FedEAS wins. It puts the fake food exactly where it's needed (the missing salad), whereas the Uniform method wastes some of it on things people already have.

The "Secret Sauce"

The magic formula relies on Entropy (a math way of measuring disorder or imbalance).

If your data is messy and unbalanced (high entropy), you get a bigger budget.
If your data is neat and balanced (low entropy), you get a tiny budget.
The system stops generating data long before everyone is perfectly balanced, because the "last few pieces" are too expensive to create and don't help much.

Summary

FedEAS is like a smart shopping list for a group project. Instead of buying 100 of everything for everyone (which is wasteful), it checks who is missing what, gives them just enough to fix the gap, and stops there. It saves time, saves money, and still gets the group to the finish line.

Technical Summary: WHERE to Generate Matters: Budget-Aware Synthetic Augmentation for Label Skewed Federated Learning

Problem Statement

Label skew, where clients in a Federated Learning (FL) setting hold locally imbalanced class distributions, is a fundamental challenge that causes client drift and degrades global model accuracy. While existing synthetic data augmentation methods attempt to correct this by generating missing samples, the dominant policy—Full Class Balancing—requires every client to generate samples until all classes reach the size of the client's largest class.

This approach is computationally prohibitive. As demonstrated in the paper, achieving full balancing on a standard CIFAR-10 partition with 20 clients and high skew ( $\alpha=0.1$ ) requires generating over 226,000 synthetic samples. Furthermore, existing budget-constrained methods often allocate generation resources uniformly or based on client data size, ignoring the specific label distribution skew. The authors posit that the critical question is not just how much data to generate, but WHERE the samples should go to maximize accuracy within a fixed budget.

Methodology: FedEAS

The paper proposes FedEAS (Federated Entropy-Adaptive Synthesis), a policy that dynamically assigns a per-class generation budget to each client based on its local label distribution. Unlike previous methods that fix the total budget in advance, FedEAS derives the total generation budget from the sum of individual client budgets.

Core Mechanism

FedEAS operates on three key observations derived from the analysis of client drift and imbalance reduction:

Imbalance is concentrated: A small subset of highly skewed clients contributes disproportionately to the global imbalance.
Targeted generation is efficient: Imbalance decreases only when samples are added to scarce or absent classes; adding samples to already abundant classes yields diminishing or negative returns.
Diminishing returns: The cost to remove imbalance increases as the distribution becomes more balanced; full balancing is often unnecessary for significant accuracy gains.

The Entropy-Adaptive Budget Rule

For each client $k$ , FedEAS computes a per-class generation budget $b_k$ using the following formula:

$b_k = \lfloor \sqrt{\bar{n}_k} \cdot (1 - \tilde{H}_k) \cdot \beta \rfloor$

Where:

$\bar{n}_k = N_k / C$ is the per-class mean count for client $k$ .
$\tilde{H}_k$ is the normalized Shannon entropy of the client's local label distribution (ranging from 0 for highly skewed to 1 for perfectly balanced).
$\beta$ is a scalar budget parameter shared by all clients.
The term $(1 - \tilde{H}_k)$ ensures that highly skewed clients receive larger budgets, while near-balanced or IID clients receive almost none (reducing to standard FedAvg in the limit).
The $\sqrt{\bar{n}_k}$ term scales the budget sub-linearly with client size to prevent over-allocating to large clients.

Generation and Training

Once $b_k$ is computed, the client generates synthetic samples only for classes $c$ where the local count $n_k^c < b_k$ . The number of samples generated for class $c$ is $n_{k, \text{gen}}^c = \max\{0, b_k - n_k^c\}$ . This "fill-to-threshold" strategy ensures samples are directed exclusively to absent or scarce classes. The generation is performed once per client using a pre-trained class-conditional Diffusion Probabilistic Model (DDPM), and the generated samples are cached for use in all subsequent training rounds.

Key Contributions

Entropy-Adaptive Budget Allocation: FedEAS introduces a policy that determines both the quantity of synthetic data and its distribution ("WHERE") based on local label skew. It allocates larger budgets to skewed clients and targets only scarce classes.
Generation-Efficient Accuracy: The method recovers the majority of the accuracy gains associated with Full Class Balancing while reducing the total generation budget by 94.1% (e.g., 13,437 samples vs. 226,783 samples on CIFAR-10). This translates to a 3.7× reduction in end-to-end runtime on a single GPU.
Allocation Dominance: Under a matched-budget protocol (where all methods use the same total number of generated samples), FedEAS outperforms Uniform allocation by up to 18.82% on CIFAR-10 and CIFAR-100. It also converges up to 2× faster than "Missing-only" generation policies.

Experimental Results

The authors evaluated FedEAS on CIFAR-10 and CIFAR-100 under Dirichlet label skew ( $\alpha \in \{0.05, 0.1, 0.3\}$ ) with varying numbers of clients ( $K=20, 100$ ).

Accuracy vs. Budget: On CIFAR-10 ( $\alpha=0.1, K=20$ ), FedEAS achieved 71.65% accuracy, recovering two-thirds of the gain provided by Full-Balance (79.91%) while using only 5.9% of the synthetic samples.
Comparison with Baselines: FedEAS consistently outperformed standard FL baselines (FedAvg, FedProx, SCAFFOLD, MOON) and augmentation baselines (Uniform, Missing-only).
Budget Sensitivity: Accuracy was shown to rise monotonically with the budget parameter $\beta$ . The authors selected $\beta=12$ as the default, which satisfied two conditions: removing at least 50% of the initial imbalance score while keeping synthetic samples below 25% of the total training data.
Ablation Studies: Removing the entropy factor or replacing the sub-linear size scaling with a linear rule resulted in lower accuracy and higher generation costs, confirming the necessity of both components in the budget formula.

Significance and Claims

The paper argues that allocation is the primary design problem for synthetic augmentation in label-skewed FL. The authors claim that the total generation budget should not be a fixed, pre-determined constraint but rather a consequence of the per-client needs derived from their local distributions.

By shifting the focus from "full balancing" to "entropy-adaptive budgeting," FedEAS demonstrates that significant accuracy improvements can be achieved with minimal synthetic data generation. The method is generator-agnostic (compatible with any class-conditional generator) and requires no changes to the standard FL communication protocol or aggregation weights, making it a practical and efficient solution for mitigating client drift in heterogeneous environments.