ICML 2019oral134 citations
Semi-Cyclic Stochastic Gradient Descent
Hubert Eichner, Tomer Koren, Brendan Mcmahan, Nathan Srebro, Kunal Talwar
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 guarantees as for i.i.d., non-cyclic, sampling.
BibTeX
@InProceedings{pmlr-v97-eichner19a,
title = {Semi-Cyclic Stochastic Gradient Descent},
author = {Eichner, Hubert and Koren, Tomer and Mcmahan, Brendan and Srebro, Nathan and Talwar, Kunal},
booktitle = {Proceedings of the 36th International Conference on Machine Learning},
pages = {1764--1773},
year = {2019},
editor = {Chaudhuri, Kamalika and Salakhutdinov, Ruslan},
volume = {97},
series = {Proceedings of Machine Learning Research},
month = {09--15 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v97/eichner19a/eichner19a.pdf},
url = {https://proceedings.mlr.press/v97/eichner19a.html},
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 guarantees as for i.i.d., non-cyclic, sampling.}
}