On the Convergence of Heterogeneous Federated Learning with Arbitrary
  Adaptive Online Model Pruning
  One of the biggest challenges in Federated Learning (FL) is that client
devices often have drastically different computation and communication
resources for local updates. To this end, recent research efforts have focused
on training heterogeneous local models obtained by pruning a shared global
model. Despite empirical success, theoretical guarantees on convergence remain
an open question. In this paper, we present a unifying framework for
heterogeneous FL algorithms with {\em arbitrary} adaptive online model pruning
and provide a general convergence analysis. In particular, we prove that under
certain sufficient conditions and on both IID and non-IID data, these
algorithms converges to a stationary point of standard FL for general smooth
cost functions, with a convergence rate of $O(\frac{1}{\sqrt{Q}})$. Moreover,
we illuminate two key factors impacting convergence: pruning-induced noise and
minimum coverage index, advocating a joint design of local pruning masks for
efficient training.
