# Lazy Aggregation for Heterogeneous Federated Learning
## 3 Methods
### FedLA
The former can be reduced by synchronous aggregation, which is the focus of previous works, but this paper has shifted its attention to the latter. For the aggregation, the result of multi-epochs training with a small LR isn't different from an epoch training with a lager LR on the device side, and multiple devices with few samples train sequentially which is equivalent to a device training with a large number of samples. Therefore, we can generalize the conclusion of the inequality (6). The sampling range is extended from batch to device. With sampling, the WD growth caused by distribution difference disappears gradually. Therefore, monitoring WDR is a great way to judge whether sampling is necessary. If WDR is greater than the threshold, the current round of weights won't be aggregated but forwarded to the next round of selected devices. On the contrary, we consider that the sampling is sufficient. Only when their whole distributions are consistent with the global distribution will the WD growth slow down. On this basis, this paper proposes a federated lazy aggregate (FedLA) as shown in Algorithm 1:  
```
Input:\(T\), \(K\), \(E\), \(B\), \(w_{0}\), \(d_{0}\), \(\epsilon\)  Initialize \(w_{0}^{0},n_{0}^{1}\ldots n_{0}^{k-1}\gets 0\); \(w_{0}^{0},w_{0}^{1}\ldots w_{0}^{K-1}\gets w_{0}\) fort = 0, 1, 2, \(\ldots\), \(T-1\)do  Sample devices \(S_{t}\in[N]\), \(|S_{t}|=K\leq N\)  Transmit \(w_{0}^{0}\ w_{1}^{1},\ \ldots\ w_{t}^{K-1}\) to selected \(K\) devices, respectively for each device \(k\in S_{t}\) in parallel do \(n_{k}\), \(w_{t+1}^{k}=ClientUpdate\Big{(}w_{t}^{k}\ E,\ B\Big{)}\)  Transmit device \(n_{k}\), \(w_{t+1}^{k}\) to server endfor fork = 0, 1, 2, \(\ldots\), \(T-1\)do \(n_{t+1}^{k}\gets n_{t}^{k}+n_{k}\) endfor \(d_{t+1}=WD\Big{(}w_{t+1}^{0}\), \(w_{t+1}^{1}\), \(\ldots\), \(w_{t+1}^{K-1}\Big{)}\) if\(\left|\frac{d_{t+1}-d_{t}}{d_{t+1}}\right|\leq\epsilon\)do \(w_{t+1}\leftarrow\frac{1}{\sum_{k=0}^{K-1}n_{t+1}^{k}}\sum_{k=0}^{K-1}\ n_{t+1}^{k}w_{t+1}^{k}\); \(w_{t+1}^{0},w_{t+1}^{1}\ldots w_{t+1}^{K-1}\gets w_{t+1}\) \(n_{t+1}^{0},n_{t+1}^{1}\ldots\ n_{t+1}^{k-1}\gets 0\); \(d_{t+1}=0\) else \(w_{t+1}\gets w_{t}\) endif endfor Output:\(w_{T}\)
```  
**Algorithm 1** Federated Lagygregate (FedLA)  
Where \(E\) represents the number of local training epochs, \(B\) represents the batch size for loading data, and \(w^{k}\) represents the weight of \(k\)-th device which is initialized to the received weight in the \(t\)-th round. \(T\) represents the number of total rounds; \(w_{0}\) represents initial global weight; \(d_{0}\) indicates the initial WD value, generally assign 0; \(\epsilon\) is the threshold of WDR; and \(n_{t}^{k}\) indicates the number of cumulative samples in the \(t\)-th round. FedLA adopts the same local solver as FedAvg, which optimizes the received weight by mini-batch SGD, and then the updated weights are sent back to server. Unlike FedAvg, aggregation doesn't occur every round, but is determined according to WDR. The impact of heterogeneous data could be effectively mitigated through aggregation with intervals. In addition to adding WDR (computational complexity O(K2d), where \(d\) is the number of parameters in the model) and postponing aggregation, no other optimizations are introduced. Thus, FedLA has the same convergence rate O(1/T) as FedAvg [4] for strongly convex and smooth problems in non-IID. In practice, only classifier weights are needed for judgment, and the weights of feature layers are transmitted when aggregation is possible which ensures efficiency and reduces redundant aggregation. Moreover, it is compatible with other optimization and privacy strategies.