  Second-order optimizers hold intriguing potential for deep learning, but
suffer from increased cost and sensitivity to the non-convexity of the loss
surface as compared to gradient-based approaches. We introduce a coordinate
descent method to train deep neural networks for classification tasks that
exploits global convexity of the cross-entropy loss in the weights of the
linear layer. Our hybrid Newton/Gradient Descent (NGD) method is consistent
with the interpretation of hidden layers as providing an adaptive basis and the
linear layer as providing an optimal fit of the basis to data. By alternating
between a second-order method to find globally optimal parameters for the
linear layer and gradient descent to train the hidden layers, we ensure an
optimal fit of the adaptive basis to data throughout training. The size of the
Hessian in the second-order step scales only with the number weights in the
linear layer and not the depth and width of the hidden layers; furthermore, the
approach is applicable to arbitrary hidden layer architecture. Previous work
applying this adaptive basis perspective to regression problems demonstrated
significant improvements in accuracy at reduced training cost, and this work
can be viewed as an extension of this approach to classification problems. We
first prove that the resulting Hessian matrix is symmetric semi-definite, and
that the Newton step realizes a global minimizer. By studying classification of
manufactured two-dimensional point cloud data, we demonstrate both an
improvement in validation error and a striking qualitative difference in the
basis functions encoded in the hidden layer when trained using NGD. Application
to image classification benchmarks for both dense and convolutional
architectures reveals improved training accuracy, suggesting possible gains of
second-order methods over gradient descent.
