About Dirichlet non-iid Partition

[SpeeeedLee]

Hello, I am working on non-iid partition method in FL, and have some problems with Dirichlet partition.
In ./src/loaders/split.py, it seems like that :

1. Do not consider the situation where a client requires number of data in a class that is larger than remaining data in that class

2. Do not properly update the remaining class_idcs :
   class_indices[required_class] = class_indices[required_class][:required_counts[idx]]
   maybe it should be:
   class_indices[required_class] = class_indices[required_class][required_counts[idx]:]

3. If the satisfied_counts is less than ideal_counts in the first while loop, then in the second while loop, the client is just given another ideal_counts sample (sampled = np.random.choice(args.num_classes, ideal_counts, p=cat_param)), which may lead to the client having sample way too much than ideal_counts.

Thanks for your code and hope you can help me with these concerns

[vaseline555]

Dear @SpeeeedLee

Thank you for your report!
Since I don't have much time now, so I think I should take some time to inspect your concerns...!
Please understand my situation. 😢

Plus, could you please post some example command & corresponding result (with your expected result) that causes problems you listed?

Here are some quick notes for your concerns are:

1. To prevent the case you mentioned (i.e., 'required number of samples > remaining samples in class'), the code check if selected classes have enough samples by comparing with MIN_SAMPLES:

   Federated-Learning-in-PyTorch/src/loaders/split.py

   Line 152 in 6c07b19

   required_counts = counts * (counts > MIN_SAMPLES)

   If it isn't satisfying, please provide me a cornercase you found.
2. I think you are right, but I should double-check it again. Thank you!
3. It was somewhat intended behavior since the ideal_counts is literally an ideal sample counts that may be assigned to each client. In fact, I thought it is both inevitable and okay since the original paper did not state their original implementation in detail & I thought unbalanced sample sizes are more natural for non-IID setting in FL. Plus, when checking with pdb, the case when the while loop is iterated more than once is usually happened when samples are being depleted, i.e., only few of clients are in the queue to be assigned. Thus, the extreme case you mentioned (i.e., clients having too much sample sizes more than ideal_counts) are barely happened empirically. However, it was implemented under my subjective decision - so please provide me a feedback pertaining to current implementation. And I will check another repository, too.

Thank you, and please give me some time!

Best,
Adam

[SpeeeedLee]

Thank you for your quick reply. I am just currently curious about the implementation of the partition method proposed by [Hsu et al., 2019], and it's totally fine to take your time.

About the reply you listed, I want to ask further in the following:

1. It seems to me that this line is just for making sure whether the "selected classes" have larger number than "int(1 / args.test_size))", which is not for comparing to "remaining samples in class"
   

   Federated-Learning-in-PyTorch/src/loaders/split.py

   Line 152 in 6c07b19

   required_counts = counts * (counts > MIN_SAMPLES)

   
   https://github.com/vaseline555/Federated-Learning-in-PyTorch/blob/6c07b19c6810c82bd9455bf7364808a568376bf4/src/loaders/split.py#L111C9-L111C46

2. Say issue in 2. is now correct to the right version, then it seems to me that the last few clients will not have enough remaining samples to sample from. This is because when the alpha parameter of Dirichlet is small, then the following happens:
   a. first few clients will take almost all data of certain classes

b. if the next few clients happen to want samples from those depleted classes, the second while loop will be triggerd since the "satisfied_counts" < "ideal_counts"

c. however, the sampled number in the second while loop is identical to the first while loop :

Federated-Learning-in-PyTorch/src/loaders/split.py

Line 144 in 6c07b19

sampled = np.random.choice(args.num_classes, ideal_counts, p=cat_param)

so those clients will sample approximately 2x ideal_ccounts
(if the second sample result is again want samples from depleted classes, then a third while loop might triggered -->
~ 3x ideal counts ...)

d. then the final few clients will never have enough remaning samples.

Maybe I misunderstood some concepts of your code, so please point out if anything in above is incorrect, thank you !

[vaseline555]

Sorry for super late reply 😢
I've just completed my preliminary PhD defense and also preapring for upcoming ICML 2024 submission.
I am going to dig into this issue until the end of February. Thank you!