Search papers, labs, and topics across Lattice.
This paper investigates the performance gap between the SCAFFOLD algorithm and the simpler FedAvg in federated learning, attributing it to the phenomenon known as Edge of Stability (EoS). Through empirical analysis, the authors demonstrate that EoS dynamics negatively impact SCAFFOLD's ability to accurately estimate the global gradient, particularly under conditions of high sharpness and data heterogeneity. The findings reveal that the equilibrium sharpness is inversely related to the learning rate and influenced by data heterogeneity, providing insights into the limitations of SCAFFOLD in practical applications.
SCAFFOLD's struggles in federated optimization stem from its inability to reliably estimate the global gradient at the Edge of Stability, revealing critical limitations in its design.
In federated learning, it is well known that heterogeneous data can (in theory) slow down optimization, and much effort has been directed at designing optimization algorithms that are unaffected by data heterogeneity, such as the SCAFFOLD algorithm. Yet, despite strong theoretical guarantees, SCAFFOLD does not usually outperform the much simpler FedAvg in practice. In this work, we propose that this gap is due to the presence of Edge of Stability (EoS) and progressive sharpening in federated optimization, supported by extensive empirical probing. First, we find that EoS-like dynamics occur with both FedAvg and SCAFFOLD under a variety of architectures and hyperparameters. We observe that the equilibrium value of the sharpness is inversely proportional to the learning rate (as in GD), and interestingly, the degree of data heterogeneity (but not the number of local steps) also affects the equilibrium value. Most importantly, we observe that SCAFFOLD's ability to estimate the gradient of the global objective is severely degraded at the EoS, as measured by the correlation between sharpness and SCAFFOLD's error in estimating the global gradient along the optimization trajectory. This suggests a mechanism for SCAFFOLD's lackluster performance in deep learning: with high sharpness at the EoS, SCAFFOLD cannot reliably estimate the global gradient.
