  Federated learning is a decentralized machine learning framework that enables
collaborative model training without revealing raw data. Due to the diverse
hardware and software limitations, a client may not always be available for the
computation requests from the parameter server. An emerging line of research is
devoted to tackling arbitrary client unavailability. However, existing work
still imposes structural assumptions on the unavailability patterns, impeding
their applicability in challenging scenarios wherein the unavailability
patterns are beyond the control of the parameter server. Moreover, in harsh
environments like battlefields, adversaries can selectively and adaptively
silence specific clients. In this paper, we relax the structural assumptions
and consider adversarial client unavailability. To quantify the degrees of
client unavailability, we use the notion of $\epsilon$-adversary dropout
fraction. We show that simple variants of FedAvg or FedProx, albeit completely
agnostic to $\epsilon$, converge to an estimation error on the order of
$\epsilon (G^2 + \sigma^2)$ for non-convex global objectives and $\epsilon(G^2
+ \sigma^2)/\mu^2$ for $\mu$ strongly convex global objectives, where $G$ is a
heterogeneity parameter and $\sigma^2$ is the noise level. Conversely, we prove
that any algorithm has to suffer an estimation error of at least $\epsilon (G^2
+ \sigma^2)/8$ and $\epsilon(G^2 + \sigma^2)/(8\mu^2)$ for non-convex global
objectives and $\mu$-strongly convex global objectives. Furthermore, the
convergence speeds of the FedAvg or FedProx variants are $O(1/\sqrt{T})$ for
non-convex objectives and $O(1/T)$ for strongly-convex objectives, both of
which are the best possible for any first-order method that only has access to
noisy gradients.
