acceptodds
Under review as a conference paper at ICLR 2027

Federated Complementary Label Learning

Abstract

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.

Primary area:
other topics in machine learning (i.e., none of the above)
Keywords:
Federated Learning

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_Qz4kOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies federated complementary-label learning (FCLL), where clients possess information about which classes their samples do not belong to. This paper identifies fragmented complementary supervision across clients as a central challenge, particularly under heterogeneous data distributions. To solve this challenge, this paper proposes a FCLL framework: FedCUE. FedCUE first learns from observed complementary labels and then constructs local semantic clusters using features extracted from the global encoder. Then each client uploads statistics and the server aggregates these statistics to construct global complementary evidence, which is returned to clients for joint training with local supervision. The paper gives a convergence analysis for the time-varying objective. Experiments conducted on synthetic and manually annotated complementary label datasets with varying degrees of data heterogeneity.

Critical strengths

S1. FedCUE explores a significant machine learning scenario, identifying the extension of complementary evidence sharing beyond individual clients as a new research direction. FedCUE introduces a novel pipeline grounded in federated learning insights, enabling the exchange of complementary information across different clients without directly sharing individual privacy samples. S2. Experiment section evaluates FedCUE across various levels of data heterogeneity using multiple complementary labels datasets (synthetic and manually annotated) The study encompasses a range of experiments that provide valuable empirical evidence for understanding the framework and this new topic.

Critical weaknesses

W1. Ablation study results indicate that global evidence aggregation yields only marginal performance gains (close to 0.22 pp) in main settings and can even lead to performance degradation in some cases. As the evaluations were conducted using a single random seed, the stability of these incremental benefits remains unclear. Without this global component, FedCUE may require a more substantial methodological contribution, otherwise resembles a centralized CLL approach combined with standard FedAvg. consequently, the independent contribution of the method's core distinguishing component has not been fully substantiated. More importantly, the five baseline methods used for main benchmark experiment were not specifically designed for CLL but are normal federated learning methods, making it difficult to accurately assess how FedCUE compares to CLL-specific baselines. W2. FedCUE characterizes local clusters solely using feature centers, soft complementary distributions, and support sizes. While this approach is communication-efficient (since only upload statistics), such coarse-grained statistics may fail to fully preserve information. Although the paper examines the number of clusters and the matching radius in the context of k-means, it does not further analyze the information loss resulting from those statistics, nor does it compare the method against other clustering baselines. Consequently, it remains unclear whether the proposed statistics set is sufficient to capture the information needed for reliable cross-client complementary evidence transfer.

Questions for authors

Q1. Could the authors clarify the design differences between FedCUE’s "local evidence construction" and existing feature-based CLL methods? Given the similarities between them, could the authors include federated learning versions of these methods (e.g. combining existing CLL approaches with FedAvg) for comparison under comparable experimental settings? Such a comparison would help establish the additional contribution of the proposed “global evidence aggregation mechanism”. Q2. Could the authors please clarify the exact CNN architecture and the feature extraction layers corresponding to hθh_\theta (including their output dimensions)? Do these settings remain consistent across different datasets and communication rounds? Additionally, please clarify whether the hyperparameters are fixed across all experiments or adjusted for different scenarios, and describe the process used for selecting these hyperparameters. Q3. The paper's introduction (Sec. 1) highlights FCLL collaboration among hospitals as a key application scenario. However, different hospitals may employ varying imaging equipment, acquisition protocols, or operational standards, leading to client-specific differences in feature distributions even for the same semantic categories. Since FedCUE relies heavily on feature-space clustering and cross-client cluster matching, this heterogeneity arising from variations in image style could directly affect the reliability of “global evidence aggregation mechanism”. Could the authors evaluate FedCUE in representative cross-domain settings, or provide further evidence explaining why its cluster matching and complementary evidence transfer mechanisms remain reliable under such conditions?

Reviewer_cxBNOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies federated learning with exclusively complementary-label supervision, focusing on the fragmentation of sparse class-exclusion information across Non-IID clients. It proposes FEDCUE, a multi-level complementary-evidence learning framework. Building on the observed complementary-label loss, the method uses a shared global encoder to construct local feature clusters and aggregates complementary labels from similar samples into soft exclusion distributions. The server combines uploaded cluster centers, complementary distributions, and support sizes to construct cross-client evidence, excluding the receiving client’s own contribution from the returned complementary targets. The paper derives a convergence bound that accounts for round-to-round objective variation and evaluates the method on benchmarks with synthetic and human-annotated complementary labels, including experiments on Non-IID settings, component ablations, federation size, and participation ratios. FEDCUE achieves accuracy improvements over the evaluated federated baselines. Local evidence consolidation provides the most consistent gains, while cross-client evidence offers additional improvements that depend on the dataset and degree of heterogeneity.

Critical strengths
  1. Clearly motivates the problem by connecting sparse complementary-label supervision with evidence fragmentation in federated learning. Uses a shared encoder to construct comparable features and excludes sample-level and client-level self-contributions to reduce evidence reuse.

  2. Evaluates both synthetic and human-annotated complementary labels across different heterogeneity levels, federation sizes, and participation ratios.

  3. Explicitly accounts for objective variation caused by evidence reconstruction and clearly states the scope of the theoretical analysis and privacy guarantees.

Critical weaknesses
  1. Comparisons mainly use general federated methods with the same basic complementary-label loss, with limited coverage of stronger complementary-label learning methods; The additional gains from cross-client evidence are relatively small and not consistently positive. Their stability and the propagation of incorrect exclusion evidence remain insufficiently analyzed; The experimental setup lists only one random seed, without repeated runs or uncertainty estimates.

  2. The convergence analysis includes objective variation but does not establish how the actual evidence-construction procedure satisfies the required variation-control conditions.

  3. Hyperparameter experiments mainly focus on CIFAR-20. The separate effects of the three radii and their selection without exact labels remain unclear.

  4. Client-side computation, storage, and additional synchronization overhead are not measured. Privacy risks from the uploaded statistics are also not empirically evaluated.

Questions for authors
  1. The current comparisons mainly evaluate general federated methods using the same basic complementary-label loss. This leaves uncertainty about whether FEDCUE’s advantage extends beyond this particular baseline formulation. What evidence supports its advantage over stronger complementary-label learning or local label-propagation methods?

  2. Table 2 shows a 0.35-point decrease on SVHN, while Table 11 shows a 1.75-point decrease on CIFAR-10 under strong heterogeneity. How do the authors distinguish stable gains from random variation and explain the conditions under which global evidence causes negative transfer?

  3. The convergence bound explicitly depends on VTV_T, but the analysis does not establish how the proposed evidence-reconstruction procedure controls its growth. What properties of FEDCUE support VT/(ηHT)→0V_T/(\eta HT)\rightarrow 0, particularly around the warm-up transition and under strong heterogeneity?

  4. The radius analysis changes rLr_L, rGr_G, and rRr_R simultaneously, leaving their individual effects unclear. How are the three radii selected for a new dataset when exact class labels are unavailable?

  5. Appendix F.1 quantifies the additional communication volume, but does not capture the runtime and memory costs of feature extraction, clustering, evidence retrieval, and the additional synchronization stage. What is the resulting end-to-end training overhead relative to FedAvg, including peak client memory usage and synchronization delays?

  6. Privacy-sensitive applications are a central motivation, and small-support clusters or evidence drawn from only a few clients may expose local information. Under the assumed threat model, what information can the server and participating clients infer from the uploaded summaries and returned evidence banks?

Reviewer_8ZCuOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies federated learning with complementary labels, which indicate classes that an example does not belong to. FEDCUE aggregates exclusion information within local feature clusters and exchanges cluster summaries across clients. The reconstructed targets supplement the observed labels during training. Experiments evaluate the method on synthetic and human-annotated datasets under different levels of client heterogeneity.

Critical strengths
  • The paper studies an interesting problem, federated learning with complementary labels when exact labels are difficult to obtain.
  • The experiments include both synthetic and human-annotated complementary labels. The human-data results provide evidence that the method can handle some annotation bias and noise.
Critical weaknesses
  • It is unclear how much useful exclusion information other clients add. The paper argues that clients can help each other by providing different exclusions for similar examples. However, annotators may favor familiar or easy exclusions [r1, r2], so different clients could repeatedly provide the same information. Uniformly sampled synthetic labels encourage more diverse exclusions. The human-label experiments include annotation bias, but do not directly measure what additional exclusion information global sharing provides. It would be helpful to measure this contribution and test whether global sharing still improves over local evidence when clients increasingly favor the same exclusions.
  • Global evidence provides small or inconsistent gains over local evidence. In Table 2, adding global evidence changes accuracy by +0.61, +0.49, −0.35, and +0.14 percentage points across the four datasets. Under stronger heterogeneity, Table 11 shows a larger gain on CIFAR-20 (+2.45), but a decrease on CIFAR-10 (−1.75). Local evidence accounts for much of the improvement.
  • The comparisons do not establish improvement over existing complementary-label enhancement methods. Lin et al.’s label augmentation already constructs soft complementary targets from neighboring examples and is cited in the submission [r3]. A client-local adaptation combined with FedAvg is the most direct missing comparison, particularly because local evidence accounts for much of FEDCUE’s gain. PLNL is another suitable comparator [r4].
  • The paper does not measure whether transferred exclusions are correct. Similar examples can have different true labels, so transferring exclusions can teach the model to reject the correct class. Figure 5 reports accuracy versus radius, but does not directly evaluate this error. It would be helpful to measure the average exclusion probability assigned to the recipient’s true class, separately for local and global targets.
Questions for authors
  • What additional valid exclusion information does global exchange provide when clients favor the same easy exclusions? Does it still improve over the local-evidence variant?
  • How does FEDCUE compare with an established complementary-label method, such as Lin et al.’s label augmentation [r3], applied locally with FedAvg under matched feature access and training budgets?
  • How much exclusion probability do local and global targets assign to the true class, compared with the original annotations? How does this change with the radius?
  • Please specify the CNN architecture and the validation data and criteria used to select hyperparameters.
  • What explains the apparent differences between FEDCUE and FedAvg in Figure 3 before the 20-round warm-up ends? Do they use the same initialization and training procedure during warm-up?

[r1] Xiyu Yu, Tongliang Liu, Mingming Gong, and Dacheng Tao. “Learning with Biased Complementary Labels.” European Conference on Computer Vision (ECCV), 2018. [r2] Hsiu-Hsuan Wang, Tan-Ha Mai, Nai-Xuan Ye, Wei-I Lin, and Hsuan-Tien Lin. “CLImage: Human-Annotated Datasets for Complementary-Label Learning.” Transactions on Machine Learning Research, 2025. Originally released as arXiv:2305.08295 in 2023. [r3] Wei-I Lin, Gang Niu, Hsuan-Tien Lin, and Masashi Sugiyama. “Enhancing Label Sharing Efficiency in Complementary-Label Learning with Label Augmentation.” arXiv preprint arXiv:2305.08344, 2023. [r4] Yuhang Li, Zhuying Li, and Yuheng Jia. “Complementary Label Learning with Positive Label Guessing and Negative Label Enhancement.” International Conference on Learning Representations (ICLR), 2025.

2 comments
AuthorsOpenReview ↗

Response to Reviewer 8ZCu (Part 1)

Dear Reviewer 8ZCu,

Thank you for recognizing the value of our research problem and our evaluation on synthetic and human-annotated complementary-label datasets. To address your main concerns, we have added a CLL-specific federated comparison, a three-seed paired ablation, a shared exclusion-preference stress test, and direct diagnostics of reconstructed evidence.

W1 & Q1: Can Global Sharing Provide Additional Useful Exclusion Information?

We conduct a new shared exclusion-preference stress test to examine the role of global sharing when clients provide increasingly similar exclusion information. This experiment further clarifies the importance of evidence complementarity for effective collaboration.

On CIFAR-20 with β=0.1 and seed=2026, we assign one shared non-ground-truth exclusion class to each ground-truth class and progressively increase the proportion of annotations using that class. A strength of 0 preserves the original complementary labels, while 0.5 and 0.9 represent moderate and strong shared preferences, respectively.

Shared Preference StrengthLocal-only Accuracy (%)Full Accuracy (%)Full−Local (pp)
024.3824.53+0.15
0.510.859.33−1.52
0.95.263.71−1.55

Without an additional shared preference, Full improves over Local-only by 0.15 pp, supporting the value of cross-client evidence in supplementing local supervision. As the shared preference becomes stronger, accuracy decreases substantially for both methods, and global sharing no longer provides additional gains. This trend is consistent with our emphasis on evidence complementarity: effective collaboration depends on usable complementary supervision rather than simply increasing the amount of shared information. This stress test further characterizes collaborative performance under shared annotation preferences.

W2: Contribution and Stability of Global Evidence

We conduct a new three-seed paired ablation to quantify the average contribution of global evidence and its variation across random seeds, complementing the single-run results in the original submission.

We compare Full and Local-only while fixing data partitions, complementary labels, augmentation, batch, radii, and cluster numbers within each seed. Only global evidence is enabled or disabled:

Dataset, β=0.5Local-only Accuracy (%)Full Accuracy (%)Mean Gain (pp)
CIFAR-1067.74 ± 2.7067.97 ± 2.52+0.23
CIFAR-2024.79 ± 1.5824.75 ± 1.16−0.04
CL-CIFAR209.66 ± 0.299.80 ± 0.33+0.14

Although gains vary across datasets, the macro-averaged gain remains positive, indicating that global evidence can provide additional performance benefits overall.

W3 & Q2: Federated Comparison with Existing CLL Methods

We additionally evaluate the suggested Local LabelAug + FedAvg to directly compare FedCUE with local complementary-label augmentation in federated settings.

LabelAug enhances supervision by propagating complementary labels among similar samples. Under heterogeneous FL, decentralized data and skewed client distributions restrict local-neighborhood coverage. Our adaptation constructs graphs and augments labels within each client, while the server performs standard FedAvg. FedCUE further supplements locally unavailable information through cross-client cluster-level statistics.

We report accuracy (%) at round 100 over three seeds (2026/2027/2028):

MethodCIFAR-10, β=0.1CIFAR-20, β=0.1
Local LabelAug + FedAvg21.12 ± 4.7112.82 ± 1.81
FedCUE Full48.21 ± 2.2423.71 ± 0.98

FedCUE outperforms Local LabelAug + FedAvg in both settings. This comparison supports the value of designing an evidence-learning mechanism specifically for federated settings: simply combining local label augmentation with parameter aggregation is insufficient to achieve the performance of FedCUE.

We will release the federated adaptation implementation, feature-access mechanism, and complete training configurations to facilitate verification of the comparison settings. These results apply to the specific client-local federated adaptation and should not be generalized to the performance of the original centralized LabelAug.

AuthorsOpenReview ↗

Response to Reviewer 8ZCu (Part 2)

W4 & Q3: Correctness and Control of Transferred Evidence

We provide new diagnostics of true-class exclusion probability mass to directly examine whether reconstructed evidence incorrectly excludes the receiving sample's ground-truth class. The following table reports the average true-class exclusion probability mass over rounds 21–100, where lower values are better:

DatasetβOriginal AnnotationsLocal TargetGlobal Target
CIFAR-100.100.008710.07434
CIFAR-200.100.016690.04394
SVHN0.500.001610.00929
CL-CIFAR100.10.039300.041910.06608

The diagnostics confirm that reconstructed evidence contains incorrect exclusion information. This metric measures the exclusion probability mass assigned to the ground-truth class, rather than the classification error rate. Local and Global targets are evaluated separately on samples satisfying their respective filtering criteria.

FedCUE uses distance-based filtering and reliability weighting to limit the influence of mismatched evidence. The new independent radius experiments further demonstrate that controlling the range of evidence utilization affects final accuracy. We independently vary the three radii, fixing the other two at 0.5, on CIFAR-20 with β=0.1:

Independently Varied ParameterAccuracy at 0.4 (%)Accuracy at 0.6 (%)
Local reliability radius rLr_L25.5224.04
Global matching radius rGr_G24.5324.36
Retrieval radius rRr_R24.7024.22

For all three stages, a radius of 0.4 yields higher accuracy than 0.6, indicating that the range of evidence utilization affects final performance. We will consider reducing incorrect cross-class evidence propagation and improving evidence reliability as directions for future work.

Q4: CNN Architecture and Hyperparameter Selection

FedCUE uses a nine-convolution-layer CNN with 128-dimensional, L2-normalized features extracted after global average pooling and before the classifier.

The network has three convolutional blocks with channels 128–128–128, 256–256–256, and 512–256–128, followed by global average pooling and a linear classifier. The feature dimension remains 128 across datasets and communication rounds, while input channels and classification heads are dataset-specific. Evidence is constructed using a frozen copy of the current global model each round, with encoder parameters updated across rounds.

Hyperparameter selection. Evidence-related parameters were initially assigned manually predefined values, without systematic search or separate tuning for different β values. Fig. 5 and supplementary experiments examine their sensitivity. We will release the code, complete configurations, and feature extraction implementation, and specify the parameter-setting procedure in the revised manuscript.


Dear Reviewer 8ZCu,

Thank you again for your careful evaluation and constructive feedback. We sincerely appreciate your thoughtful comments, which have helped us further clarify and strengthen our work. We hope that our responses and additional experiments have adequately addressed your questions and concerns.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.