On the Convergence of Federated Learning Algorithms without Data
  Similarity
Ali Beikmohammadi Sarit Khirirat Sindri Magnússon
Data similarity assumptions have traditionally been relied upon to understand
the convergence behaviors of federated learning methods. Unfortunately, this
approach often demands fine-tuning step sizes based on the level of data
similarity. When data similarity is low, these small step sizes result in an
unacceptably slow convergence speed for federated methods. In this paper, we
present a novel and unified framework for analyzing the convergence of
federated learning algorithms without the need for data similarity conditions.
Our analysis centers on an inequality that captures the influence of step sizes
on algorithmic convergence performance. By applying our theorems to well-known
federated algorithms, we derive precise expressions for three widely used step
size schedules: fixed, diminishing, and step-decay step sizes, which are
independent of data similarity conditions. Finally, we conduct comprehensive
evaluations of the performance of these federated learning algorithms,
employing the proposed step size strategies to train deep neural network models
on benchmark datasets under varying data similarity conditions. Our findings
demonstrate significant improvements in convergence speed and overall
performance, marking a substantial advancement in federated learning research.