Semi-Cyclic Stochastic Gradient Descent

By Hubert Eichner, Tomer Koren, H. Brendan McMahan, Nati Srebro, Kunal Talwar. 2019

118 citations recorded by the source corpus.

We consider convex SGD updates with a block-cyclic structure, i.e. where each cycle consists of a small number of blocks, each with many samples from a possibly different, block-specific, distribution. This situation arises, e.g., in Federated Learning where the mobile devices available for updates at different times during the day have different characteristics. We show that such block-cyclic structure can significantly deteriorate the performance of SGD, but propose a simple approach that allows prediction with the same performance guarantees as for i.i.d., non-cyclic, sampling.

Subfields: Artificial Intelligence, Computer Networks and Communications, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

In Optimization & Training

Citations in the corpus

Advances and Open Problems in Federated Learning (2019, methodology): “[151] described this issue and some mitigation strategies, but many open questions remain.”
Turbo-Aggregate: Breaking the Quadratic Aggregation Barrier in Secure Federated Learning (2020, background): “stochastic gradient descent on clear (unmasked) gradient updates, to reduce communication load [36] or to model data-heterogeneity [37].”
Secure Federated Submodel Learning (2019, background): “Eichner et al. [38] captured data heterogeneity in federated learning, particularly cyclic patterns, and offered a pluralistic solution for convex objectives and sequential SGD. Fourth is regarding production and standardization.”
Federated Learning: Challenges, Methods, and Future Directions (2019, background): “[14] investigate a pluralistic solution (adaptively choosing between a global model and device-specific models) to address the cyclic patterns in data samples during federated training.”
Adaptive Personalized Federated Learning (2020, methodology): “This pluralistic approach for federated optimization (FO) has recently resulted in significant research in personalized learning schemes (Eichner et al., 2019; Smith et al., 2017; Dinh et al., 2020; Mansour et al., 2020; Fallah et al., 2020; Li et al., 2020a).”
FedMD: Heterogenous Federated Learning via Model Distillation (2019, background): “There is also statistical heterogne-ity (the non i.i.d. problem) where clients have a varying amount of data coming from distinct distributions [9, 10, 11, 12, 13, 14].”
Federated Learning of a Mixture of Global and Local Models (2020, methodology): “Approaches based on variational inference Corinzia & Buhmann (2019), cyclic patterns in practical FL data sampling Eichner et al. (2019) and transfer learning Zhao et al. (2018) have been proposed. The second motivation for our work is the realization that even very simple variants of FedAvg, such a”
Federated Learning With Quantized Global Model Updates (2020, methodology): “Different approaches have been studied to mitigate the effect of non-iid data in FL [3, 13–17].”
Federated Learning for Healthcare Informatics (2019, background): “Recently, Smith et al. [96] empirically demonstrated this point on real-world federated datasets and proposed a novel method MOCHA to solve a general convex MTL problem with handling the system challenges at the same time.”
Lower Bounds and Optimal Algorithms for Personalized Federated Learning (2020, unknown): “There are multiple strategies in the literature for incorporating the personalization into FL: multi-task learning [49, 48, 14], transfer learning [54, 23], variational inference [8], mixing of the local and global models [41, 19, 31, 10] and others [13].”
FedScale: Benchmarking Model and System Performance of Federated Learning at Scale (2021, background): “While the first two aspects are oft-mentioned in the FL literature [36], network connectivity and the availability of client devices can affect both and, in turn, impair model convergence [20, 31].”
Artemis: tight convergence guarantees for bidirectional compression in Federated Learning (2020, background): “[2019]; Eichner et al. [2019]; Li et al.”
Achieving Linear Speedup with Partial Worker Participation in Non-IID Federated Learning (2021, background): “In practice, the workers need to be in certain states in order to be able to participate in FL (e.g., in charging or idle states, etc.(Eichner et al., 2019)).”
A Survey on Federated Learning for Resource-Constrained IoT Devices (2021, unknown): “Besides, Eichner et al. [172] aimed to identify cyclic patterns within data samples, while a detailed analysis of transfer learning strategy for personalization during FL can be seen in [170].”
Federated learning with hierarchical clustering of local updates to improve training on non-IID data (2020, methodology): “[13] propose a semi-cyclic method to train pluralistic models that perform model averaging over blocks of clients (e.”
FedScale: Benchmarking Model and System Performance of Federated Learning (2021, background): “, device drop-out or rejoining) can affect the dynamics of data availability (distribution shift of cross-device data), which may impair model convergence [11]; too few clients can lead to unstable statistical training convergence, but too many can slow down practical model aggregation because of he”