  We study stochastic gradient descent (SGD) with local iterations in the
presence of malicious/Byzantine clients, motivated by the federated learning.
The clients, instead of communicating with the central server in every
iteration, maintain their local models, which they update by taking several SGD
iterations based on their own datasets and then communicate the net update with
the server, thereby achieving communication-efficiency. Furthermore, only a
subset of clients communicate with the server, and this subset may be different
at different synchronization times. The Byzantine clients may collaborate and
send arbitrary vectors to the server to disrupt the learning process. To combat
the adversary, we employ an efficient high-dimensional robust mean estimation
algorithm from Steinhardt et al.~\cite[ITCS 2018]{Resilience_SCV18} at the
server to filter-out corrupt vectors; and to analyze the outlier-filtering
procedure, we develop a novel matrix concentration result that may be of
independent interest.
  We provide convergence analyses for strongly-convex and non-convex smooth
objectives in the heterogeneous data setting, where different clients may have
different local datasets, and we do not make any probabilistic assumptions on
data generation. We believe that ours is the first Byzantine-resilient
algorithm and analysis with local iterations. We derive our convergence results
under minimal assumptions of bounded variance for SGD and bounded gradient
dissimilarity (which captures heterogeneity among local datasets). We also
extend our results to the case when clients compute full-batch gradients.
