IP Library › Granted Patent US 12,190,232
Granted Patent B2
US 12,190,232 · App. 16/327,679 · Granted Jan 7, 2025

Asychronous training of machine learning model

Inventors: Taifeng Wang (Redmond, WA); Wei Chen (Redmond, WA); Tie-Yan Liu (Redmond, WA); Fei Gao (Redmond, WA); Qiwei Ye (Redmond, WA)
Assignee: Microsoft Technology Licensing, LLC
G06N3/08G06N3/04G06N3/045G06N3/084
View Patent ↗
Loading inventors, assignments & file history…
Monitor This Case
Get email alerts when status or documents change.
Order Certified Copies
Most orders are placed with the USPTO same day — all within 24 business hours.
Order via The Patent Place →
Pre-filled with this patent's details
Quick Facts
Patent No.
US 12,190,232
App. No.
16/327,679
Granted
Jan 7, 2025
Kind
B2
Abstract

Various implementations relate to asynchronous training of a machine learning model. A server receives feedback data generated by training the machine learning model from a worker. The feedback data are obtained by the worker with its own training data and are associated with previous values of a set of parameters of the machine learning model at the worker. The server determines differences between the previous values and current values of the set of parameters at the server. The current value may have been updated for once or more due to operation of other workers. Then, the server can update the current values of the set of parameters based on the feedback data and the differences between values of the set of parameters. Thus, the updating does not only take the training result of each worker into consideration but also makes proper compensation for delay between different workers.

Claims (52)

1. A computer-implemented method comprising:

receiving, by a computing device from a worker implemented by a computer processing unit, feedback data generated by training a machine learning model, the feedback data being associated with previous values of a set of parameters of the machine learning model at the worker;

determining, by the computing device, differences between the previous values and current values of the set of parameters;

calculating a zero-order term and a first-order term of a series expansion based on the feedback data and the differences; and

updating the current values based on the zero-order term and the first-order term to obtain updated values of the set of the parameters, wherein updating the current values based on the zero-order term and the first-order term:

comprises applying update amounts to the current values, the update amounts including a term that is a product of a delayed gradient and a learning rate; and

provides compensation for delay between a plurality of workers implemented by one or more computer processing units that each provide respective feedback data generated by training the machine learning model, the compensation for delay reducing mismatch between the plurality of workers and enabling efficient asynchronous training of the machine learning model.

2. The method of claim 1 , wherein the feedback data indicates trends of change of an optimization objective of the machine learning model with respect to the previous values of the set of parameters.

3. The method of claim 2 , wherein updating the current values comprises:

determining coefficients of a transformation based on the trends of change; and

determining differential amounts between the current values and the updated values by applying the transformation on the differences.

4. The method of claim 3 , wherein the transformation is a linear transformation, the coefficients are linear rates of change, and the trends of change are represented by a gradient of the optimization objective with respect to the previous values of the set of parameters.

5. The method of claim 4 , wherein determining the coefficients of the transformation comprises:

computing a tensor product of the gradient as unbiased estimates of the linear rates of change.

6. The method of claim 4 , wherein determining the coefficients of the transformation comprises:

determining, based on the gradient, magnitudes of rates of change of the optimization objective with respect to respective parameters in the set of parameters; and

determining the linear rates of change based on the magnitudes of the rates of change.

7. The method of claim 6 , wherein determining the linear rates of change based on the magnitudes of the rates of change comprises:

computing squares of the magnitudes of the rates of change; and

determining the linear rates of change based on the squares of the magnitudes of the rates of change.

8. The method of claim 1 , further comprising:

receiving a request for the set of parameters from the worker; and

in response to the request, transmitting the updated values of the set of parameters to the worker.

9. The method of claim 2 , wherein the machine learning model includes a neural network model and the optimization objective is represented by a cross entropy loss function.

10. An electronic device comprising:

a first processing unit;

a memory coupled to the first processing unit and storing instructions that, when executed by the first processing unit, cause the electronic device to perform acts comprising:

receiving, from a worker implemented by a second processing unit, feedback data generated by training a machine learning model, the feedback data being associated with previous values of a set of parameters of the machine learning model at the worker;

determining differences between the previous values and current values of the set of parameters;

calculating a zero-order term and a first-order term of a series expansion based on the feedback data and the differences; and

updating the current values based on the zero-order term and the first-order term to obtain updated values of the set of the parameters, wherein updating the current values provides compensation for delay between a plurality of workers providing respective feedback data generated by training the machine learning model, the compensation for delay reducing mismatch between the plurality of workers and enabling efficient asynchronous training of the machine learning model, and wherein update amounts applied to the current values as part of the updating include a term that is a product of a delayed gradient and a learning rate.

11. The device of claim 10 , wherein the feedback data indicate trends of change of an optimization objective of the machine learning model with respect to the previous values of the set of parameters.

12. The device of claim 11 , wherein updating the current values comprises:

determining coefficients of a transformation based on the trends of change; and

determining differential amounts between the current values and the updated values by applying the transformation on the differences.

13. The device of claim 12 , wherein the transformation is a linear transformation, the coefficients are linear rates of change, and the trends of change are represented by the delayed gradient of the optimization objective with respect to the previous values of the set of parameters.

14. The device of claim 13 , wherein determining the coefficients of the transformation comprises:

computing a tensor product of the delayed gradient as unbiased estimates of the linear rates of change.

15. A system comprising:

a processor; and

a memory coupled to the processor and storing instructions that, when executed by the processor, cause a computing device to:

receive, from a worker implemented by a processing unit, feedback data generated by training a machine learning model, the machine learning model being a neural network comprising multiple layers, the feedback data being associated with previous values of a set of parameters of the machine learning model at the worker;

determine differences between the previous values and current values of the set of parameters;

calculate a zero-order term and a first-order term of a series expansion based on the feedback data and the differences;

update the current values based on the zero-order term and the first-order term; and

compensate for delay between a plurality of workers providing respective feedback data generated during training of the machine learning model by updating the current values based on the zero-order term and the first-order term, wherein compensating for the delay reduces mismatch between the plurality of workers and enables efficient asynchronous training of the machine learning model.

16. The system of claim 15 , wherein the machine learning model is trained using training data that is randomly sampled from a complete set of training data.

17. The system of claim 15 , wherein series expansion corresponds to Taylor expansion and other order terms of the series expansion are not used to update the current values.

18. The system of claim 15 , wherein the first-order term reflects a rate of change of a gradient of an optimization objective.

19. The system of claim 15 , wherein the first-order term corresponds to a second-order derivative of a cross entropy loss function.

20. The system of claim 15 , wherein the instructions, when executed, further cause the computing device to:

use the trained machine learning model to perform a task.

Assignments (1)
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded May 1, 2019
From: WANG, TAIFENG; CHEN, WEI; LIU, TIE-YAN; GAO, FEI; YE, QIWEI
To: MICROSOFT TECHNOLOGY LICENSING, LLC
Reel/Frame 049049/0518 →
Priority Claims (1)
CN 201610730381.8 · Aug 25, 2016 · national
Continuity (1)
Related Publication 20190197404A1 · Jun 27, 2019
References Cited (61)
US 8027938B1 · Xu et al. · 2011 [cited by applicant]
US 9218573B1 · Corrado et al. · 2015 [cited by applicant]
US 9269057B1 · Chandra et al. · 2016 [cited by applicant]
US 10152676B1 · Strom · 2018 [cited by examiner]
US 20030009742A1 · Bass et al. · 2003 [cited by applicant]
US 20140379386A1 · Drennan, III · 2014 [cited by applicant]
US 20150127337A1 · Heigold et al. · 2015 [cited by applicant]
CN 104346214A · 2015 [cited by applicant]
CN 105022699A · 2015 [cited by applicant]
CN 105683944A · 2016 [cited by applicant]
CN 105825269A · 2016 [cited by applicant]
CN 105894087A · 2016 [cited by applicant]
De, S., Taylor, G., & Goldstein, T. (2015). Scaling Up Distributed Stochastic Gradient Descent Using Variance Reduction. arXiv preprint arXiv:1512.02970v1. (Year: 2015). [cited by examiner]
Hsu, D., Karampatziakis, N., Langford, J., & Smola, A. (2011). Parallel online learning. arXiv preprint arXiv:1103.4204. (Year: 2011). [cited by examiner]
J Reddi, S., Hefny, A., Sra, S., Poczos, B., & Smola, A. J. (2015). On variance reduction in stochastic gradient descent and its asynchronous variants. Advances in neural information processing systems, 28. (Year: 2015). [cited by examiner]
Agarwal, A., & Duchi, J. C. (2011). Distributed delayed stochastic optimization. Advances in neural information processing systems, 24. (Year: 2011). [cited by examiner]
Witold Pedrycz, “Cluster-Centric Fuzzy Modeling”, IEEE, 2014 (Year: 2014). [cited by examiner]
Irina Higgins, “Early Visual Concept Learning with Unsupervised Deep Learning”, 2016 (Year: 2016). [cited by examiner]
Mu Li, “Communication Efficient Distributed Machine Learning with the Parameter Server” (Year: 2014). [cited by examiner]
Ziangru Lian, “A Comprehensive Linear Speedup Analysis for Asynchronous Stochastic Parallel Optimization from Zeroth-Order to First-Order”, (Year: 2016). [cited by examiner]
“Notice of Allowance Issued in Chinese Patent Application No. 201610730381.8”, Mailed Date: Mar. 26, 2021, 5 Pages. [cited by applicant]
“First Office Action and Search Report Issued in Chinese Patent Application No. 201610730381.8”, Mailed Date : Nov. 4, 2020, 8 Pages. [cited by applicant]
Q. Meng et al., “Asynchronous Accelerated Stochastic Gradient Descent”, Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence (IJCAI-16): 1853-1859 (2016). [cited by applicant]
X. Lian et al., “Asynchronous Parallel Stochastic Gradient for Nonconvex Optimization”, Department of Computer Science, University of Rochester: 1-31 (2015) (revised 2017). [cited by applicant]
S. Becker et al., “Improving the Convergence of Back-Propagation Learning with Second Order Methods”, Proceeding of the 1988 Connectionist Models Summer School: 29-37(1989). [cited by applicant]
International Search Report and Written Opinion for PCT/US2017/047247, mailed Nov. 10, 2017. [cited by applicant]
“Office Action Issued in European Patent Application No. 17758721.9”, Mailed Date: Mar. 19, 2020, 12 Pages. [cited by applicant]
“Distributed Machine Learning Toolkit”, Retrieved From: http://www.dmtk.io/, Aug. 24, 2016, 2 Pages. [cited by applicant]
Agarwal, et al., “Distributed Delayed Stochastic Optimization”, Proceedings of Neural Information Processing Systems, Dec. 12, 2011, 9 Pages. [cited by applicant]
Avron, et al., “Revisiting Asynchronous Linear Solvers: Provable Convergence Rate through Randomization”, in Journal of the ACM, vol. 62, Issue 6, Dec. 2015, 27 Pages. [cited by applicant]
Bahdanau, et al., “Neural Machine Translation by Jointly Learning to Align and Translate”, in Proceeding of International Conference on Learning Representations, May 7, 2015, 15 Pages. [cited by applicant]
Bottou, Leon, “Stochastic Gradient Descent Tricks”, in Publication of Neural Networks: Tricks of the Trade, Springer, Nov. 17, 2012, 16 Pages. [cited by applicant]
Chan, et al., “Distributed Asynchronous Optimization of Convolutional Neural Networks”, in Publication of Interspeech 2014, Sep. 20, 2015, 6 Page. [cited by applicant]
Chen, et al., “Revisiting Distributed Synchronous SGD”, in Repository of: https://arxiv.org/abs/1604.00981, Apr. 15, 2016, 5 Pages. [cited by applicant]
Chen, et al., “Scalable Training of Deep Learning Machines by Incremental Block Training With Intra-Block Parallel Optimization and Blockwise Model-Update Filtering”, in Proceedings of IEEE International Conference on A… [cited by applicant]
Dean, et al., “Large scale distributed deep networks”, in Proceedings of 26th Annual Conference on Neural Information Processing System, Dec. 3, 2012, 9 Pages. [cited by applicant]
Duchi, et al., “Asynchronous Stochastic Convex Optimization”, Retrieved From: https://arxiv.org/pdf/1508.00882.pdf, Aug. 4, 2015, 38 Pages. [cited by applicant]
Faraby, Said Al., “A More Robust Asynchronous SGD”, in Master Thesis of University of Amsterdam, Feb. 2015, 46 Pages. [cited by applicant]
Folland, G, “Higher-Order Derivatives and Taylors Formula in Several Variables”, Retrieved From: https://sites.math.washington.edu/˜folland/Math425/taylor2.pdf, Aug. 17, 2016, 4 Pages. [cited by applicant]
Gupta, et al., “Model Accuracy and Runtime Tradeoff in Distributed Deep Learning”, in Repository of: https://arxiv.org/pdf/1509.04210.pdf, Sep. 2015, 10 Pages. [cited by applicant]
Hastie, et al., “The Elements of Statistical Learning”, in Publication of Springer Series in Statistics, Jan. 2009, 758 Pages. [cited by applicant]
He, et al., “Deep Residual Learning for Image Recognition”, in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, Jun. 26, 2016, pp. 770-778. [cited by applicant]
Heigold, et al., “Asynchronous Stochastic Optimization for Sequence Training of Deep Neural Networks”, in Proceedings of the IEEE International Conference on Acoustic, Speech and Signal Processing, May 4, 2014, pp. 5624… [cited by applicant]
Ho, et al., “More Effective Distributed MI via a Stale Synchronous Parallel Parameter Server”, in Proceedings of Advances in Neural Information Processing Systems 26, Dec. 5, 2013, 9 Pages. [cited by applicant]
He, Kaiming, “Deep Residual Learning for Image Recognition”, Retrieved From: https://web.archive.org/web/20170104075218/https://github.com/KaimingHe/deep-residual-networks, Jan. 4, 2017, 3 Pages. [cited by applicant]
Khalil-Hani, et al., “A-SDLM: An Asynchronous Stochastic Learning Algorithm for Fast Distributed Learning”, in Proceedings of the 13th Australasian Symposium on Parallel and Distributed Computing, Jan. 27, 2015, pp. 75-… [cited by applicant]
Kingma, et al., “Adam: A method for Stochastic Optimization”, in Proceedings of the International Conference on Learning Representations, May 7, 2015, 15 Pages. [cited by applicant]
Krizhevsky, et al., “ImageNet Classification with Deep Convolutional Neural Networks”, in Proceedings of the 26th Annual Conference on Neural Information Processing Systems, Dec. 3, 2012, pp. 1-9. [cited by applicant]
Krizhevsky, Alex, “Learning Multiple Layers of Features From Tiny Images”, in Technical report, Apr. 8, 2009, 60 Pages. [cited by applicant]
Sercu, et al., “Very Deep Multilingual Convolutional Neural Networks for LVCSR”, in Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing, Mar. 20, 2016, pp. 4955-4959. [cited by applicant]
McMahan, et al., “Delay-Tolerant Algorithms for Asynchronous Distributed Online Learning”, in Proceedings of Annual Conference on Neural Information Processing Systems, Dec. 8, 2014, 9 Pages. [cited by applicant]
Mikolov, et al., “Distributed Representations of Words and Phrases and their Compositionality”, in the Proceedings of the 27th Annual Conference on Neural Information Processing Systems, Dec. 5, 2013, 9 Pages. [cited by applicant]
Niu, et al., “Hogwild: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent”, in Proceedings of Advances in Neural Information Processing Systems, Dec. 12, 2011, 9 Pages. [cited by applicant]
Odena, Augustus, “Faster Asynchronous SGD”, in Repository of: https://arxiv.org/pdf/1601.04033.pdf, Jan. 15, 2016, 10 Pages. [cited by applicant]
Zheng, et al., “Asynchronous Stochastic Gradient Descent with Delay Compensation for Distributed Deep Learning”, in Journal of Computing Research Repository , Sep. 27, 2016, 12 Pages. [cited by applicant]
Russakovsky, et al., “ImageNet Large Scale Visual Recognition Challenge”, in International Journal of Computer Vision, vol. 115, Issue 3, Dec. 2015, 43 Pages. [cited by applicant]
Sak, et al., “Long Short-Term Memory Recurrent Neural Network Architectures for Large Scale Acoustic Modeling”, in Proceedings of Fifteenth Annual Conference of the International Speech Communication Association, Sep. 1… [cited by applicant]
Silver, et al., “Mastering the Game of Go with Deep Neural Networks and Tree Search”, in Journal of Nature, vol. 529, Jan. 28, 2016, 20 Pages. [cited by applicant]
Szegedy, et al., “Inception-V4, Inception-Resnet and the Impact of Residual Connections on Learning”, in Repository of: https://arxiv.org/abs/1602.07261, Feb. 23, 2016, 12 Pages. [cited by applicant]
Zhang, et al., “Deep learning with Elastic Averaging SGD”, in Proceedings of the Annual Conference on Neural Information Processing Systems, Dec. 7, 2015, 9 Pages. [cited by applicant]
Zhang, et al., “Staleness-aware Async-SGD for Distributed Deep Learning”, in Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, Jul. 9, 2016, 7 Pages. [cited by applicant]