본문 바로가기
KERD
논문KCI 등재

A Sequencing Problem with Generalized Due Dates for Distributed Training of Neural Networks

0

조회

0

다운로드

0

인용

0

참고문헌

키워드

초록

We consider the stale problem which makes the training speed slow in the field of deep learning. The problem can be formulated as a single-machine scheduling problem with generalized due dates in which the objective is to minimize the total earliness and tardiness. We show that the problem can be solved in polynomial time if the orders of the small and the large jobs in an optimal schedule are known in advance.

Abstract

We consider the stale problem which makes the training speed slow in the field of deep learning. The problem can be formulated as a single-machine scheduling problem with generalized due dates in which the objective is to minimize the total earliness and tardiness. We show that the problem can be solved in polynomial time if the orders of the small and the large jobs in an optimal schedule are known in advance.

참고문헌 (24)

  1. R.A. Ahuja, "Faster algorithm for the shortest path problem", Journal of the Association for Computing Machinery, 37, pp.213~223 (1990)
  2. Y. Bengio, "Curriculum learning", Proceedings of the 26th International Conference on Machine Learning, pp.41~48 (2009)
  3. B. Bahdanau, "Neural machine translation by jointly learning to align and translate", Proceedings of 3rd International Conference on Learning Representations (2015)
  4. T. Chilimbi, "Project ADAM: Building an efficient and scalable deep learning training system", Proceedings of the 11th USENIX Symposium on Operating Systems Design and Implementation, pp.571~582 (2014)
  5. B.C. Choi, "Strong NP-hardness of minimizing total deviation with generalized and periodic due dates", Operations Research Letters, 47, pp.433~437 (2019)
  6. B.C. Choi, "A single machine scheduling with generalized and periodic due dates", Submitted to Discrete Applied Mathematics, ~
  7. B.C. Choi, "Just-in-time scheduling with generalized due dates and identical due date intervals", Asian-Pacific Journal of Operational Research, 6, pp.1~13 (2018)
  8. J. Dean, "Large scale distributed deep networks", Proceedings of the 25th International Conference on Advances in Neural Information Processing Systems, pp.1223~1231 (2012)
  9. C. Farabet, "Learning hierarchical features for scene labeling", IEEE Transactions in Pattern Aanlysis and Machine Intelligence, 35, pp.1915~1929 (2013)
  10. Y. Gao, "Unary NP-hardness of minimizing total weighted tardiness with generalized due dates", Operations Research Letters, 44, pp.92~95 (2006)
  11. N. G. Hall, "Scheduling problems with generalized due dates", Transactions, 18, pp.220~222 (1986)
  12. N.G. Hall, "Earliness-tardiness scheduling problems II: Deviation of completion times about a restrictive common due date", Operations Research, 39, pp.847~856 (1991)
  13. G.E. Hinton, "A fast learning algorithm for deep belief nets", Neural Computation, 18, pp.1527~1554 (2006)
  14. N.G. Hall, "Earliness-tardiness scheduling problems I : Weighted deviation of completion times about a common due date", Operations Research, 39, pp.836~846 (1991)
  15. N.G. Hall, "On the complexity of generalized due date scheduling problems", European Journal of Operational Research, 51, pp.100~109 (1991)
  16. K. He, "Delving deep into rectifiers: Surpassing human-level performance on ImageNet classification", Proceedings of the 2015 International Conference on Computer Vision, pp.1026~1034 (2015)
  17. A. Krizhevsky, "ImageNet classification with deep convolutional neural networks", Proceedings of 25th International Conference on Advances in Neural Information Processing Systems, pp.1090~1098 (2012)
  18. Y. LeCun, "Deep learning", Nature, 521, pp.436~444 (2015)
  19. V. Nair, "Rectified linear units improve restricted Boltzmann machines", Proceedings of the 27th International Conference on Machine Learning, pp.807~814 (2010)
  20. S. Srikandarajah, "A note on the generalized due dates scheduling problem", Naval Research Logistics, 37, pp.587~597 (1990)
  21. N. Srivastava, "Dropout: A simply way to prevent neural networks from overfitting", Journal of Machine Learning Research, 15, pp.1929~1958 (2014)
  22. J. Tsitsiklis, "Distributed asynchronous deterministic and stochastic gradient optimization algorithms", IEEE Transactions on Automatic Control, 31, pp.803~812 (1986)
  23. L. Wa, "Single-machine scheduling to minimize the total earliness and tardiness is strongly NP-hard", Operations Research Letters, 41, pp.363~365 (2013)
  24. W. Zhang, "Staleness-aware async-SGD for distributed deep learning", Proceedings of the 25th International Joint Conference on Artificial Intelligence, pp.2350~2356 (2016)

관련 논문AI추천

이 간행물의 다른 논문 (18건)