Appendix B — Conditions for robust aggregation

The assumptions behind Krum, coordinate median, and trimmed mean results, for readers who need to check them before relying on these rules.

A team that combines training updates from many participants may choose Krum, coordinate median, or trimmed mean because each is described as robust to bad updates. That description comes from theorems, and each theorem is valid only under its assumptions. If a deployment breaks a condition, the guarantee no longer applies, even though the rule still runs and still returns a result. Section 24.2 explains the client and coordinator roles, distinguishes parameters, deltas, and gradients, and works a one-dimensional example. The conditions below are a guide to checking whether a result applies, not a replacement for the complete theorem and proof in each paper. A gradient contains the local rate of loss change with respect to each model parameter. In the papers’ gradient algorithms, the server subtracts the combined gradient multiplied by a learning rate. In the branch delta example, it adds the chosen parameter change to the common starting model.

B.1 Krum

Krum picks one submitted update: the one with the smallest sum of squared distances to its \(n-f-2\) nearest neighbors. Blanchard et al.¹ prove a resilience result for it. The result describes one round with \(n\) submitted vectors, of which at most \(f\) may be Byzantine, meaning arbitrary and possibly written by an attacker. The alignment condition concerns the expected chosen vector: it must have a positive component along the true gradient. A separate condition bounds the second, third and fourth moments of the chosen vector in terms of the honest estimator’s moments. A moment is an expectation of a power of its magnitude. This part of the result depends on the corresponding honest moments being finite.

The setting has several parts. The server is reliable, and training proceeds in synchronous rounds. The paper assigns a zero vector to a Byzantine participant that supplies no vector, so that participant cannot block the round indefinitely. The server combines the \(n\) vectors, including any such substitutes. Each honest participant sends an estimate \(G\) of the same true gradient \(g\). These estimates are independent, identically distributed, and unbiased, so on average they equal \(g\). Their spread satisfies \(E\|G-g\|^2 = d\sigma^2\). Here \(d\) is the number of coordinates in each vector, and \(\sigma\) sets how noisy a single honest estimate is per coordinate. The Byzantine vectors may be arbitrary and may collude. Under this setting the result needs

\[2f+2 < n \qquad \text{and} \qquad \eta(n,f)\sqrt{d}\,\sigma < \|g\|\]

The first condition limits how many bad vectors the round can hold. With \(n\) vectors, fewer than about half may be Byzantine. The second condition compares noise with signal. The left side grows with the honest noise \(\sigma\) and the dimension \(d\). The right side, \(\|g\|\), is the size of the true gradient. The condition asks the true gradient to stand out clearly above the honest noise. The factor \(\eta(n,f)\) depends on the participant counts, not the learning rate. Proposition 1 defines it as

\[\eta(n,f)=\sqrt{2\left(n-f+\frac{f(n-f-2)+f^2(n-f-1)}{n-2f-2}\right)}.\]

Example

Checking Krum conditions. Suppose a round has \(n=7\) and permits \(f=2\) Byzantine submissions. The count condition is \(6<7\), and \(\eta=\sqrt{2(5+22)}=\sqrt{54}\). With \(d=100\) and \(\sigma=0.01\), the noise side is about \(0.735\). A true gradient norm of \(1\) satisfies the displayed inequality; a norm of \(0.5\) does not. These assumed values illustrate the check. The true gradient and honest noise are not generally known from untrusted submissions alone.

Resilience alone does not give convergence. Proposition 2 of Blanchard et al.² additionally assumes a nonnegative cost \(Q(x)\) with three continuous derivatives, where \(x\) is the parameter vector. Positive learning rates \(\gamma_t\) obey \(\sum_t\gamma_t=\infty\) and \(\sum_t\gamma_t^2<\infty\). The unbiased estimator has moment bounds \(E\|G(x)\|^r\le A_r+B_r\|x\|^r\) for \(r=2,3,4\) and constants \(A_r,B_r\). A fixed angle \(0\le\theta<\pi/2\) must satisfy \(\eta(n,f)\sqrt d\,\sigma(x)\le\|\nabla Q(x)\|\sin\theta\) at every \(x\). Outside a bounded region, \(\|\nabla Q(x)\|\) stays above a positive constant and its angle to \(x\) is at most a fixed \(\phi<\pi/2-\theta\). These angular bounds keep the expected descent direction aligned with the true gradient and prevent escape to unbounded parameters. Under those conditions, gradient norms converge to zero almost surely. This is a stationary-point result, not a global-minimum or backdoor guarantee. With persistent gradient noise, the paper cautions about reaching a region where the gradient is small relative to that noise.

Federated training often breaks this model. Several local epochs on different participants’ data do not satisfy it by default, because the deltas need not be unbiased, identically distributed estimates of one shared gradient. The count \(f\) concerns the round’s \(n\) submitted vectors, not the whole fleet of participants. The selected vector may still be Byzantine.

B.2 Coordinate median and trimmed mean

Coordinate median takes the median of each coordinate across submitted updates. Coordinate trimmed mean removes the largest and smallest \(\beta\) fraction of values in each coordinate and averages the rest. Yin et al.³ prove error bounds for both.

Their setting differs from Krum’s, and its \(n\) means something else. There are \(m\) workers. Each holds \(n\) independent records drawn from one common distribution, and the datasets stay fixed across iterations. At each step the server sees the empirical gradient that each worker computes at one shared model. That is not the same as multi-epoch updates computed on data that is not independent or not identical across participants. The Byzantine fraction \(\alpha\) is the share of the \(m\) workers that may send arbitrary values.

Median needs smoothness, bounded variance and absolute skewness, and strong convexity for some claims. Smoothness bounds how quickly gradients change. Strong convexity supplies a positive lower bound on curvature. The parameter domain is compact and convex; convex-loss results require a minimizer with zero gradient in that domain. It also needs a finite-sample margin:

\[\alpha + \sqrt{d\log(1+nm\hat L D)/(m(1-\alpha))} + 0.4748 S/\sqrt{n} \le 1/2 - \epsilon\]

The sum on the left must stay below one half by the positive slack \(\epsilon\). Its first term, \(\alpha\), is the Byzantine fraction. The second shrinks as the number of workers \(m\) grows and grows with the dimension \(d\). Inside its logarithm, \(\hat L=(\sum_{k=1}^{d}L_k^2)^{1/2}\) is the root sum of squares of the coordinate smoothness constants \(L_k\). Each \(L_k\) bounds how quickly that loss-gradient coordinate can change with the parameter vector. The diameter \(D\) is the largest distance between two allowed parameter vectors. The third term shrinks as each worker’s record count \(n\) grows. There, \(S\) bounds absolute skewness for each gradient coordinate. For a coordinate with positive variance, this quantity is the third absolute central moment divided by variance to the power \(3/2\). The value 0.4748 is a fixed numerical constant. This margin limits the Byzantine fraction together with the uncertainty from finite samples.

Example

Checking the median margin. Suppose \(m=1{,}000\) workers each have \(n=1{,}000\) records, the gradient has \(d=2\) coordinates, and \(\alpha=0.1\). Assume \(\hat L D=1\), \(S=1\), and \(\epsilon=0.1\). These values illustrate the calculation, not a measured deployment. With the natural logarithm, the three terms on the left are approximately \(0.1\), \(0.1752\), and \(0.0150\). Their sum is \(0.2902\), below the right side \(0.5-0.1=0.4\), so these assumed values satisfy the margin.

If only the worker count changes to \(m=100\), the second term becomes approximately \(0.5058\) and the sum becomes \(0.6208\). That setting fails the margin. Neither calculation establishes smoothness, distribution, moment, or convergence assumptions. Those require separate justification before applying the theorem.

Trimmed mean needs sub-exponential tails, which limit how often honest values fall far from the center. It also needs

\[\alpha \le \beta \le 1/2 - \epsilon\]

plus similar smoothness and parameter-space limits. In words, the fraction \(\beta\) trimmed from each end must be at least the Byzantine fraction \(\alpha\), but this does not identify every bad value. A malicious value inside the retained range can remain. The trimming fraction must also stay below one half by the slack \(\epsilon\), so that some values remain to average.

The loss class determines what the error bound measures. In Yin et al.⁴, Theorems 1 and 4 concern distance to the minimizer for strongly convex loss. Theorems 2 and 5 concern excess loss for convex loss and add Assumption 5 on the size of the parameter domain. Theorems 3 and 6 concern the smallest gradient norm reached for nonconvex loss and use Assumption 6, a different domain-size condition. These are probability bounds over sampled data, with the theorem’s iteration count and step size \(1/L_F\), where \(L_F\) bounds how quickly the population gradient changes. The two displayed fraction tests alone imply none of these training guarantees.

The domain assumptions keep the iterates inside the allowed parameter set \(W\) without a projection step that moves an outside point back into \(W\). Let \(w_0\) be the initial parameters, \(w^*\) a population-loss minimizer, and \(F\) the population loss. Assumption 5 requires \(W\) to contain the Euclidean ball centered at \(w^*\) with radius \(2\|w_0-w^*\|_2\).

Assumption 6 instead assumes \(\|\nabla F(w)\|_2\le M\) throughout \(W\) and requires a ball centered at \(w_0\) of radius

\[\frac{2(M+\Delta)\bigl(F(w_0)-F(w^*)\bigr)}{\Delta^2}.\]

Here \(M\) bounds gradient magnitude and \(\Delta>0\) is the median theorem’s statistical error quantity defined in equation (3) of Yin et al.⁵. It is not a client parameter delta. For trimmed mean, Theorem 6 substitutes its own error quantity \(\Delta'\) from equation (5). The loss gap and error quantity therefore affect the required domain size. Neither assumption follows from a sufficiently small Byzantine fraction. Applying the result still requires the corresponding theorem’s other assumptions, step size, iteration count, and probability bound.

These results do not show that a combined model is free of a backdoor. They are error bounds for the training result under the stated setting, not checks on what an update teaches the model. Krum may select a malicious submitted vector. Coordinate median may use a malicious value for a coordinate, and trimmed mean may leave one among the values it averages. Discarding values can remove useful honest information. The statistical cost depends on the assumptions and chosen trimming fraction; these papers do not show that the rules always reduce learning quality. And a deployment whose updates break the stated setting, such as multi-epoch training on different participants’ data, loses the guarantee while the rule keeps running. These methods remain candidates to test against an expected attack, not proof that a hidden update is benign.

Example

A malicious value survives trimming. For an arithmetic example, suppose one coordinate receives \([0,1,2,2.5,3,4,5,6,7,8]\), with the attacker supplying \(2.5\). Trimming \(\beta=0.1\) removes \(0\) and \(8\). The retained sum is \(30.5\), giving \(30.5/8=3.8125\). Here \(\alpha=\beta=0.1\), yet the malicious value remains. The fraction condition supports an error bound under the other assumptions; it is not a test of which participant is honest.

---

1. Peva Blanchard et al., “Machine Learning with Adversaries: Byzantine Tolerant Gradient Descent,” Advances in Neural Information Processing Systems 30 (2017), Definition 1 and score \(s(i)\) on p. 4 and Proposition 1 on p. 5, section 5 Proposition 2 on p. 6, source. The resilience result needs \(2f+2<n\), independent unbiased estimates, bounded variance, and \(\eta(n,f)\sqrt{d}\sigma<\|g\|\), plus separate convergence conditions. The selected vector may be Byzantine.

2. Peva Blanchard et al., “Machine Learning with Adversaries: Byzantine Tolerant Gradient Descent,” Advances in Neural Information Processing Systems 30 (2017), Definition 1 and score \(s(i)\) on p. 4 and Proposition 1 on p. 5, section 5 Proposition 2 on p. 6, source. The resilience result needs \(2f+2<n\), independent unbiased estimates, bounded variance, and \(\eta(n,f)\sqrt{d}\sigma<\|g\|\), plus separate convergence conditions. The selected vector may be Byzantine.

3. Dong Yin et al., “Byzantine-Robust Distributed Learning: Towards Optimal Statistical Rates,” Proceedings of the 35th International Conference on Machine Learning, PMLR 80 (2018), pp. 5650-5659, Definitions 1 to 2 on PDF p. 3 and Algorithm 1 and Assumptions 1 to 4 on PDF p. 4 and Theorems 1 to 6 on PDF pp. 5 to 6, source. Coordinate median and trimmed mean need distinct moment, smoothness, and fraction assumptions and a common distribution empirical gradient model, not multi epoch non identical updates.

4. Dong Yin et al., “Byzantine-Robust Distributed Learning: Towards Optimal Statistical Rates,” Proceedings of the 35th International Conference on Machine Learning, PMLR 80 (2018), pp. 5650-5659, Definitions 1 to 2 on PDF p. 3 and Algorithm 1 and Assumptions 1 to 4 on PDF p. 4 and Theorems 1 to 6 on PDF pp. 5 to 6, source. Coordinate median and trimmed mean need distinct moment, smoothness, and fraction assumptions and a common distribution empirical gradient model, not multi epoch non identical updates.

5. Dong Yin et al., “Byzantine-Robust Distributed Learning: Towards Optimal Statistical Rates,” Proceedings of the 35th International Conference on Machine Learning, PMLR 80 (2018), pp. 5650-5659, Definitions 1 to 2 on PDF p. 3 and Algorithm 1 and Assumptions 1 to 4 on PDF p. 4 and Theorems 1 to 6 on PDF pp. 5 to 6, source. Coordinate median and trimmed mean need distinct moment, smoothness, and fraction assumptions and a common distribution empirical gradient model, not multi epoch non identical updates.