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

다국어 초록 (Multilingual 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.

참고문헌 (Reference)

1 Y. Gao, "Unary NP-hardness of minimizing total weighted tardiness with generalized due dates" 44 : 92-95, 2006

2 B.C. Choi, "Strong NP-hardness of minimizing total deviation with generalized and periodic due dates" 47 : 433-437, 2019

3 W. Zhang, "Staleness-aware async-SGD for distributed deep learning" 2350-2356, 2016

4 L. Wa, "Single-machine scheduling to minimize the total earliness and tardiness is strongly NP-hard" 41 : 363-365, 2013

5 N. G. Hall, "Scheduling problems with generalized due dates" 18 : 220-222, 1986

6 V. Nair, "Rectified linear units improve restricted Boltzmann machines" 807-814, 2010

7 T. Chilimbi, "Project ADAM: Building an efficient and scalable deep learning training system" 571-582, 2014

8 N.G. Hall, "On the complexity of generalized due date scheduling problems" 51 : 100-109, 1991

9 B. Bahdanau, "Neural machine translation by jointly learning to align and translate" 2015

10 C. Farabet, "Learning hierarchical features for scene labeling" 35 : 1915-1929, 2013

11 J. Dean, "Large scale distributed deep networks" 1223-1231, 2012

12 B.C. Choi, "Just-in-time scheduling with generalized due dates and identical due date intervals" 6 : 1-13, 2018

13 A. Krizhevsky, "ImageNet classification with deep convolutional neural networks" 1090-1098, 2012

14 R.A. Ahuja, "Faster algorithm for the shortest path problem" 37 : 213-223, 1990

15 N.G. Hall, "Earliness-tardiness scheduling problems II: Deviation of completion times about a restrictive common due date" 39 : 847-856, 1991

16 N.G. Hall, "Earliness-tardiness scheduling problems I : Weighted deviation of completion times about a common due date" 39 : 836-846, 1991

17 N. Srivastava, "Dropout: A simply way to prevent neural networks from overfitting" 15 : 1929-1958, 2014

18 J. Tsitsiklis, "Distributed asynchronous deterministic and stochastic gradient optimization algorithms" 31 : 803-812, 1986

19 K. He, "Delving deep into rectifiers: Surpassing human-level performance on ImageNet classification" 1026-1034, 2015

20 Y. LeCun, "Deep learning" 521 : 436-444, 2015

21 Y. Bengio, "Curriculum learning" 41-48, 2009

22 B.C. Choi, "A single machine scheduling with generalized and periodic due dates"

23 S. Srikandarajah, "A note on the generalized due dates scheduling problem" 37 : 587-597, 1990

24 G.E. Hinton, "A fast learning algorithm for deep belief nets" 18 : 1527-1554, 2006