Semi-Cyclic Stochastic Gradient Descent

Hubert Eichner, Tomer Koren, Brendan Mcmahan, Nathan Srebro, Kunal Talwar
Proceedings of the 36th International Conference on Machine Learning, PMLR 97:1764-1773, 2019.

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.

Cite this Paper

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.} }
Endnote
%0 Conference Paper %T Semi-Cyclic Stochastic Gradient Descent %A Hubert Eichner %A Tomer Koren %A Brendan Mcmahan %A Nathan Srebro %A Kunal Talwar %B Proceedings of the 36th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2019 %E Kamalika Chaudhuri %E Ruslan Salakhutdinov %F pmlr-v97-eichner19a %I PMLR %P 1764--1773 %U https://proceedings.mlr.press/v97/eichner19a.html %V 97 %X 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.
APA
Eichner, H., Koren, T., Mcmahan, B., Srebro, N. & Talwar, K.. (2019). Semi-Cyclic Stochastic Gradient Descent. Proceedings of the 36th International Conference on Machine Learning, in Proceedings of Machine Learning Research 97:1764-1773 Available from https://proceedings.mlr.press/v97/eichner19a.html.

Related Material