  Existing global convergence guarantees of (stochastic) gradient descent do
not apply to practical deep networks in the practical regime of deep learning
beyond the neural tangent kernel (NTK) regime. This paper proposes an
algorithm, which is ensured to have global convergence guarantees in the
practical regime beyond the NTK regime, under a verifiable condition called the
expressivity condition. The expressivity condition is defined to be both
data-dependent and architecture-dependent, which is the key property that makes
our results applicable for practical settings beyond the NTK regime. On the one
hand, the expressivity condition is theoretically proven to hold
data-independently for fully-connected deep neural networks with narrow hidden
layers and a single wide layer. On the other hand, the expressivity condition
is numerically shown to hold data-dependently for deep (convolutional) ResNet
with batch normalization with various standard image datasets. We also show
that the proposed algorithm has generalization performances comparable with
those of the heuristic algorithm, with the same hyper-parameters and total
number of iterations. Therefore, the proposed algorithm can be viewed as a step
towards providing theoretical guarantees for deep learning in the practical
regime.
