- Rating
- 2
- Confidence
- 3
- Informativeness
- 3
- Presentation
- 3
- Soundness
- 1
Read review
Paper summary
This paper proposes PDR to speed up robust aggregation in FL. The server projects client gradients into a smaller space, computes aggregation weights there, and combines the original gradients using those weights. The paper provides convergence bounds using subspace embeddings and tests four aggregators on TinyImageNet and CIFAR100 under Byzantine attacks and heterogeneous data. Results show faster aggregation with similar accuracy in many settings.
Critical strengths
- PDR addresses a practically relevant bottleneck by reducing server side computation without changing the client upload protocol. It performs expensive distance comparisons in a lower-dimensional space and reconstructs the update from the original gradients, making it relatively easy to integrate into existing federated learning systems and potentially applicable to several robust aggregators.
- The paper provides convergence analyses for both non-convex and strongly convex objectives and studies the additional aggregation error introduced by sparse subspace embeddings.
- The experimental results show substantial reductions in aggregation time while generally maintaining comparable accuracy. For example, on CIFAR-100 under the Gaussian attack with b=0.1, PDR reduces the aggregation time of Geometric Median from 0.900.900.90 to 0.240.240.24 seconds, while its accuracy remains nearly unchanged at 58.79% and 58.78, respectively.
Critical weaknesses
- The theoretical framework does not clearly cover all evaluated aggregators. Equation (8) assumes one scalar weight per client, whereas standard Bulyan performs coordinate-wise selection and cannot generally be represented by a single set of client weights. Moreover, Definition 2.1 implies exact recovery of the honest mean when b=0, while Krum typically returns one selected gradient rather than the mean.
- The paper defines the Byzantine fraction b using client data sizes, but Krum and Bulyan usually impose robustness conditions on the number of malicious clients. These notions are not equivalent when clients have unequal dataset sizes, and the paper does not explain how the stated guarantees extend to this setting.
- The timing protocol includes projection generation, projection, and low-dimensional aggregation, but it is unclear whether the high-dimensional reconstruction in Equation (8) is included. The results also report only the maximum accuracy over 100 rounds without averages or variation across multiple runs. Some noticeable accuracy drops deserve further discussion; for example, PDR+Bulyan decreases from 50.76% to 45.97% on TinyImageNet under the Gaussian attack with b=0.3.
- The relationship between the theoretical embedding conditions and the experimental choices is insufficiently explained. Although k=8192 and s=8 are used by default and additional values are evaluated, the paper does not quantify their resulting distortion or show whether they satisfy the conditions assumed by the convergence analysis.
- Some complexity claims should be stated more precisely. The reported costs for Krum and for Geometric Median are linear, rather than super-linear, in the model dimension . PDR reduces the dimensionality of the expensive aggregation stage but retains the cost of reading, projecting, and reconstructing full-dimensional gradients.
Questions for authors
- Which version of Bulyan is used in the experiments, and how are the scalar client weights in Equation (8) obtained given its coordinate-wise aggregation? Similarly, how does standard Krum satisfy Definition 2.1 when b=0, since it selects one gradient rather than returning the honest mean?
- Are client dataset sizes equal in the theoretical and experimental settings, or is the number of Byzantine clients separately constrained? If neither condition holds, how do the data-weighted definition of b and the guarantees of Krum and Bulyan align?
- Does the reported wall-clock time include the high-dimensional reconstruction in Equation (8)? Could the authors provide results over multiple random seeds, including the mean and standard deviation, particularly for cases with noticeable accuracy degradation such as PDR+Bulyan in Table 1?
- What empirical distortion is produced by the default setting k=8192 and s=8? Do these parameters satisfy the sparse subspace-embedding conditions assumed in the convergence analysis, and how should they be selected for different values of M and p?
- The stated complexities and are linear in . Is there any component of the baseline aggregation whose complexity is super-linear in ? If not, could the related claims be revised to more precisely describe the computational advantage of PDR?
4 comments
We thank the reviewer for the careful reading and the comments.
The multi-seed mean and standard deviation on CIFAR-100 at are now in Table 6 on page 24.
Thanks for the response. I still have two concerns.
Question 2: The guarantees for unequal dataset sizes are still unclear. Byzantine clients could hold a small share of the data but still exceed the number Krum can tolerate. The experiments with equal dataset sizes do not address this issue.
Question 4: The actual embedding distortion with the default parameters is still not reported. The accuracy and aggregation error results are helpful, but they do not directly measure this distortion.
I will keep my score at 2 for now, mainly because of the concern in Question 2.
We thank the reviewer for the careful reading and the comments.
1. Question 2.
We would like to clarify our wording. The theory uses a data-weighted fraction because Geometric Median and MCA can be applied with unequal client dataset sizes, and PDR wraps these rules, so the analysis must cover that case. Krum and Multi-Krum do not apply in this setting. They are count-based, and if is not the fraction of Byzantine clients their guarantees become difficult to analyze. That limitation belongs to Krum and Multi-Krum themselves, not to PDR.
This is why the experiments use equal . Equal sizes are a special case already covered by the theory, and they make the comparison fair across aggregators. In that setting , so the two count-based rules are used under the condition for which they are defined. A scenario in which many Byzantine clients hold only a small share of the data therefore lies outside the guarantee of Krum and Multi-Krum, and is not a gap in PDR.
2. Question 4.
We would like to clarify this point. The conditions in Lemma 2.3 and Theorem 3.8 are sufficient, not necessary. The in the theory is the worst-case distortion of the subspace embedding, so it cannot be read off from a single training run. The default is a practical choice, not a claim that a prescribed is met.
In the experiment prepared for Reviewer BXsQ, we froze the uploads from one TinyImageNet round (, round 50) and redrew 200 times. The table below reports the median and the 99th percentile of the aggregation error .
| Krum | Multi-Krum | GM | MCA | |
|---|---|---|---|---|
Multi-Krum, Geometric Median, and MCA remain small. The error of Krum is larger because Krum returns a single client gradient, so it reflects data heterogeneity rather than the embedding, and it stays essentially unchanged as decreases. The effect on accuracy is reported in Table 5 on page 23, and in the ablations in Tables 2 and 4.
1. Weakness 1 and Question 1
With regard to Weakness 1 and Question 1, please see the reply to Reviewer BXsQ, Weakness 3 and Question 1. The submitted bound cbν2 does not fit Krum, so Definition 2.1 is now the λ-robust aggregator. The runs labeled Bulyan are Multi-Krum, Equation (8) in the submission is Equation (5), and the weights are listed in Appendix A on page 14.
2. Weakness 2 and Question 2
With regard to Weakness 2 and Question 2, the proofs are written for unequal dataset sizes, without loss of generality. Equation (3) on page 3 sets b by dataset size, and Definition 2.1 weights honest clients by Si. Equal sizes are the special case b=B/M, and that case is already covered by the same proof.
Krum and Multi-Krum count malicious clients, so that count matches the data-weighted fraction only when every client has the same number of examples. The experiments therefore use the equal-size case. Section 4 on page 8 and Appendix B on page 14 already state the split. Each dataset is partitioned across M=50 clients with equal local dataset sizes. Dirichlet heterogeneity sets the labels only. The Byzantine fraction is therefore b=B/M, and the values b∈(0.1,0.3). This is the case in which the count-based conditions of Krum and Multi-Krum coincide with the data-weighted b.
3. Weakness 3 and Question 3
With regard to Weakness 3, the Metrics paragraph in Section 4 on page 8 defines the reported wall-clock time. For PDR it includes building P and applying it to the uploads, computing the weights in Rk, and aggregating those weights on the original uploads to obtain gt=∑mα~mtgmt. That last sum is Equation (8) in the submission and Equation (5) on page 3. Appendix B on page 15 lists the same steps, with building P and applying P written separately. The numbers in Table 1 already contain this sum.
With regard to the accuracy drop, PDR trades accuracy for server time. Lemma 3.6 on page 6 multiplies the aggregation-error floor by 1−ϵ1+ϵ, so a drop relative to the unwrapped rule is consistent with that guarantee. Table 1 records the time saved by this trade.
The multi-seed mean and standard deviation of maximum test accuracy on TinyImageNet at β=0.6 are in Table 5 on page 23. The CIFAR-100 multi-seed results will be added later.
4. Weakness 4 and Question 4
With regard to Weakness 4 and Question 4, Section 4 on page 8 states that (k,s)=(8192,8) is a practical choice. The experiments do not claim that this default meets a prescribed ϵ. Lemma 2.3 on page 4 and Theorem 3.8 on page 7 give sufficient conditions: a smaller ϵ requires k=O~(M/ϵ2) and s=O~(1/ϵ), and the dense size is k≥ϵ218(M+2ln(2T/δ)). Falling below them means the worst-case embedding guarantee no longer holds; it does not mean the model necessarily fails to converge. The sketch size depends on M, not on p. The model dimension p appears only in the projection cost O(Mps). One training run does not yield a clean ϵ, because the ϵ in the theory is the worst-case distortion of the subspace embedding. Lemma 3.6 on page 6 puts that ϵ into the aggregation-error floor through 1−ϵ1+ϵ. The ablation therefore reads the trade-off through accuracy, in Table 2 on page 10 and Table 4 on page 22.
5. Weakness 5 and Question 5
With regard to Weakness 5 and Question 5, we agree. O(M2p) and O(IMp) are linear in p, and no term is super-linear in p. We corrected this wording in the abstract, the introduction, and Section 3. The complexity results are unchanged: Krum goes from O(M2p) to O(Mps+M2k), and Geometric Median from O(IMp) to O(Mps+IMk), so M2 or I⋅M multiplies the sketch size k rather than p. That saving grows with the number of clients. The remaining full-dimensional work is the sparse projection and the reconstruction, O(Mps+Mp).