Semi-Cyclic Stochastic Gradient Descent

Abstract

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.

Cited by in corpus (11)

• FedMD: Heterogenous Federated Learning via Model Distillation
• Adaptive Personalized Federated Learning
• Federated Learning of a Mixture of Global and Local Models
• Lower Bounds and Optimal Algorithms for Personalized Federated Learning
• FedScale: Benchmarking Model and System Performance of Federated Learning at Scale
• Federated Learning With Quantized Global Model Updates
• Distributed Optimization over Block-Cyclic Data
• An Energy Consumption Model for Electrical Vehicle Networks via Extended Federated-learning
• Global Multiclass Classification and Dataset Construction via Heterogeneous Local Experts
• Demystifying the Effects of Non-Independence in Federated Learning
• Optimization for Supervised Machine Learning: Randomized Algorithms for Data and Parameters