acceptodds
Under review as a conference paper at ICLR 2027

Making Distance-Based Robust Aggregation Fast: A Server-Side Embedding Wrapper

Abstract

Distance-based robust aggregators such as Krum, Bulyan, Geometric Median, and MCA defend Federated Learning against Byzantine clients, but they are slow on the server: Krum costs , and related pairwise geometry is likewise super-linear in the model dimension . Existing JL and sketch protocols mainly reduce communication or cryptographic overhead; they do not accelerate the standard centralized interface in which clients still upload full-dimensional gradients. We propose Projected Dimensionality Reduction (PDR), a plug-and-play server-side wrapper: after full-dimensional uploads, the server applies a sparse embedding, computes reliability weights in , and reconstructs the update in , reducing aggregation to . For this wrapper we prove that the usual robust-FL rates (non-convex) and (strongly convex) are retained, with the Byzantine error floor inflated only by . Experiments show large reductions in server wall-clock time while tracking the accuracy of the wrapped aggregators. To our knowledge, PDR is the first server-side sparse-embedding wrapper for existing distance-based RAggs under full-dimensional uploads, together with a convergence analysis of that wrapper.

Primary area:
optimization
Keywords:
federated learning, Byzantine robustness

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_PACfOpenReview ↗
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
  1. 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.
  2. The paper provides convergence analyses for both non-convex and strongly convex objectives and studies the additional aggregation error introduced by sparse subspace embeddings.
  3. 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
  1. 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.
  2. 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.
  3. 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.
  4. 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.
  5. Some complexity claims should be stated more precisely. The reported costs O(M2p)O(M^2p) for Krum and O(IMp)O(IMp) for Geometric Median are linear, rather than super-linear, in the model dimension pp. PDR reduces the dimensionality of the expensive aggregation stage but retains the cost of reading, projecting, and reconstructing full-dimensional gradients.
Questions for authors
  1. 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?
  2. 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?
  3. 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?
  4. 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?
  5. The stated complexities O(M2p)O(M^2p) and O(IMp)O(IMp) are linear in pp. Is there any component of the baseline aggregation whose complexity is super-linear in pp? If not, could the related claims be revised to more precisely describe the computational advantage of PDR?
4 comments

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ν2cb\nu^{2} does not fit Krum, so Definition 2.1 is now the λ\lambda-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 bb by dataset size, and Definition 2.1 weights honest clients by SiS_{i}. Equal sizes are the special case b=B/Mb=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=50M=50 clients with equal local dataset sizes. Dirichlet heterogeneity sets the labels only. The Byzantine fraction is therefore b=B/Mb=B/M, and the values b∈(0.1,0.3)b\in(0.1,0.3). This is the case in which the count-based conditions of Krum and Multi-Krum coincide with the data-weighted bb.

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 PP and applying it to the uploads, computing the weights in Rk\mathbb{R}^k, and aggregating those weights on the original uploads to obtain gt=∑mα~mtgmtg^{t}=\sum_{m}\tilde{\alpha}_{m}^{t} g_{m}^{t}. 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 PP and applying PP 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−ϵ\frac{1+\epsilon}{1-\epsilon}, 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\beta=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)(k,s)=(8192,8) is a practical choice. The experiments do not claim that this default meets a prescribed ϵ\epsilon. Lemma 2.3 on page 4 and Theorem 3.8 on page 7 give sufficient conditions: a smaller ϵ\epsilon requires k=O~(M/ϵ2)k=\tilde{\mathcal{O}}(M/\epsilon^2) and s=O~(1/ϵ)s=\tilde{\mathcal{O}}(1/\epsilon), and the dense size is k≥18ϵ2(M+2ln⁡(2T/δ))k\ge\frac{18}{\epsilon^2}\bigl(M+2\ln(2T/\delta)\bigr). 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 MM, not on pp. The model dimension pp appears only in the projection cost O(Mps)\mathcal{O}(Mps). One training run does not yield a clean ϵ\epsilon, because the ϵ\epsilon in the theory is the worst-case distortion of the subspace embedding. Lemma 3.6 on page 6 puts that ϵ\epsilon into the aggregation-error floor through 1+ϵ1−ϵ\frac{1+\epsilon}{1-\epsilon}. 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)\mathcal{O}(M^2p) and O(IMp)\mathcal{O}(IMp) are linear in pp, and no term is super-linear in pp. We corrected this wording in the abstract, the introduction, and Section 3. The complexity results are unchanged: Krum goes from O(M2p)\mathcal{O}(M^2p) to O(Mps+M2k)\mathcal{O}(Mps+M^2k), and Geometric Median from O(IMp)\mathcal{O}(IMp) to O(Mps+IMk)\mathcal{O}(Mps+IMk), so M2M^2 or I⋅MI\cdot M multiplies the sketch size kk rather than pp. That saving grows with the number of clients. The remaining full-dimensional work is the sparse projection and the reconstruction, O(Mps+Mp)\mathcal{O}(Mps+Mp).

We thank the reviewer for the careful reading and the comments.

The multi-seed mean and standard deviation on CIFAR-100 at β=0.6\beta=0.6 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 bb 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 bb 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 SiS_{i}. Equal sizes are a special case already covered by the theory, and they make the comparison fair across aggregators. In that setting b=B/Mb=B/M, 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 ϵ\epsilon 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 (k,s)=(8192,8)(k,s)=(8192,8) is a practical choice, not a claim that a prescribed ϵ\epsilon is met.

In the experiment prepared for Reviewer BXsQ, we froze the uploads from one TinyImageNet round (β=0.6\beta=0.6, round 50) and redrew PP 200 times. The table below reports the median and the 99th percentile of the aggregation error ∥g−gˉH∥2/∥gi−gˉH∥2\|g-\bar g_{\mathcal{H}}\|^2\big/\|g_{i}-\bar g_{\mathcal{H}}\|^2.

(k,s)(k,s)KrumMulti-KrumGMMCA
(8192,8)(8192,8)0.612/0.6120.612/0.6122×10−152\times 10^{-15}9.6×10−5/1.0×10−49.6\times 10^{-5}/1.0\times 10^{-4}3.6×10−6/3.9×10−63.6\times 10^{-6}/3.9\times 10^{-6}
(2048,8)(2048,8)0.612/0.6120.612/0.6122×10−152\times 10^{-15}1.0×10−4/1.2×10−41.0\times 10^{-4}/1.2\times 10^{-4}3.7×10−6/4.6×10−63.7\times 10^{-6}/4.6\times 10^{-6}
(1024,8)(1024,8)0.612/0.6120.612/0.6122×10−152\times 10^{-15}1.0×10−4/1.3×10−41.0\times 10^{-4}/1.3\times 10^{-4}4.0×10−6/5.2×10−64.0\times 10^{-6}/5.2\times 10^{-6}

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 kk decreases. The effect on accuracy is reported in Table 5 on page 23, and in the (k,s)(k,s) ablations in Tables 2 and 4.

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

The paper proposes a dimensional reduction scheme, named PDR, to reduce the runtime complexity of distance-based robust aggregation rules like Krum and Geometric Median, used for robust federated learning.

Critical strengths
  1. The problem of making robust aggregation computationally efficient is important and timely.
  2. The proposed scheme is relatively novel and adds practical value to the field of robust federated learning.
  3. The empirical study shows clear benefits in terms of compute time.
Critical weaknesses
  1. Writing quality. In the abstract, several non-standard notations are used without definition, making the logic difficult to follow. For example, what is JL, ss, and ϵ\epsilon? While some of these become clear in the introduction, it would improve readability to define these terms when they are being used for the first time. Similarly, the summary of contributions is hard to follow because it relies on technical terms that only become clear once the reader reaches the subsequent sections.
  2. Hidden assumption? The aggregation rule is assumed to be representable as a linear combination of the input vectors (lines 130-132 and lines 715-717). This assumption is not stated prominently, and the paper does not discuss how the corresponding weights are recovered.
  3. The claim about robustness in Rk\mathbb{R}^k when operating over projected input vectors is not obvious and should be proved formally.
  4. Loose bound. The linear dependence on σ2\sigma^2 is sub-optimal; prior work [a,b,c] addresses this problem through the use of momentum. Moreover, distance-based aggregators such as Krum and Geometric Median can be enhanced with pre-aggregation schemes like nearest neighbor mixing [a] and bucketing [d]. Empirical comparisons against these enhancements would strengthen the results.
  5. Trade-off not satisfactorily discussed. There appears to be a tension between how small kk can be (consequently, how efficiently can we aggregate) and how small can be the training error, both tied to ϵ\epsilon. However, there is no ablation study to show this trade-off.

References:

[a] Allouah, Youssef, et al. “Fixing by mixing: A recipe for optimal byzantine ML under heterogeneity.” International Conference on Artificial Intelligence and Statistics. PMLR, 2023.

[b] Farhadkhani, Sadegh, et al. “Byzantine machine learning made easy by resilient averaging of momentums.” International Conference on Machine Learning. PMLR, 2022.

[c] Karimireddy, Sai Praneeth, Lie He, and Martin Jaggi. “Learning from history for byzantine robust optimization.” International Conference on Machine Learning. PMLR, 2021.

[d] Karimireddy, Sai Praneeth, Lie He, and Martin Jaggi. “Byzantine-robust learning on heterogeneous datasets via bucketing.” arXiv preprint arXiv:2006.09365 (2020).

Questions for authors

Mainly:

  1. How would you respond to the above weaknesses?
  2. How are the linear-combination weights of the aggregation rule recovered in practice?
  3. For what value of cc is the robustness definition satisfied in the projected space?
  4. How does PDR compare, empirically and in terms of the bound, with momentum-based methods [a,b,c] and with pre-aggregation schemes such as nearest neighbor mixing [a] and bucketing [d]?

Minor:

  1. What does OSNAP stand for?
5 comments

1. Weakness 1 and Minor Question 1

With regard to Weakness 1 and Minor Question 1, the abstract now defines the symbols at first use. JL is the Johnson-Lindenstrauss lemma, and a JL sketch is a random map that approximately preserves distances among a fixed set of vectors. ss is the column sparsity, TT is the number of rounds, and ϵ\epsilon is the embedding distortion. The introduction repeats these definitions at first use. OSNAP is written out in Section 2.2 as an oblivious sparse norm-approximating projection.

2. Weakness 2 and Question 2

With regard to Weakness 2 and Question 2, Equation (5) on page 3, which was Equation (8) in the submission, writes the update as a weighted combination of the original uploads. Remark 2.4 on page 4 limits PDR to vector-level distance-based aggregators, not coordinate-wise median or trimmed mean. The weights come from running RAgg in Rk\mathbb{R}^k and are listed in Appendix A on page 14. Krum puts weight one on the selected client. The submitted Bulyan runs keep only its first stage and then a weighted mean, so we call them Multi-Krum, with weight 1/∣S∣1/|S|. Geometric Median uses the normalized Weiszfeld weights, and MCA uses its normalized reliability weights.

3. Weakness 3 and Question 3

With regard to Weakness 3, robustness is about Euclidean distances and does not depend on the ambient dimension, so the same statement applies in Rk\mathbb{R}^k to the weighted mean of the projected honest vectors. The weights are scalars on the original uploads, gt=∑mα~mtgmtg^{t}=\sum_{m}\tilde{\alpha}_{m}^{t} g_{m}^{t}. Appendix D records that PtgtP^{t}g^{t} is the rule's output in Rk\mathbb{R}^k and PtgˉtP^{t}\bar{g}^{t} is the weighted mean of the projected honest vectors. Lemma 3.6 on page 6 then multiplies the aggregation-error bound by 1+ϵ1−ϵ\frac{1+\epsilon}{1-\epsilon}.

With regard to Question 3, in the submission c>0c>0 is the constant in E∥g^−gˉ∥2≤cbν2\mathbb{E}\|\hat{g}-\bar{g}\|^2 \le c b \nu^{2}, where ν2\nu^{2} is the largest pairwise second moment of the honest vectors and cc does not depend on ν2\nu^{2}. Following the other reviewers, Definition 2.1 on page 3 is now λ\lambda-robust and no longer contains cc. The projected-space guarantee is this bound, which depends on Euclidean distances rather than on a value of cc. ϵ\epsilon appears only as the embedding distortion in Lemma 3.6.

4. Weakness 4 and Question 4

With regard to Weakness 4 and Question 4, the introduction now cites these papers and contrasts them with PDR. Karimireddy, He, and Jaggi [a] use history, and Farhadkhani et al. [b] average momentums. Both reduce the term linear in the stochastic variance. Allouah et al. [c] use nearest-neighbor mixing, and Karimireddy, He, and Jaggi [d] use bucketing. Both are pre-aggregation steps under heterogeneity. Their purpose is a smaller error. PDR accelerates server aggregation, which adds the factor 1+ϵ1−ϵ\frac{1+\epsilon}{1-\epsilon} on the aggregation-error floor (Lemma 3.6, page 6). Comparisons hold the base rule fixed. If one of these methods is itself a vector-level distance-based aggregator, the wrapper still applies and moves that computation from pp to the sketch size kk.

5. Weakness 5

With regard to Weakness 5, the trade-off is between ϵ\epsilon and the sketch size kk together with the column sparsity ss. Lemma 2.3 on page 4 states k=O~(M/ϵ2)k=\tilde{\mathcal{O}}(M/\epsilon^2) and s=O~(1/ϵ)s=\tilde{\mathcal{O}}(1/\epsilon): a smaller ϵ\epsilon requires a larger kk and a larger ss. Lemma 3.6 on page 6 puts that ϵ\epsilon into the aggregation-error floor through 1+ϵ1−ϵ\frac{1+\epsilon}{1-\epsilon}.

ϵ\epsilon is not directly observed, so the ablation reads it through accuracy. Table 2 on page 10 and Table 4 on page 22 sweep k∈(2048,4096,8192)k\in(2048,4096,8192) and s∈(1,2,4,8)s\in(1,2,4,8). Accuracy stays in the same range as kk decreases, while the wall-clock time is driven mainly by ss.

[a] Karimireddy, Sai Praneeth, Lie He, and Martin Jaggi. "Learning from history for Byzantine robust optimization.'' International Conference on Machine Learning. PMLR, 2021.

[b] Farhadkhani, Sadegh, et al. "Byzantine machine learning made easy by resilient averaging of momentums.'' International Conference on Machine Learning. PMLR, 2022.

[c] Allouah, Youssef, et al. "Fixing by mixing: A recipe for optimal Byzantine ML under heterogeneity.'' International Conference on Artificial Intelligence and Statistics. PMLR, 2023.

[d] Karimireddy, Sai Praneeth, Lie He, and Martin Jaggi. "Byzantine-robust learning on heterogeneous datasets via bucketing.'' International Conference on Learning Representations, 2022.

Thank you for responding to my concerns, and addressing some of the weaknesses. However, my following concerns still remain:

Assumption on linearity. Can we obtain weights (or write an aggregation as a weighted combination of original inputs) for any distance-based aggregation? While the paper explains how that is the case of Krum, Multi-Krum, Geometric median and MCA, it is not clear whether this property applies to every distance-based aggregation. If this property is not something general, the paper should does this limitation upfront.

Looseness of the bound. The rebuttal/revision does not address the loose dependence of the non-vanishing (asymptotic) error on σ\sigma. If you look at prior work [a, b, c] carefully, their non-vanishing error does not depend of σ\sigma, unlike the current paper. Can the authors explain this apparent looseness in the error bound?

Besides the above two concerns, I also feel that the technical content of the paper has changed substantially in the revision, which would require the revised paper to be treated like a new submission. Given the limited time of this discussion period, it is not possible for reviewers to properly review the revised paper.

Thanks for the comments.

1. Assumption on linearity.

PDR is proved for current mainstream vector-level distance-based aggregators whose output satisfies Equation (5), such as Krum, Geometric Median, Multi-Krum, and MCA. Remark 2.4 on page 4 now already states this scope and excludes rules that cannot be written in this form, including coordinate-wise rules such as the median or trimmed mean. Appendix A on page 14 shows how the reliability weights are recovered for the four methods above.

2. Looseness of the bound. PDR claims server-side acceleration, not a tighter error bound. The only added factor is 1+ϵ1−ϵ\frac{1+\epsilon}{1-\epsilon} in Lemma 3.6, which multiplies the λ\lambda-robust floor of the robust aggregator itself. The σ\sigma dependence in the non-vanishing term is inherited from that aggregator, not introduced by PDR.

The papers [a, b, c] reduce the error bound by changing what is aggregated. [a] and [b] use history or momentum, and [c] combines nearest-neighbor mixing with momentum. That is a different goal from acceleration. To keep PDR general, we analyze and experiment on the base vector-level aggregators, rather than on a specialized pipeline.

3. On the scope of the revision.

The revised paper addresses the reviewers' comments. We clarified the robustness definition, the scope in Remark 2.4, the complexity wording, and the experimental presentation. The method itself is unchanged. PDR remains a server-side embedding wrapper for current mainstream vector-level distance-based aggregators whose output satisfies Equation (5), with the same reconstruction in Equation (5). We did not introduce a new algorithm or a new experimental setting. We hope this clarification makes the revision easier to assess within the discussion period.

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

The paper proposes PDR, a server-side wrapper for accelerating distance-based robust aggregation in federated learning.
It computes aggregation weights using sparse low-dimensional projections and applies them to the original gradients, leaving client uploads unchanged. The authors claim convergence guarantees with controlled inflation of the robustness error, although their applicability to the evaluated aggregators requires justification. Experiments on TinyImageNet and CIFAR-100 report substantial server speedups, but accuracy preservation is uneven and the timing description is incomplete. I see value in the simple server-side design and its compatibility with existing client protocols. However, the unresolved theoretical coverage, the unsupported conditioning step, and the gaps in empirical validation leave me unconvinced that the paper sufficiently establishes its main claims.

Critical strengths

One technical choice I appreciated is preserving the entire span of the uploaded gradients. This accommodates aggregation weights that depend on the projection itself, an important dependency that pairwise distance preservation alone does not directly address. I find this geometric argument well motivated, although the subsequent conditioning step still needs justification.

Critical weaknesses
  1. I found the presentation unnecessarily difficult to follow. I consider readability essential especially in the world of LLM. The abstract uses M,p,s,k,TM,p,s,k,T without explaining their meanings. Terms such as JL, Count Sketch, and OSNAP also receive little intuitive explanation. This creates a difficult barrier for the reader. Instead I see technical details in section 2 in form of lemmas. I would move the detailed versions of Lemmas 2.2 and 2.3 to the appendix. Section 2.2 could retain the essential geometric guarantee. The remaining space could explain the algorithm and its assumptions. A worked example could show the steps from projection to weight computation and reconstruction.

  2. I scrutinized the proof and am not convinced by the conditioning argument in Appendix B. The projection is sampled independently of the uploaded gradients. However, embedding success depends on both the projection and those gradients. A uniformly high success probability does not establish that conditioning preserves the mini-batch distribution. The subsequent convergence proofs still use unbiasedness and independence of the gradient noise. I think this step needs justification. It underpins the expectation bounds in Lemma 3.6 and Theorems 3.8 and 3.10.

  3. In my reading, the connection between the advertised aggregators and the theoretical assumptions remains incomplete. Definition 2.1 requires exact recovery of the honest mean when b=0b=0. As far as I know, ordinary Krum and geometric median need not return that mean. Yet Remarks 2.4 and 3.7 suggest that the guarantees cover these methods. Bulyan also needs separate treatment. Its coordinate-wise selection does not directly supply the shared scalar weights required by Equation (24). These concerns do not disprove a theorem conditional on the stated assumptions. They do leave me uncertain and I think there is a mismatch between evaluated implementations and what the theory actually covers.

Questions for authors

1.This is related to my weakness point 3. Could the authors explain how Definition 2.1 applies to the following no-attack example? Consider five equally weighted honest gradients (0,0,0,0,5). Their mean is 1, but as far as I know, ordinary Krum and geometric median return 0 How is this reconciled with the zero error bound when b=0b=0? Do the evaluated implementations include an additional step that makes the definition applicable?

  1. To address my conditioning concern, could the authors provide a one-round calculation with the past held fixed? Please separate the mini-batch randomness from the projection randomness. Does the honest-gradient noise remain mean zero after conditioning on embedding success? If not, what revision to the convergence guarantee is needed?

  2. Could the authors freeze the client uploads from a few training rounds and draw many fresh projections? I would like to see how the resulting aggregation error varies across these draws. The honest-client mean could serve as the reference in this experiment. Does more aggressive compression occasionally produce a large error? Reporting upper quantiles would help me assess a source of variability that the accuracy tables do not reveal.

5 comments

1. Weakness 1

With regard to Weakness 1, these changes are in the main paper. Symbols in the abstract are defined there, and the same symbols are defined again at their first use in the body. The detailed embedding statements are Lemmas C.1 and C.2. Lemmas 2.2 and 2.3 on page 4 keep the essential geometric guarantee, the (1±ϵ)(1\pm\epsilon) distortion. The saved space is used for the round-tt workflow in Section 2.2 and for Figure 1, which shows one round from projection to weight computation and reconstruction. Assumptions are retained in Section 3, as they serve the theoretical analysis there, not the methodology in Section 2.

2. Weakness 2 and Question 2

With regard to Weakness 2 and Question 2, the expectation in the proof is over the honest mini-batch noise, given the model wtw^t. It is not a conditional expectation given embedding success. The noise does not involve PP. Figure 1 shows the order in one round: the clients upload first, and only then does the server draw PP. Embedding success is decided by that later draw. The error inequality is used when the embedding succeeds, and, for the whole run, when it succeeds in every round. Unbiasedness is used only for the mini-batch expectation given wtw^t. These two pieces are joined by the existing union bound of probability δ/T\delta/T per round, so the displayed convergence bounds are unchanged. The same steps are written out in Appendix D. This is where the conditioning argument from Appendix B of the submission now appears. Section 2.2 states that this randomness is the server's draw of PP after the uploads, not a reweighting of those uploads.

3. Weakness 3 and Question 1

With regard to Weakness 3 and Question 1, the definition in the submission does not cover Krum. It requires the aggregate to equal the honest mean when b=0b=0. On (0,0,0,0,5)(0,0,0,0,5) the mean is 11 and Krum returns 00. We replaced Definition 2.1 on page 3, which followed the cbν2cb\nu^{2} bound of Karimireddy et al. and Gorbunov et al., by the λ\lambda-robust aggregator of Allouah et al. [a, b], which is better suited to the b=0b=0 case.

Write πi=Si/∑j∈GtrueSj\pi_i = S_i / \sum_{j \in \mathcal{G}_{\mathrm{true}}} S_j and gˉ=∑i∈Gtrueπigi\bar{g} = \sum_{i \in \mathcal{G}_{\mathrm{true}}} \pi_i g_i, where Gtrue\mathcal{G}_{\mathrm{true}} is the honest subset. Allouah et al. [b] use the uniform average of the honest vectors. We use this SiS_i-weighted mean, and the two agree when the honest dataset sizes are equal. E∥g^−gˉ∥2≤λ∑i∈Gtrueπi E∥gi−gˉ∥2.\mathbb{E} \left\lVert \hat{g} - \bar{g} \right\rVert^2 \leq \lambda \sum_{i \in \mathcal{G}_{\text{true}}} \pi_i \ \mathbb{E} \left\lVert g_i - \bar{g} \right\rVert^2. At bb=0, the example has honest mean 1, variance 4, and squared error 1 for Krum and geometric median. The revised condition requires 1≤4$\lambda$. For the Krum variant in [a, Proposition 3], λ\lambda=6 at bb=0, giving 1≤24.

The submitted definition bounded the aggregation error by cbν2cb\nu^{2}, which is zero at b=0b=0. Lemma 3.6 on page 6 and Theorems 3.8 and 3.10 on page 7 no longer use that bound. They use only the λ\lambda-robust definition above. A (1±ϵ)(1\pm\epsilon) subspace embedding still multiplies that bound by 1+ϵ1−ϵ\frac{1+\epsilon}{1-\epsilon}.

The runs labeled Bulyan use the first stage of Bulyan: a Krum score keeps mm clients. The second stage is a weighted mean of those whole vectors, with weight 1/m1/m on each, now Equation (5). Standard Bulyan replaces that mean by a coordinate-wise selection, so the submitted name was misleading. We now call the method Multi-Krum.

4. Question 3

With regard to Question 3, we froze the uploads from one TinyImageNet round (β=0.6\beta=0.6, round 50) and redrew PP 200 times. Each entry is the median and the 99th percentile of ∥g−gˉH∥2/∥gi−gˉH∥2\|g-\bar g_{\mathcal{H}}\|^2\big/\|g_i-\bar g_{\mathcal{H}}\|^2.

(k,s)(k,s)KrumMulti-KrumGMMCA
(8192,8)(8192,8)0.612/0.6120.612/0.6122×10−152\times 10^{-15}9.6×10−5/1.0×10−49.6\times 10^{-5}/1.0\times 10^{-4}3.6×10−6/3.9×10−63.6\times 10^{-6}/3.9\times 10^{-6}
(2048,8)(2048,8)0.612/0.6120.612/0.6122×10−152\times 10^{-15}1.0×10−4/1.2×10−41.0\times 10^{-4}/1.2\times 10^{-4}3.7×10−6/4.6×10−63.7\times 10^{-6}/4.6\times 10^{-6}
(1024,8)(1024,8)0.612/0.6120.612/0.6122×10−152\times 10^{-15}1.0×10−4/1.3×10−41.0\times 10^{-4}/1.3\times 10^{-4}4.0×10−6/5.2×10−64.0\times 10^{-6}/5.2\times 10^{-6}

Multi-Krum stays at numerical zero, and Krum stays at 0.6120.612 because it returns one gradient. GM and MCA rise only in the tail. The 99th percentile stays next to the median, so a smaller sketch does not occasionally produce a large aggregation error.

[a] Allouah, Youssef, et al. ”Fixing by mixing: A recipe for optimal Byzantine ML under heterogeneity.'' International Conference on Artificial Intelligence and Statistics. PMLR, 2023.

[b] Allouah, Youssef, et al. “Robust Distributed Learning: Tight Error Bounds and Breakdown Point under Data Heterogeneity.'' Advances in Neural Information Processing Systems, 2023.

Thank you for the revisions. I appreciate the clearer presentation (W1), the revised robustness definition (W3/Q1), and the correction from Bulyan to Multi-Krum (W3).

Regarding W2/Q2, my main concern remains the expectation argument in Appendix D. Equation (24) holds only on embedding success, whereas equations (26)–(27) use unrestricted mini-batch expectations. Sampling the projection after the uploads and applying a union bound do not by themselves justify this transition, since success depends on both the uploads and the projection. I would appreciate a precise justification of this step.

For Q3, the repeated-projection experiment is helpful, but I had requested a few training rounds, whereas the response still examines only one. The attack setting and normalization of the reported error also need clarification. As a follow-up to W3, I remain uncertain whether the revised data-weighted definition covers all evaluated implementations.

Thanks for the comments.

W2/ Q2. As already stated at line 817 of the revised paper, the distortion inequality is used only when the embedding succeeds. All subsequent bounds, including equations (26) and (27) and Theorems 3.8 and 3.10, are therefore stated only on that event. The symbol E\mathbb{E} is the mini-batch expectation given wtw^{t}. For each honest client, it is unbiased for that client's local dataset, not for the full dataset. It does not include PP and is not an expectation over embedding success, so the two are not entangled. A failed embedding in one round is not a skipped mini-batch, and it does not break the unbiasedness of the mini-batch expectation. If any round fails, the iterate may diverge, and the run would need to be restarted.

The number of clients MM is fixed during training. After the uploads are received, a fresh PtP^{t} is drawn independently of the mini-batch. On the embedding-success event, equation (24) holds for every realization. If A≤BA\le B holds for every such realization, then E[A]≤E[B]\mathbb{E}[A]\le\mathbb{E}[B]. Taking the mini-batch expectation therefore preserves the inequality and yields

(1−ϵ)E∥gt−gˉt∥2≤E∥Pt(gt−gˉt)∥2=E∥RAgg(g~1t,…,g~Mt)−Ptgˉt∥2(1-\epsilon)\mathbb{E}\|g^{t}-\bar{g}^{t}\|^{2}\le\mathbb{E}\|P^{t}(g^{t}-\bar{g}^{t})\|^{2}=\mathbb{E}\|RAgg(\tilde{g}_{1}^{t},\ldots,\tilde{g}_{M}^{t})-P^{t}\bar{g}^{t}\|^{2}

Definition 2.1 is already an inequality on expectations. Applying it in Rk\mathbb{R}^{k} gives equation (26). The same argument applies to the factor 1+ϵ1+\epsilon. On the success event, ∥Pt(git−gˉt)∥2≤(1+ϵ)∥git−gˉt∥2\|P^{t}(g_{i}^{t}-\bar{g}^{t})\|^{2}\le(1+\epsilon)\|g_{i}^{t}-\bar{g}^{t}\|^{2} holds for every realization, so the inequality remains valid after taking the expectation, which is equation (27).

By Lemmas 2.2 and 2.3, this PtP^{t} embeds the span of the uploads with probability at least 1−δ/T1-\delta/T. A union bound over TT rounds gives probability at least 1−δ1-\delta that every round succeeds. Theorems 3.8 and 3.10 state the convergence bounds only on this event, with that same probability.

Q3. The experiment freezes the uploads and redraws PP, which isolates the variability due to the projection. Following the request for a few training rounds, we froze three TinyImageNet rounds (β=0.6\beta=0.6, b=0.1b=0.1, Gaussian attack, rounds 25, 50, and 75) and redrew PP 200 times in each case. The reference gˉ\bar g is the mean of the honest uploads. Each table entry is the median and the 99th percentile of ∥g^−gˉ∥2/1∣Gtrue∣∑i∈Gtrue∥gi−gˉ∥2\|\hat g-\bar g\|^2\Big/\frac{1}{|\mathcal{G}_{\rm true}|}\sum_{i\in\mathcal{G}_{\rm true}}\|g_{i}-\bar g\|^2, where g^\hat g is the reconstructed aggregate, Gtrue\mathcal{G}_{\rm true} is the honest subset, and the denominator is the average honest scatter, which is fixed once the uploads are frozen.

T=25T=25

(k,s)(k,s)KrumMulti-KrumGMMCA
(8192,8)(8192,8)0.806/0.8420.806/0.8421.2×10−151.2\times 10^{-15}6.7×10−5/7.5×10−56.7\times 10^{-5}/7.5\times 10^{-5}2.8×10−6/3.1×10−62.8\times 10^{-6}/3.1\times 10^{-6}
(2048,8)(2048,8)0.814/0.8420.814/0.8421.2×10−151.2\times 10^{-15}7.2×10−5/8.4×10−57.2\times 10^{-5}/8.4\times 10^{-5}2.9×10−6/3.5×10−62.9\times 10^{-6}/3.5\times 10^{-6}
(1024,8)(1024,8)0.814/0.8930.814/0.8931.2×10−151.2\times 10^{-15}7.6×10−5/9.6×10−57.6\times 10^{-5}/9.6\times 10^{-5}3.1×10−6/4.1×10−63.1\times 10^{-6}/4.1\times 10^{-6}

T=50T=50

(k,s)(k,s)KrumMulti-KrumGMMCA
(8192,8)(8192,8)0.612/0.6120.612/0.6122×10−152\times 10^{-15}9.6×10−5/1.0×10−49.6\times 10^{-5}/1.0\times 10^{-4}3.6×10−6/3.9×10−63.6\times 10^{-6}/3.9\times 10^{-6}
(2048,8)(2048,8)0.612/0.6120.612/0.6122×10−152\times 10^{-15}1.0×10−4/1.2×10−41.0\times 10^{-4}/1.2\times 10^{-4}3.7×10−6/4.6×10−63.7\times 10^{-6}/4.6\times 10^{-6}
(1024,8)(1024,8)0.612/0.6120.612/0.6122×10−152\times 10^{-15}1.0×10−4/1.3×10−41.0\times 10^{-4}/1.3\times 10^{-4}4.0×10−6/5.2×10−64.0\times 10^{-6}/5.2\times 10^{-6}

T=75T=75

(k,s)(k,s)KrumMulti-KrumGMMCA
(8192,8)(8192,8)0.596/0.5960.596/0.5962.2×10−152.2\times 10^{-15}1.1×10−4/1.2×10−41.1\times 10^{-4}/1.2\times 10^{-4}4.0×10−6/4.3×10−64.0\times 10^{-6}/4.3\times 10^{-6}
(2048,8)(2048,8)0.596/0.5960.596/0.5962.2×10−152.2\times 10^{-15}1.1×10−4/1.3×10−41.1\times 10^{-4}/1.3\times 10^{-4}4.2×10−6/4.9×10−64.2\times 10^{-6}/4.9\times 10^{-6}
(1024,8)(1024,8)0.596/0.5960.596/0.5962.2×10−152.2\times 10^{-15}1.2×10−4/1.4×10−41.2\times 10^{-4}/1.4\times 10^{-4}4.4×10−6/5.5×10−64.4\times 10^{-6}/5.5\times 10^{-6}

Multi-Krum, Geometric Median, and MCA remain small in both the median and the tail at all three rounds. The value for 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 kk decreases.

As a follow-up to Weakness 3, Propositions 3 and 4 of [a] analyze Krum and Geometric Median. The experiments also evaluate Multi-Krum. Geometric Median is computed by the Weiszfeld algorithm, and MCA uses a similar fixed-point iteration with correntropy weights. In all four cases the output can be written as in Equation (5), and Appendix A on page 14 records the recovered weights. Our experiments show that the wrapper remains effective for these four implementations.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.