PreprintCited by 66Stochastic Gradient Optimization TechniquesPrivacy-Preserving Technologies in DataMachine Learning and Data Classification

Semi-Cyclic Stochastic Gradient Descent

Open access
Eichner, Hubert, Koren, Tomer, McMahan, H. Brendan, Srebro, Nathan, Talwar, Kunal·2019·arXiv

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.

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

DataCite · 10.48550/arxiv.1904.10120

Cites

0 citation errors · 0 not checkable

Statistics

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • When component distributions truly differ, pluralism can beat the ideal IID baseline.

    “When the component distributions are actually different, pluralism can outperform the “ideal” IID baseline.”

    From Federated Learning for Healthcare Informatics (2021) · cites this paper as [28]

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Cites

The publisher hasn’t deposited this paper’s reference list.

Research works printed but not linked: 25

  1. Amit, Y., Fink, M., Srebro, N., and Ullman, S. Uncovering shared structures in multiclass classification. In Proceedings of the 24th international conference on Machine learning , pp. 17-24. ACM, 2007.
  2. Ando, R. K. and Zhang, T. A framework for learning predictive structures from multiple tasks and unlabeled data. Journal of Machine Learning Research , 6(Nov):18171853, 2005.
  3. Argyriou, A., Evgeniou, T., and Pontil, M. Convex multitask feature learning. Machine Learning , 73(3):243-272, 2008.
  4. Arjevani, Y. and Shamir, O. Communication complexity of distributed convex learning and optimization. In Advances in neural information processing systems 28 , pp. 1756-1764, 2015.
  5. Baxter, J. A model of inductive bias learning. Journal of Artificial Intelligence Research , 12:149-198, 2000.
  6. Ben-David, S. and Schuller, R. Exploiting task relatedness for multiple task learning. In Learning Theory and Kernel Machines , pp. 567-580. Springer, 2003.
  7. Bonawitz, K., Eichner, H., Grieskamp, W., Huba, D., Ingerman, A., Ivanov, V., Kiddon, C., Konecn´ y, J., Mazzocchi, S., McMahan, H. B., Overveldt, T. V., Petrou, D., Ramage, D., and Roselander, J. Towards federated learning at scale: System design. In Conference on Systems and Machine Learning (SysML) , 2019. URL http://arxiv.org/abs/1902.01046 . · arXiv
  8. Carmon, Y., Duchi, J. C., Hinder, O., and Sidford, A. Lower bounds for finding stationary points i. arXiv preprint arXiv:1710.11606 , 2017. · arXiv
  9. Caruana, R. Multitask learning. Machine learning , 28(1): 41-75, 1997.
  10. Even-Dar, E., Kearns, M., Mansour, Y., and Wortman, J. Regret to the best vs. regret to the average. Machine Learning , 72(1):21-37, Aug 2008. ISSN 15730565. doi: 10.1007/s10994-008-5060-z. URL https: //doi.org/10.1007/s10994-008-5060-z . · DOI
  11. Evgeniou, T. and Pontil, M. Regularized multi-task learning. In Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining , pp. 109-117. ACM, 2004.
  12. Evgeniou, T., Micchelli, C. A., and Pontil, M. Learning multiple tasks with kernel methods. Journal of Machine Learning Research , 6(Apr):615-637, 2005.
  13. Hard, A., Rao, K., Mathews, R., Beaufays, F., Augenstein, S., Eichner, H., Kiddon, C., and Ramage, D. Federated learning for mobile keyboard prediction. arXiv preprint 1811.03604 , 2018. · arXiv
  14. Hazan, E. Introduction to online convex optimization. Foundations and Trends R © in Optimization , 2(3-4):157-325, 2016.
  15. Koneˇ cn´ y, J., McMahan, H. B., Ramage, D., and Richt´ arik, P. Federated optimization: Distributed machine learning for on-device intelligence. arXiv preprint arXiv:1610.02527 , 2016. · arXiv
  16. Maurer, A. Bounds for linear multi-task learning. Journal of Machine Learning Research , 7(Jan):117-139, 2006.
  17. McMahan, H. B., Moore, E., Ramage, D., Hampson, S., and y Arcas, B. A. Communication-efficient learning of deep networks from decentralized data. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics , pp. 1273-1282, 2017.
  18. Sani, A., Neu, G., and Lazaric, A. Exploiting easy data in online optimization. In Advances in Neural Information Processing Systems , pp. 810-818, 2014.
  19. Shalev-Shwartz, S. Online learning and online convex optimization. Foundations and Trends R © in Machine Learning , 4(2):107-194, 2012.
  20. Shalev-Shwartz, S., Shamir, O., Srebro, N., and Sridharan, K. Stochastic convex optimization. In Proceedings of the 22nd Annual Conference on Learning Theory (COLT) , 2009.
  21. Turlach, B. A., Venables, W. N., and Wright, S. J. Simultaneous variable selection. Technometrics , 47(3):349-363, 2005.
  22. Woodworth, B. and Srebro, N. Tight complexity bounds for optimizing composite objectives. In Advances in neural information processing systems , pp. 3639-3647, 2016.
  23. Woodworth, B. and Srebro, N. Lower bound for randomized first order convex optimization. arXiv preprint arXiv:1709.03594 , 2017. · arXiv
  24. Woodworth, B., Wang, J., Smith, A., McMahan, B., and Srebro, N. Graph oracle models, lower bounds, and gaps for parallel stochastic optimization. In Advances in Neural Information Processing Systems 31 , pp. 85058515. 2018.
  25. Zinkevich, M. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the 20th International Conference on Machine Learning (ICML) , pp. 928-936, 2003.

Cited by

Sorted by citations

Authors
Eichner, H., Koren, T., McMahan, H. B., Srebro, N., & Talwar, K.
Affiliations
  • Google (United States) (US)
  • Toyota Technological Institute at Chicago (US)
Venue
arXiv
Publisher
arXiv
Published
2019
Pages
1764-1773
ISSN
2331-8422 (ISSN-L)
OpenAlex
W2941142392
Cited by
66
References
0
Citations by year
2025: 2 · 2024: 11 · 2023: 9 · 2022: 5 · 2021: 14 · 2020: 24 · 2019: 1
Type
posted content
Language
en
Open access
Locations
  • arXiv (Cornell University) (submittedVersion)
  • arXiv (Cornell University)
  • International Conference on Machine Learning
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Stochastic Gradient Optimization Techniques
  • Physical Sciences › Computer Science › Artificial Intelligence › Privacy-Preserving Technologies in Data
  • Physical Sciences › Computer Science › Artificial Intelligence › Machine Learning and Data Classification
Keywords
stochastic gradient descent, non-IID data, federated learning, convex optimization, performance guarantees, heterogeneous devices

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review