Supplementary Material

The supplementary material is organized as follows. First, we prove Proposition 1 and Theorem 1. In this section we prove Proposition 1, and some preliminary lemmas. Definition 4. Let the function Algorithm 1 for all i [m] and k 0. Let us define the following terms: g We will make use of the following notation for the history of the method. These samples are assumed to be independent across clients.