If the gradient computation has linear complexity (assuming \(\mathcal {O}(1)\)  cost for the gradient computation with respect to one model parameter) and since each worker is assigned to \(l\)  files of \(b/f\)  samples each, the gradient computation cost at the worker level is \(\mathcal {O}((lb/f)d)\)  (\(K\)  such computations in parallel). In our schemes, however, \(b\)  is a constant multiple of \(f\)  and in general \(r < l = \binom{K-1}{r-1}\) ; hence, the complexity becomes \(\mathcal {O}(ld)\)  which is similar to other redundancy-based schemes in [1]}, [2]}, [3]}. The clique-finding problem that follows as part of our detection is NP-complete. However, our experimental evidence suggests that for the kind of graphs we construct this computation takes a infinitesimal fraction of the execution time. The NetworkX package [4]} which we use for enumerating all maximal cliques is based on the algorithm of [5]} and has asymptotic complexity \(\mathcal {O}(3^{K/3})\) . We provide extensive simulations of the clique enumeration time under the Aspis file assignment for \(K = 100\)  and redundancy \(r=5\)  (cf. Tables REF , REF  for weak and optimal attack as introduced in Section , respectively). We emphasize that this value of \(K\)  exceeds by far the typical values of \(K\)  of prior work and the number of servers would suffice for the majority of challenging training tasks. Even in this case, the cost of enumerating all cliques is negligible. For this experiment, we used an EC2 instance of type i3.16xlarge. The complexity of robust aggregation varies significantly depending on the operator. For example, majority voting can be done in time which scales linearly with the number of votes using MJRTY proposed in [6]}. In our case, this is \(\mathcal {O}(Kd)\)  as the PS needs to use the \(d\) -dimensional input from all \(K\)  machines. Krum [7]}, Multi-Krum [8]} and Bulyan [9]} are applied to all \(K\)  workers by default and require \(\mathcal {O}(K^2(d+\mathrm {log}K))\) .
<TABLE>