A Block Coordinate Descent Optimizer for Classification Problems Exploiting Convexity

Ravi G. Patel, Nathaniel Trask, Mamikon A. Gulian, Eric C. Cyr

Introduction

Training deep neural networks is a fundamental challenge in machine learning due to the highly non-convex nature of the loss landscape. Standard first-order optimizers like Stochastic Gradient Descent (SGD) or Adam are computationally efficient but often suffer from slow convergence and high sensitivity to hyperparameter tuning. While second-order methods (like Newton’s method) offer faster theoretical convergence by utilizing curvature information (the Hessian matrix), they are typically computationally prohibitive for large-scale models.

Researchers at Sandia National Laboratories have proposed a novel hybrid approach: the Newton/Gradient Descent (NGD) optimizer. This method leverages a mathematical property of the final layer in classification networks to apply second-order optimization where it is most effective, while maintaining the efficiency of first-order methods elsewhere.

The NGD Framework

The NGD optimizer utilizes a Block Coordinate Descent strategy by partitioning the network's weights into two distinct groups:

  1. Hidden Layers ($\xi$): These layers act as an "adaptive basis," transforming raw input data into a set of high-level features.
  2. The Linear Layer ($W$): The final layer that maps these features to class predictions.

Exploiting Global Convexity

The key innovation of NGD lies in the proof that for cross-entropy loss with a softmax activation, the loss function is globally convex with respect to the weights of the final linear layer ($W$) when the hidden layers are fixed.

This allows the algorithm to alternate between two steps:

  • Newton Step for the Linear Layer: A Newton iteration (solved via Conjugate Gradient) finds the optimal fit for the final layer. Because the Hessian calculation only scales with the size of the final layer, it remains computationally feasible.
  • Gradient Step for Hidden Layers: Standard Adam or gradient descent updates are applied to the non-convex hidden layers.

By ensuring the classifier is always optimally tuned to the current feature representation, NGD achieves more stable and efficient training.

Qualitative Insights: The Adaptive Basis

Viewing the hidden layers as an "adaptive basis" provides unique insights into how NGD learns compared to standard Gradient Descent (GD). In synthetic tests like the "Peaks" problem, NGD demonstrates a superior ability to partition space.

Comparison of basis functions and predictions for the Peaks problem. NGD produces smoother internal representations compared to the jagged artifacts seen in GD.

As shown in the figure above, GD often learns "sharp" or jagged basis functions. In contrast, NGD produces significantly smoother internal representations. This smoothness suggests that NGD-trained models may be more robust to noise and adversarial perturbations.

Empirical Results

The authors evaluated NGD across several standard benchmarks, including MNIST, Fashion MNIST, and CIFAR-10. The results consistently show that NGD outperforms standard GD in both convergence speed and final accuracy.

Training and validation accuracy across multiple datasets. NGD (black) consistently converges faster and often reaches higher final accuracy than GD (red).

Key Performance Metrics

  • Convergence Speed: On the CIFAR-10 benchmark, NGD reached the peak validation accuracy of standard GD in approximately one-quarter of the iterations.
  • Accuracy Gains: For a CIFAR-10 ConvNet architecture, NGD improved final test accuracy by 1.76% over optimized Adam.
  • Implicit Regularization: The researchers noted that limiting the number of Conjugate Gradient iterations in the Newton step acts as a form of implicit regularization, preventing overfitting and further boosting validation performance.

Limitations and Future Work

While NGD reduces the number of iterations required for convergence, each Newton step is more computationally intensive than a standard gradient step. Future work will focus on developing highly optimized GPU kernels to ensure that the reduction in iterations translates directly into faster "wall-clock" training time. Additionally, exploring how NGD scales to models with extremely wide final layers (e.g., ImageNet) remains an open area of research.

Conclusion

By identifying and exploiting the local convexity within deep classification networks, the NGD optimizer provides a powerful hybrid tool for deep learning. It offers a path toward faster training and more robust models by ensuring the final classification layer is always mathematically optimized relative to the features learned by the hidden layers.

Summary updated

Abstract

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.
BibTeX
@inproceedings{patel2021block,
  author = {Ravi G. Patel and Nathaniel Trask and Mamikon A. Gulian and Eric C. Cyr},
  title = {{A Block Coordinate Descent Optimizer for Classification Problems Exploiting Convexity}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  url = {https://openreview.net/forum?id=0Oz59vnxK3j},
}
Figure