A block coordinate descent optimizer for classification problems exploiting convexity

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

Abstract: Standard deep learning optimization relies on first-order methods like SGD or Adam due to the non-convex nature of the loss landscape. This paper introduces a hybrid optimizer, NGD (Newton/Gradient Descent), which leverages a block coordinate descent approach. By identifying that the cross-entropy loss is globally convex with respect to the final linear layer weights, NGD applies second-order Newton steps to the classifier while maintaining first-order updates for hidden layers. Experimental results across MNIST, Fashion MNIST, and CIFAR-10 demonstrate that NGD achieves faster convergence and superior generalization by learning smoother basis functions.

Introduction

Training deep neural networks involves navigating a highly non-convex loss landscape. While first-order methods are computationally efficient, they often struggle with plateaus and local minima. Second-order methods, which utilize the Hessian matrix, offer faster convergence but are typically avoided due to the extreme computational cost of calculating second derivatives for millions of parameters. This research explores whether isolating a convex sub-problem within the network can make second-order methods both safe and efficient.

Methodology

The proposed NGD algorithm partitions network parameters into two groups: the hidden layers ($\xi$), which act as an adaptive basis, and the final linear layer ($W$), which performs classification. The authors prove that for standard cross-entropy loss, the objective is globally convex with respect to $W$ when $\xi$ is fixed.

NGD employs a block coordinate descent strategy:

  • Newton Step: For each batch, Newton’s method finds the globally optimal weights for the final layer. This is stable due to convexity and computationally feasible because the final layer's parameter count is relatively small.
  • Gradient Step: Standard gradient descent (e.g., Adam) updates the hidden layers to refine the features.

By alternating these steps, the classifier remains perfectly tuned to the features generated by the hidden layers throughout the training process.

Key Insights: The Adaptive Basis Perspective

A core contribution of this work is viewing the network as a system that learns a set of basis functions (hidden layers) and subsequently fits a model to them. NGD appears to provide a form of implicit regularization. In synthetic tests like the "Peaks" problem, NGD-trained networks produced smoother basis functions and cleaner decision boundaries compared to the jagged, overfit boundaries often seen with standard gradient descent.

Figure 4: Visualization of the Peaks problem comparing GD and NGD predictions, class boundaries, and learned basis functions.

Experimental Results

The researchers evaluated NGD against standard Gradient Descent (GD) and Adam across several benchmarks, including MNIST, Fashion MNIST, and CIFAR-10.

Figure 5: Training and validation accuracy across CIFAR-10, Fashion MNIST, and MNIST datasets, comparing GD and NGD over iterations.

Key findings include:

  • Accelerated Convergence: On CIFAR-10, NGD reached peak validation accuracy in approximately one-quarter of the iterations required by standard GD.
  • Enhanced Accuracy: For ConvNet architectures on CIFAR-10, NGD yielded a 1.76% improvement in final test accuracy over an optimized Adam baseline.
  • Qualitative Improvements: In 2D synthetic tests, NGD correctly identified low-density data regions that standard methods missed, resulting in more logical decision maps.

Discussion and Future Work

While NGD significantly reduces the number of iterations needed for convergence, each Newton step is more computationally intensive than a gradient step. Future work will focus on developing optimized GPU kernels to translate iteration-wise gains into wall-clock time speedups. Additionally, the "smoother" basis functions learned by NGD suggest potential benefits for adversarial robustness, which warrants further investigation. Implementing this block coordinate descent approach within standard deep learning frameworks also remains a key engineering challenge for scaling to larger models.

Reference: Patel, R. G., Trask, N. A., Gulian, M. A., & Cyr, E. C. (2020). A block coordinate descent optimizer for classification problems exploiting convexity. arXiv:2006.10123v1 [cs.LG].

Summary updated

BibTeX
@inproceedings{patel2021block,
  author = {Ravi G. Patel and Nathaniel A. 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