Byzantine-Robust Stochastic Aggregation for Heterogeneous Datasets

In l_1-norm RSA (Eqs. 5-8) and general l_p-norm RSA (Eqs. 9-11, p >= 1), regular worker i in R updates x_i^{k+1} = x_i^k - alpha^{k+1}(nabla F(x_i^k, xi_i^k) + lambda * sign(x_i^k - x_0^k)) (or dual-norm subgradient in partial_{x_i}||x_i^k - x_0^k||_p), while the master updates x_0^{k+1} = x_0^k - alpha^{k+1}(nabla f_0(x_0^k) + lambda * (sum_{i in R} sign(x_0^k - x_i^k) + sum_{j in B} sign(x_0^k - z_j^k))), bounding every Byzantine worker's influence in dual l_b-norm (1/b + 1/p = 1) by at most lambda regardless of the magnitude of z_j^k.

Theorem 1 proves that in the absence of Byzantine workers (B = empty), the l_p-penalized objective (Eq. 9) achieves exact consensus x_i^* = x_0^* = tilde_x^* whenever lambda >= lambda_0 := max_{i in R} ||nabla E[F(tilde_x^*, xi_i)]||_b, and Theorems 2-3 establish O(1/(k+1)) sublinear convergence to a bounded O(lambda^2 q^2) neighborhood of tilde_x^* under arbitrary heterogeneous worker distributions D_i.

When q > 0 Byzantine workers are present, RSA converges to a non-zero asymptotic error neighborhood Delta_1 = O(lambda^2 q^2) / mu^2 around the true consensus optimum tilde_x^* (Theorems 2-3), creating a trade-off between choosing lambda >= lambda_0 large enough for consensus across heterogeneous workers and keeping lambda small to minimize Byzantine bias.