Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU
  Networks
  We study the problem of training deep neural networks with Rectified Linear
Unit (ReLU) activation function using gradient descent and stochastic gradient
descent. In particular, we study the binary classification problem and show
that for a broad family of loss functions, with proper random weight
initialization, both gradient descent and stochastic gradient descent can find
the global minima of the training loss for an over-parameterized deep ReLU
network, under mild assumption on the training data. The key idea of our proof
is that Gaussian random initialization followed by (stochastic) gradient
descent produces a sequence of iterates that stay inside a small perturbation
region centering around the initial weights, in which the empirical loss
function of deep ReLU networks enjoys nice local curvature properties that
ensure the global convergence of (stochastic) gradient descent. Our theoretical
results shed light on understanding the optimization for deep learning, and
pave the way for studying the optimization dynamics of training modern deep
neural networks.
