acceptodds
Under review as a conference paper at ICLR 2027

Minimizing Label Distribution Shift through Client Selection in Federated Learning

Abstract

Federated learning (FL) is a distributed learning approach that trains a machine learning model using data from multiple clients without exposing each client's local data. Although standard FL assumes a uniform test label distribution, many practical applications, such as medical diagnosis, involve known or estimated test label distributions that often deviate from uniformity. Existing client selection strategies are either limited by client's label distribution estimation or restricted to uniform test label distributions, and furthermore, they lack rigorous theoretical guarantees in non-convex settings. To bridge this gap, we propose FedMLS, a novel client selection strategy that minimizes the Kullback-Leibler (KL) divergence between the test label distribution and the time-averaged label distribution of the selected clients. We establish convergence guarantees for FedMLS under test label distribution shift and extend our analysis to scenarios with loss reweighting. Moreover, we design an iterative mechanism leveraging Fully Homomorphic Encryption (FHE) to implement FedMLS without exposing sensitive clients' label statistics. Extensive experiments on the CIFAR-100, iNaturalist-User-120k, and Shakespeare datasets demonstrate that FedMLS consistently outperforms state-of-the-art baselines, achieving higher test accuracy and up to 10.7× faster convergence than FedAvg (4.6× when combined with FedIR loss reweighting).

Primary area:
optimization
Keywords:
Federated Learning, Client Selection, Label Shift

Reviews

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

The paper studies federated learning for a known target label distribution when only a subset of clients can participate in each round. The objective is to select clients so that training is better aligned with the distribution expected at deployment.FedMLS does not require every round to match the target exactly. Instead, it matches the average label mixture formed by participating clients across rounds. Minimum participation rates limit prolonged exclusion of clients, and virtual queues guide the selections. The paper provides theoretical analyses, an encrypted implementation, and experiments on four datasets, including combinations with FedIR, component ablations, and misspecified target priors.

Critical strengths
  1. The method combines target-distribution matching with participation coverage in an implementable framework. It considers both alignment with deployment needs and reliance on a small subset of clients. The contribution lies in this constrained scheduling design, not merely in using KL divergence.

  2. Four datasets and eight-run summaries provide substantial empirical evidence. In Table 8, adding matching while retaining minimum participation rates raises accuracy from 33.17% to 36.48% without FedIR, and from 42.92% to 44.61% with FedIR. Matching therefore provides an additional benefit; the gains cannot all be attributed to the participation constraint.

Critical weaknesses
  1. The implemented joint algorithm and the explanation of its gains are not yet clearly connected. Equation 1 uses reweighted distributions, whereas Algorithm 2 displays raw distributions. Under Theorem 4's full-support, exact-reweighting assumptions, the label mismatch is already zero. Improved accuracy for the combination is not contradictory, but cannot automatically be explained by further reducing that mismatch. The paper needs to identify the actual selection objective and distinguish matching, participation coverage, and scheduling effects.

  2. The privacy claim is broader than the established result. Theorem 2 analyzes the Service's aggregate observations, but Algorithm 2 also gives the Selector client-specific optimization feedback together with its known auxiliary variables. Protection under this different view is not established. The paper needs an argument covering these outputs or a narrower claim; this concern does not establish an actual data breach.

Questions for authors
  1. For the FedIR combination, does selection use raw or reweighted distributions? Please specify loss normalization and the treatment of missing classes. Original FedIR uses mini-batch self-normalization; does this implementation do the same? When ideal reweighting has already eliminated label mismatch, what evidence explains the additional selection benefit?

  2. On-Demand FL and FedPALS already exploit the target through sampling or aggregation weights. What does the long-run queue add? Existing evidence, or a static-sampling control with the same objective, minimum-rate constraints, and participation budget, could distinguish matching, coverage, and scheduling effects. Cumulative mismatch and participation-coverage trajectories are another option; these are alternatives, not a request for every comparison.

  3. How are individual label statistics protected when the Selector knows the auxiliary variables and receives client-specific feedback? Label-aware secure aggregation also treats weights derived from label statistics as confidential. Please explain why the intermediate outputs preserve the claimed protection, or explicitly restrict the guarantee to the Service's aggregate view. This question concerns the stated non-colluding model.

References:

[1] Edvin Listo Zec, Adam Breitholtz, and Fredrik D. Johansson. Overcoming label shift with target-aware federated learning. arXiv:2411.03799v2, revised 2025.

[2] Isu Jeong and Seulki Lee. On-Demand Federated Learning for Arbitrary Target Class Distributions. AISTATS 2024, PMLR 238.

[3] Tzu-Ming Harry Hsu, Hang Qi, and Matthew Brown. Federated Visual Classification with Real-World Data Distribution. ECCV 2020.

[4] Aftab Akram, Harry N. H. Pham, Melek Önen, and Clémentine Gritti. SAAFL: Secure Aggregation for Label-Aware Federated Learning. IFIP SEC 2025. DOI: 10.1007/978-3-031-92882-6_3.

1 comment

We thank the reviewer for the detailed and technically precise questions.

Question 1: For the FedIR combination, does selection use raw or reweighted distributions? Please specify loss normalization and the treatment of missing classes. Original FedIR uses mini-batch self-normalization; does this implementation do the same? When ideal reweighting has already eliminated label mismatch, what evidence explains the additional selection benefit?

Reply: When applying FedIR, FedMLS uses the reweighted label distribution for the selection. We follow FedIR’s mini-batch normalization of the importance weights. A class that is missing from client nn is given zero weight. This has no effect on training since the client has no samples of that class (fn,k=0f_{n, k} = 0).

Why Eq. (1) is not zero. If every client held every class, then D=0D = 0, as the reviewer notes. However, In our experiments, clients hold on average 5.89 of 1,203 classes (iNaturalist-Users-120k) and 53.70 of 79 classes (Shakespeare). Eq. (1) then becomes D(Sˉ,λ)=−∑kptest,klog⁡(1M∑nSˉn1[k∈Kn]Zn)⏟coverage of class k.D(\bar S, \lambda) = -\sum_{k} p_{test,k} \log \underbrace{\Big( \frac{1}{M} \sum_{n} \bar S_n \frac{\mathbb 1[k \in \mathcal K_n]}{Z_n} \Big)}_{\text{coverage of class } k}.

where Kn\mathcal K_n is the support of client nn's label distribution and Zn=∑j∈Knptest,jZ_n = \sum_{j \in \mathcal K_n} p_{test,j}.

This objective is zero only if every test class receives its full target mass from the selected clients. It heavily penalizes classes that are frequent at in test set but held by few selected clients. FedIR corrects the label proportions within each client but cannot supply classes missing from the selected clients. The remaining shift D(Sˉ,λ)D(\bar{S}, \lambda) can only be reduced by choosing which clients participate, which is what FedMLS does.

Question 2: On-Demand FL and FedPALS already exploit the target through sampling or aggregation weights. What does the long-run queue add? Existing evidence, or a static-sampling control with the same objective, minimum-rate constraints, and participation budget, could distinguish matching, coverage, and scheduling effects. Cumulative mismatch and participation-coverage trajectories are another option; these are alternatives, not a request for every comparison.

Reply: The problem can be formulated as static-probability sampling with the same objective and constraints. However, in the cross-device FL setting, client availability is random and its distribution must be known for this approach. In contrast, drift-plus-penalty framework dynamically adjusts to the client availability with a provable bound on the objective.

Question 3: How are individual label statistics protected when the Selector knows the auxiliary variables and receives client-specific feedback? Label-aware secure aggregation also treats weights derived from label statistics as confidential. Please explain why the intermediate outputs preserve the claimed protection, or explicitly restrict the guarantee to the Service's aggregate view. This question concerns the stated non-colluding model.

Reply: The Selector receives the scores h(r)=VMp⊤u(r)h(r) = \frac{V}{M}\mathbf p^\top u(r) in plaintext over many iterations, and it knows its own a(r)a(r). This is sufficient to reconstruct pnp_n. We therefore revise the protocol so that the Selector never sees h or a in plaintext.

Revised protocol (two-party secret sharing). We split aa, hh, and the queue AA into additive shares x=xSel+xSvcx = x^{\mathrm{Sel}} + x^{\mathrm{Svc}}, held by the Selector and the Service, respectively. Each share is individually masked by random noise, so neither party ever holds these quantities in plaintext. The protocol changes as follows:

  1. Masking. The Service keeps its mask ξ2\xi_2 instead of sending it to the Selector. The decrypted h+ξ2h + \xi_2 becomes the Selector's share, and −ξ2-\xi_2 becomes the Service's share.
  2. Gradient step. Each entity E∈E \in {Sel, Svc} computes aE−μ(AE−hE)a^{E} - \mu(A^{E} - h^{E}) on its own shares, with no communication.
  3. Projection, selection, and queue update. The projection onto [0,1]N[0,1]^N, the top-MM selection, and the queue update use standard two-party secure comparison, which outputs fresh shares. Only S(t)S(t) is revealed, and only to the Selector.
  4. Initialization and stopping. Each party draws its share of a(0)a(0) at random, and the number of inner iterations is fixed so that the stopping time reveals nothing.

Since selection is model-independent, this computation can run ahead of training. It adds O(N)O(N) secure comparisons per inner iteration and one secure top-MM selection per round.

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

This paper proposes FedMLS, a client selection method that aims to match the long-term average label distribution of selected clients to a target test distribution. The theoretical analysis is provided. Experiments on multiple classification benchmarks show improvements over baselines.

Critical strengths
  1. Test-time label shift is realistic in many FL scenarios.

  2. The idea of selecting clients to better match the target test distribution is easy to understand and well motivated.

  3. The theoretical analysis is convincing and may inspire future studies.

Critical weaknesses
  1. The method requires the estimation of the target test label distribution, and it also relies on client label distribution information. This is a very strong assumption in FL.

  2. The framework can only be applied on label distribution shift problems on classification tasks.The method is hard to benefit other tasks like feature shifts, concept shifts, or generation, representation learning tasks. This limit the scope of this paper.

  3. The FHE-based scheme assumes non-colluding parties and a semi-honest threat model, which may be weaker than real deployment settings.

Questions for authors
  1. How robust is FedMLS to realistic misspecification of the target test distribution? Please provide some analysis.

  2. Can the method work when client label distributions are only partially available? For example, only partial clients provide the information, or the information is not convincing

2 comments

We thank the reviewer for the constructive feedback on our assumptions and scope, which prompted new robustness experiments on target misspecification and partial label reporting.

Weakness 1: The method requires the estimation of the target test label distribution, and it also relies on client label distribution information. This is a very strong assumption in FL.*

Reply: Our method needs only the label distribution ptestp_{test} of the target population, information that organizations often already hold. For example, a retailer typically tracks the share of sales per product category without logging customer features [1]. Where ptestp_{test} is not recorded, it can be specified by the deployer or estimated with label-shift estimators [2]. Because such estimates are imperfect, we evaluate misspecification directly in Section G.4.

We assume each client reports its label distribution once. This requires no capability beyond standard supervised FL, since clients already compute their sample count for aggregation, and counting per class is the same pass over local labels. Moreover, under our privacy-preserving mechanism, selection is computed on encrypted counts.

[1] Zec, Edvin Listo, Adam Breitholtz, and Fredrik D. Johansson. "Overcoming label shift in targeted federated learning." (2024).

[2] Lipton, Zachary, Yu-Xiang Wang, and Alexander Smola. "Detecting and correcting for label shift with black box predictors." International Conference on Machine Learning. PMLR, 2018.

Weakness 2: The framework can only be applied on label distribution shift problems on classification tasks.The method is hard to benefit other tasks like feature shifts, concept shifts, or generation, representation learning tasks. This limit the scope of this paper.

Reply: We respectfully maintain that this is a significant problem. Label skew is among the most common sources of heterogeneity in FL, classification is the standard evaluation setting in the literature [1, 2], and existing methods suffer performance degradation under it. Our method improves on them by 1.56–2.28 percentage points across real-world tasks and datasets.

Feature shift, concept shift, and generative tasks involve different distributional structures and are important problems in their own right, but they are outside the scope of this work.

[1] Caldas, Sebastian, et al. "LEAF: A benchmark for federated settings." arXiv preprint arXiv:1812.01097 (2018).

[2] Lai, Fan, et al. "FedScale: Benchmarking model and system performance of federated learning at scale." International Conference on Machine Learning. PMLR, 2022.

Weakness 3: The FHE-based scheme assumes non-colluding parties and a semi-honest threat model, which may be weaker than real deployment settings.

Reply: We agree that the semi-honest, non-colluding model is weaker than a fully malicious one. However, both assumptions apply only to the server-side parties, which are entities chosen by the deployment operator rather than a large population of untrusted devices. This makes the model realizable in practice by assigning the roles to independent organizations.

Question 1: How robust is FedMLS to realistic misspecification of the target test distribution? Please provide some analysis.

Reply: We additionally test a systematic, confidently wrong estimate, as if it had been taken from a different population, region or time period. The server runs FedMLS with $ p_{est} = (1 - \zeta) p_{test} + \zeta \pi (p_{test}) $ where π\pi randomly reassigns the class labels so that no class keeps its own probability, and ζ ∈ {0.25, 0.5, 1} is the fraction of the estimate that is wrong. At ζ = 1 the estimate is exactly as skewed as the true distribution, but its probability sits on the wrong classes.

Methodαtest=10\alpha_{test} = 10αtest=1\alpha_{test} = 1αtest=0.1\alpha_{test} = 0.1
FedAvg21.55 ± 0.4224.82 ± 0.3221.85 ± 0.63
FedMLS (true ptestp_{test})24.82 ± 0.2527.57 ± 0.4436.48 ± 0.40
FedMLS (ζ = 0.25)23.98 ± 0.3627.80 ± 0.5224.29 ± 0.91
FedMLS (ζ = 0.5)23.78 ± 0.3427.77 ± 0.4322.39 ± 0.41
FedMLS (ζ = 1)24.00 ± 0.2727.23 ± 0.2622.76 ± 0.47

Under mild and moderate label shift (αtest\alpha_{test} ∈ {1, 10}), FedMLS stays within 0.8 points of its accuracy with the true distribution, and above FedAvg, even when the estimate is entirely wrong (ζ = 1). It does not need an accurate estimate of ptestp_{test} in these settings.

Question 2: Can the method work when client label distributions are only partially available? For example, only partial clients provide the information, or the information is not convincing

Reply: FedMLS does not require every client to report its label distribution. A client that declines (for privacy reasons, missing labels, or stale metadata) is assigned the uniform distribution 1/K1/K by the server, and selection proceeds unchanged. This fallback is safe because participation is still guaranteed by the minimum-rate constraint, which depends only on client sample size.

Setup: We set ρ∈\rho \in {0, 0.05, 0.1, 0.3}, the fraction of clients that refuse to share their label distribution and instead receive the uniform fallback. We evaluate on CIFAR-100 with αtest=0.1\alpha_{test} = 0.1.

ρ\rhoTest Accuracy
0 (full report)36.48 ± 0.40
0.0535.54 ± 0.41
0.135.01 ± 0.75
0.334.86 ± 0.23

With up to 30% of clients withholding their label distribution, FedMLS loses at most 1.62 points of accuracy. This is because these clients are rarely selected, so the label distribution of the selected clients remains nearly as close to the test distribution as under full reporting.

Reviewer_kNeZOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

This paper proposes FedMLS, a client-selection method for federated learning with a known target label distribution. It matches the selected clients’ label proportions across rounds to the target while enforcing minimum participation rates. The paper provides convergence analyses, an encrypted implementation, and experiments on several datasets.

Critical strengths
  • The paper addresses label-distribution differences between training and deployment. Using target label statistics to guide client selection is a reasonable approach.
  • The experiments cover multiple datasets, eight random seeds, component ablations, and inaccurate target priors. They include On-Demand FL with true label statistics and evaluate all baselines with and without loss reweighting.
Critical weaknesses
  • The objective used in the FedIR experiments is unclear. With the stated FedIR weights and every class present on every client, Eq. (1) is zero for any client selection. Algorithm 2 instead uses the original label proportions. The paper attributes gains under FedIR to distribution matching without explaining this discrepancy. Please clarify which objective produced the reported results and how missing classes are handled.
  • The paper does not show whether Theorem 3 applies to its experiments. Without FedIR, the theorem’s condition fails if any possible group of selected clients lacks a target class. The authors should check whether their experimental partitions satisfy this condition.
  • The privacy guarantee is incomplete. Theorem 2 shows that the Service cannot uniquely recover the complete set of client label distributions. It does not address partial or approximate inference. The Selector also receives repeated scores derived from each client’s label distribution, but the theorem does not analyze what these scores reveal.
  • Important comparisons are missing. FedPALS [1] uses known client and target label distributions to adjust model aggregation. A comparison under the same participation budget would test whether FedMLS’s client selection offers an advantage over this alternative. The participation-only ablation should also be repeated on another main dataset to check whether label matching contributes consistently across datasets. In Table 8, participation control accounts for most of the improvement, while label matching adds 3.31 percentage points.
  • The reported speedups do not account for the full selection cost. The reported speedups count training rounds. Appendix E.2 measures computation time per inner iteration, excluding communication and setup. It would be great to have the total wall-clock time comparison.

[1] Listo Zec, E., Breitholtz, A., & Johansson, F. D. (2026). Overcoming label shift in target-aware federated learning. Transactions on Machine Learning Research.

Questions for authors
  • Under FedIR, does client selection optimize Eq. (1) using reweighted label distributions, or use the original distributions as in Algorithm 2? How are classes absent from a client handled?
  • Does Theorem 3’s condition (H>0) hold for the experimental partitions without FedIR? Which solver and stopping criterion were used for Eq. (4) during training? If Algorithm 2 was used, how were zero denominators handled? How does approximate optimization affect Theorem 1’s guarantee?
  • Can the Service estimate individual clients’ label proportions from its aggregates, even when exact recovery is impossible? What can the Selector infer from its repeated client-specific scores?
  • Can you compare with FedPALS using the same number of clients per round and training rounds? Can you also repeat the participation-only ablation on another main dataset to measure the additional gain from label matching?
  • How do the methods compare in wall-clock time to reach the same test accuracy?
  • The validation and test sets have different class proportions. Did you reweight validation accuracy to match the test distribution when choosing hyperparameters?
2 comments

We sincerely thank the reviewer for the thorough and rigorous review. The comments on the FedIR objective, the theoretical conditions, and the privacy protocol have substantially improved the clarity and soundness of our work.

Weakness 1: The objective used in the FedIR experiments is unclear. With the stated FedIR weights and every class present on every client, Eq. (1) is zero for any client selection. Algorithm 2 instead uses the original label proportions. The paper attributes gains under FedIR to distribution matching without explaining this discrepancy. Please clarify which objective produced the reported results and how missing classes are handled.

Reply Thank you for catching this. Under FedIR, selection optimizes Eq. (1) with the reweighted distributions. Algorithm 2 was written for λ=1\lambda = 1. Nothing else in the protocol changes.

Why Eq. (1) is not zero. If every client held every class, then D=0D = 0, as the reviewer notes. However, In our experiments, clients hold on average 5.89 of 1,203 classes (iNaturalist-Users-120k) and 53.70 of 79 classes (Shakespeare). Eq. (1) then becomes D(Sˉ,λ)=−∑kptest,klog⁡(1M∑nSˉn1[k∈Kn]Zn)⏟coverage of class k.D(\bar S, \lambda) = -\sum_{k} p_{test,k} \log \underbrace{\Big( \frac{1}{M} \sum_{n} \bar S_n \frac{\mathbb 1[k \in \mathcal K_n]}{Z_n} \Big)}_{\text{coverage of class } k}.

where Kn\mathcal K_n is the support of client nn's label distribution and Zn=∑j∈Knptest,jZ_n = \sum_{j \in \mathcal K_n} p_{test,j}.

This objective is zero only if every test class receives its full target mass from the selected clients. It heavily penalizes classes that are frequent at in test set but held by few selected clients. FedIR corrects the label proportions within each client but cannot supply classes missing from the selected clients. The remaining shift D(Sˉ,λ)D(\bar{S}, \lambda) can only be reduced by choosing which clients participate, which is what FedMLS does.

Question 1: Under FedIR, does client selection optimize Eq. (1) using reweighted label distributions, or use the original distributions as in Algorithm 2? How are classes absent from a client handled?

Reply: When applying FedIR, FedMLS uses the reweighted label distribution for the selection. We follow FedIR’s mini-batch normalization of the importance weights. A class that is missing from client nn is given zero weight. This has no effect on training since the client has no samples of that class (fn,k=0f_{n, k} = 0).

Question 2: Does Theorem 3’s condition (H>0) hold for the experimental partitions without FedIR? Which solver and stopping criterion were used for Eq. (4) during training? If Algorithm 2 was used, how were zero denominators handled? How does approximate optimization affect Theorem 1’s guarantee?

Reply:

  • We thank the reviewer and agree that this condition is restrictive. Although we set the target (p~test∝ptest+ϵf\tilde p_{test}\propto p_{test}+\epsilon_f) so that CC is finite, min⁡kp~test,k≤1/K\min_k\tilde p_{test,k}\le 1/K implies C≥KC\ge K. Hence H>0H>0 requires Rmax⁡(M)<1/(2β2K)R_{\max}(M)<1/(2\beta^2K), which fails under strong label skew. The condition comes from a single step in Lemma 1, a Cauchy–Schwarz bound weighted by 1/ptest,k1/p_{test,k}, and not from FedMLS itself.

  • In our training experiments, the auxiliary problem (4) is solved in each round with CVXPY using the SCS solver with convergence tolerance ϵtol=10−4\epsilon_{tol} = 10^{-4} and max number of iterations = 2500. Algorithm 2 solves the same problem by projected gradient for the privacy-preserving implementation. We add a small constant inside the logarithm, using Pk(a)+ϵfP_k(a)+\epsilon_f with ϵf=10−9\epsilon_f = 10^{-9}in both CVXPY and Algorithm 2. This keeps the objective finite and convex.

  • In the proof, the solution of (4) enters only through the step stating that our strategy minimizes the right-hand side of the drift-plus-penalty bound. Suppose that in round tt the auxiliary vector actually used is δ\delta-suboptimal, and the selection problem (3) is still solved exactly. The bound then holds with NN replaced by N+δN + \delta, and the rest of the proof is unchanged. Theorem 1 becomes

lim sup⁡T→∞E[D(Sˉ(T),λ)]≤Dλopt+N+δV\limsup_{T \to \infty} \mathbb{E}\left[ D(\bar{S}(T), \lambda) \right] \le D^{opt}_{\lambda} + \frac{N + \delta}{V}

E[Sˉn(T)]M≥c⋅rn−2(N+δ)+2V(Dλopt−Dλmin)T\frac{\mathbb{E}[\bar S_{n}(T)]}{M} \ge c \cdot r_{n} - \sqrt{\frac{2(N + \delta) + 2V(D_{\lambda}^{opt} - D_{\lambda}^{min})}{T}}

This is the standard additive-approximation result for drift-plus-penalty [1]. Approximation adds δ/V\delta/V to the optimality gap and slightly slows convergence of the participation rates.

[1] Neely, Michael. Stochastic network optimization with application to communication and queueing systems. Morgan & Claypool Publishers, 2010.

Question 3: Can the Service estimate individual clients’ label proportions from its aggregates, even when exact recovery is impossible? What can the Selector infer from its repeated client-specific scores?

Reply:

The Service observes only the aggregates P(r)=1M∑nan(r)pn.P(r)=\frac{1}{M}\sum_n a_n(r)p_n. If two clients’ data were swapped, every aggregate would stay the same. The Service therefore cannot tell which client holds which distribution. Any estimate it forms for client n is equally consistent with client n holding any of the clients’ distributions.

The Selector receives the scores h(r)=VMp⊤u(r)h(r) = \frac{V}{M}\mathbf p^\top u(r) in plaintext over many iterations, and it knows its own a(r)a(r). This is sufficient to reconstruct pnp_n. We therefore revise the protocol so that the Selector never sees h or a in plaintext.

Revised protocol (two-party secret sharing). We split aa, hh, and the queue AA into additive shares x=xSel+xSvcx = x^{\mathrm{Sel}} + x^{\mathrm{Svc}}, held by the Selector and the Service, respectively. Each share is individually masked by random noise, so neither party ever holds these quantities in plaintext. The protocol changes as follows:

  1. Masking. The Service keeps its mask ξ2\xi_2 instead of sending it to the Selector. The decrypted h+ξ2h + \xi_2 becomes the Selector's share, and −ξ2-\xi_2 becomes the Service's share.
  2. Gradient step. Each entity E∈E \in {Sel, Svc} computes aE−μ(AE−hE)a^{E} - \mu(A^{E} - h^{E}) on its own shares, with no communication.
  3. Projection, selection, and queue update. The projection onto [0,1]N[0,1]^N, the top-MM selection, and the queue update use standard two-party secure comparison, which outputs fresh shares. Only S(t)S(t) is revealed, and only to the Selector.
  4. Initialization and stopping. Each party draws its share of a(0)a(0) at random, and the number of inner iterations is fixed so that the stopping time reveals nothing.

Since selection is model-independent, this computation can run ahead of training. It adds O(N)O(N) secure comparisons per inner iteration and one secure top-MM selection per round.

Question 4 (FedPALS and ablation). We compare against FedPALS (all other components as in FedAvg), with 2,500 rounds, αtest∈{0.1,1,10}\alpha_{test} \in \{0.1, 1, 10\}, and mean ± s.e. over 4 seeds.

αtest\alpha_{test}CIFAR-100 FedPALSCIFAR-100 OursiNaturalist FedPALSiNaturalist Ours
1023.77 ± 0.1524.82 ± 0.2536.41 ± 0.2238.53 ± 0.14
126.87 ± 0.4927.57 ± 0.4436.02 ± 0.0837.89 ± 0.07
0.122.71 ± 0.3436.48 ± 0.4035.31 ± 0.2438.94 ± 0.16

FedMLS outperforms FedPALS in all settings, most under severe shift (αtest=0.1\alpha_{test} = 0.1), where aggregation reweighting cannot recover classes missing from participating clients.

We also repeat the ablation of Section G.3 on Shakespeare (αtest=0.1\alpha_{test} = 0.1, M=10M = 10).

Dist. MatchingMin-Rate Constraintw/o FedIRw/ FedIR
✓✓37.33 ± 0.4164.36 ± 0.74
×✓34.33 ± 0.5260.75 ± 1.17
✓×14.49 ± 0.5428.26 ± 0.74
××29.04 ± 0.4245.55 ± 0.95
FedAvg35.77 ± 0.5362.14 ± 0.49

The results consistent with CIFAR-100, distribution matching adds 3.00–3.61 points over the minimum-rate constraint alone, and FedMLS + FedIR performs best. Without the minimum-rate constraint, selection concentrates on few clients and accuracy collapses.

Question 5 (Wall-clock time). We measure the wall-clock speedup of FedMLS in reaching FedAvg's final test accuracy on CIFAR-100, assuming identical local training times and no communication cost. N/A means the method never reaches the target.

Methodαtest=10\alpha_{test} = 10αtest=1\alpha_{test} = 1αtest=0.1\alpha_{test} = 0.1
FedAvg2.13×1.04×6.86×
Power-of-Choice3.13×1.57×7.46×
FedCBS1.48×2.08×9.90×
On-Demand FLN/AN/A1.37×

FedMLS reaches the target faster than every baseline in all settings, with the largest gains under severe shift.

Question 6 (Validation reweighting). No. During tuning, each distribution-aware method (FedMLS, FedIR, On-Demand FL) targets pvalp_{val} and is evaluated on validation data drawn from pvalp_{val} and final runs use ptestp_{test}.

Comments on the paper

1 comment

We thank all reviewers for their constructive feedback. Below we summarize the main points addressed in our responses; all clarifications and new results will be incorporated into the revision.

1. Objective under FedIR (zmqL, kNeZ). We clarify that selection under FedIR uses the reweighted label distributions, with missing classes assigned zero weight. We explain why Eq. (1) remains nonzero in practice

2. Privacy protocol (zmqL, kNeZ, jb1f). We acknowledge that the Selector could reconstruct client label distributions from plaintext scores, and we revise the protocol using two-party additive secret sharing so that neither party sees these quantities in plaintext. We also discuss the practicality of the semi-honest, non-colluding model.

3. Theoretical guarantees (kNeZ). We clarify that the condition H>0H > 0 is restrictive and stems from a single bounding step rather than from FedMLS itself, report solver and stopping details, and extend Theorem 1 to approximate solutions of the auxiliary problem.

4. Design choices (zmqL). We explain why the drift-plus-penalty queue is preferred over static-probability sampling. It adapts to random client availability without requiring knowledge of its distribution, while retaining a provable bound.

5. New experiments.

  • Comparison with FedPALS on CIFAR-100 and iNaturalist under matched rounds and clients per round (kNeZ).
  • Ablation study on Shakespeare dataset (kNeZ).
  • Robustness when up to 30% of clients withhold their label distribution (jb1f).
  • Robustness to misspecification of the target label distribution (jb1f).
  • Wall-clock time to reach a target accuracy (kNeZ).

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.