Federated Complementary Label Learning

Federated learning enables multiple clients to collaboratively train a global model without sharing their raw data, making it well suited to privacy-sensitive applications such as healthcare and finance. In many such scenarios, however, obtaining exact class labels requires substantial domain expertise, while ruling out unlikely classes is considerably easier. This naturally gives rise to federated complementary-label learning, where each client holds only class-exclusion supervision. A key challenge in this setting is that complementary evidence is inherently sparse. Moreover, data heterogeneity further fragments such evidence across clients, making it difficult for individual clients to obtain sufficiently informative supervision. To address this problem, we propose FedCUE, a multi-level complementary-evidence learning framework that progressively consolidates fragmented exclusion information from individual samples to local semantic clusters and further to cross-client global clusters. Specifically, FedCUE associates feature clusters with soft complementary-label distributions, allowing semantically similar samples to share exclusion knowledge locally and enabling compatible complementary evidence to be aggregated across clients without exchanging raw data. We further establish a convergence guarantee for the proposed federated optimization framework under standard assumptions. Extensive experiments on synthetic and human-annotated complementary-label benchmarks under various Non-IID settings show that FedCUE consistently improves federated complementary-label learning. The gains remain robust across federation scales and participation levels, supporting the proposed multi-level evidence design.