  The convergence of GD and SGD when training mildly parameterized neural
networks starting from random initialization is studied. For a broad range of
models and loss functions, including the most commonly used square loss and
cross entropy loss, we prove an ``early stage convergence'' result. We show
that the loss is decreased by a significant amount in the early stage of the
training, and this decrease is fast. Furthurmore, for exponential type loss
functions, and under some assumptions on the training data, we show global
convergence of GD. Instead of relying on extreme over-parameterization, our
study is based on a microscopic analysis of the activation patterns for the
neurons, which helps us derive more powerful lower bounds for the gradient. The
results on activation patterns, which we call ``neuron partition'', help build
intuitions for understanding the behavior of neural networks' training
dynamics, and may be of independent interest.
