Optimal Robustness

We presented, in the previous chapter, a way to render robustness to the classic distributed mini-batch gradient-descent (DMGD) method against (a minority of) adversarial nodes. Basically, we saw that upon replacing the simple averaging operation at the server by an aggregation scheme that satisfies the property of \((f, \kappa )\) -robust averaging, the resulting robust DMGD method can tolerate up to f adversarial nodes. We formalized the notion of robustness against adversarial nodes through the definition of \((f, \varepsilon )\) -resilience (and stationary resilience). Specifically, in the strongly convex case, “robustifying” DMGD with an \((f, \kappa )\) -robust averaging rule is \((f, \varepsilon )\) -resilient, i.e., outputs an \(\varepsilon \) -suboptimal model, where \(\varepsilon \in \mathcal {O}_{\star }\left ( \kappa \sigma ^2 + \kappa \zeta \right )\) upon executing a sufficiently large number of iterations T (We write \(\phi (a) \in \mathcal {O}_{\star }(\psi (a))\) if there exists a constant \(c \in \mathbb {R}^+\) such that \(\phi (a) \leq c \psi (a)\) for all \(a \in \mathbb {R}^+\) . Similarly, \(\phi (a) \in \Omega _{\star }(\psi (a))\) if there exists a constant \(c \in \mathbb {R}^+\) such that \(\phi (a) \geq c \psi (a)\) for all \(a \in \mathbb {R}^+\) . These conventions are extensively used in this chapter.). A similar result was also shown in the non-convex case, but in terms of approximate stationarity. While we presented some simple \((f, \kappa )\) -robust averaging rules, the resulting training error is not optimal for many of those schemes, e.g., Krum, geometric median, and coordinate-wise median. Specifically, their robustness coefficient \(\kappa \) is suboptimal with respect to the tolerable fraction of adversarial nodes \(\frac {f}{n}\) . This looseness significantly weakens the overall resilience of the learning algorithm in practical settings. In this chapter, we show how by using pre-aggregations schemes, specifically nearest-neighbor mixing ( \(\mathrm {NNM}\) ) and bucketing, we can achieve order-optimal robustness. These schemes intervene prior to the aggregate, thereby yielding a two-step aggregation rule.