Large Stepsizes Federated Learning on Logistic Regression with Linearly Separable Data: The Case of Heterogeneous Devices

This paper revisits the distributed learning problem for training a multinomial logistic regression model with the Federated Averaging ($\mathtt{\text{FedAvg}}$) algorithm. We concentrate on a scenario with arbitrarily large stepsizes and heterogeneous update rules where the devices may perform a different number of local updates in each round. We show that, with linearly separable data, $\mathtt{\text{FedAvg}}$ is stable with any stepsizes and the objective values converge to zero at the rate of $\mathcal{O}(1\mathrm{/}R)$, where $R$ is the number of communication rounds. Our result also demonstrates that the effects of device heterogeneity vanish asymptotically. For sufficiently large $R$, the objective values decrease monotonically and is bounded by $\mathcal{O}(1\mathrm{/}(R{T}_{\mathrm{a}\mathrm{v}\mathrm{g}}))$, where $T_{\mathrm{a}\mathrm{v}\mathrm{g}}$ is the average number of local update steps per communication round across devices. Numerical experiments support our findings.