Deep Learning
Supplementary Materials for Nimble: Lightweight and Parallel GPU T ask Scheduling for Deep Learning Appendix A Proofs on the Stream Assignment Algorithm of Nimble
In this section, we provide detailed proofs on the theorems presented in Section 4.2. We assume that the computation graph of a neural network is given. Here we define important concepts and terminologies used in the following proofs. F or any (u,v) E, f ( u) = f (v) or there exists a path P E from u to v such that P ฮ null= . Prior to the proof of Theorem 1-2, we describe and prove Lemma 1 and Lemma 2. Lemma 1. We will prove by contradiction.
An efficient nonconvex reformulation of stagewise convex optimization problems
Convex optimization problems with staged structure appear in several contexts, including optimal control, verification of deep neural networks, and isotonic regression. Off-the-shelf solvers can solve these problems but may scale poorly. We develop a nonconvex reformulation designed to exploit this staged structure. Our reformulation has only simple bound constraints, enabling solution via projected gradient methods and their accelerated variants.