BDA-PCH: Block-Diagonal Approximation of Positive-Curvature Hessian for Training Neural Networks

Sheng-Wei Chen, Chun-Nan Chou, Edward Y. Chang

Abstract

For training fully-connected neural networks (FCNNs), we propose a practical approximate second-order method including: 1) an approximation of the Hessian matrix and 2) a conjugate gradient (CG) based method. Our proposed approximate Hessian matrix is memory-efficient and can be applied to any FCNNs where the activation and criterion functions are twice differentiable. We devise a CG-based method incorporating one-rank approximation to derive Newton directions for training FCNNs, which significantly reduces both space and time complexity. Empirical studies show the efficacy and efficiency of our proposed method.

Introduction

While first-order optimization methods like Stochastic Gradient Descent (SGD) are the workhorses of deep learning, they often lack the efficiency required for complex landscapes. Second-order methods, which utilize the "curvature" of the loss landscape via the Hessian matrix, promise faster convergence and more robust steps. However, these methods are traditionally computationally prohibitive and memory-intensive for practical deep learning applications.

Researchers at HTC Research & Healthcare have introduced a practical second-order framework designed specifically for fully-connected neural networks (FCNNs). This method, referred to as PCH-CG (or EA-CG in some contexts), combines a novel "Positive-Curvature Hessian" (PCH) approximation with an efficient Conjugate Gradient solver to handle non-convex landscapes with significantly reduced overhead.

Overcoming the Roadblocks of Second-Order Optimization

Training a neural network involves navigating a non-convex loss landscape filled with hills, valleys, and saddle points. Standard second-order methods face two primary challenges:

  1. Complexity: A network with $N$ parameters requires a Hessian of size $N^2$, making storage and inversion impossible for modern architectures.
  2. Negative Curvature: In non-convex regions, the Hessian can have negative eigenvalues, causing standard Newton methods to move toward local maxima or saddle points.

The PCH (Positive-Curvature Hessian) Matrix

To address these issues, the authors derive a layer-wise recursion for the actual Hessian. To handle non-convexity, they apply a "Pos-Eig" function, decomposing the matrix and replacing negative eigenvalues with zero (or a small positive value). This ensures the matrix remains positive semi-definite (PSD), allowing the optimizer to ignore directions of negative curvature that do not lead to the minimum.

EA-CG: Expectation-Approximation Conjugate Gradient

To solve the resulting linear equations without explicit matrix inversion, the method employs a Conjugate Gradient (CG) approach enhanced by two key techniques:

  • Kronecker Factoring: The Hessian is treated as a series of smaller blocks (one per layer) represented by Kronecker products.
  • Expectation Approximation: By assuming independence between layer activations and second derivatives of the loss, the authors compute Hessian-vector products efficiently, reducing space complexity from $O(N^2)$ to a scale linear with the number of neurons per layer.

Empirical Results

The researchers evaluated the proposed method against standard SGD and existing Kronecker-factored approximations (like Fisher and Gauss-Newton variants) on two benchmarks: CIFAR-10 and ImageNet-10.

CIFAR-10 Performance

On the CIFAR-10 dataset, the PCH-CG method demonstrated superior wall-clock efficiency. As shown in the training curves, the CG-based variants (dotted lines) generally converged faster than their inverse-based (KFI) counterparts. PCH-CG reached higher testing accuracy in fewer seconds compared to both KFI methods and standard SGD.

Training loss and test accuracy on CIFAR-10. PCH-CG (red dotted) demonstrates rapid convergence in wall-clock time compared to baselines.

Scalability on ImageNet-10

When scaled to ImageNet-10, which features higher-dimensional input data, the memory efficiency of the CG-based approach became even more apparent. While some traditional KFI methods can struggle with GPU memory limits on larger layers, the PCH-CG method maintained a steady and efficient descent in training loss, outperforming SGD in final accuracy and convergence speed.

Training loss and test accuracy on ImageNet-10. The proposed PCH-CG method (red dotted) scales effectively to higher-dimensional inputs, maintaining high accuracy and low loss.

Conclusion and Future Work

The BDA-PCH framework represents a significant step toward making second-order optimization practical for deep learning. By breaking the convexity constraint and utilizing a memory-efficient CG solver, it offers a faster alternative to SGD for FCNNs.

Currently, the method is optimized for fully-connected layers. Future research aims to extend this factorization to Convolutional Neural Networks (CNNs), where shared weights present additional challenges for Hessian approximation. While the per-iteration cost remains higher than SGD, the drastic reduction in total iterations required makes PCH-CG a compelling choice for training complex networks.

Summary updated

Abstract

For training fully-connected neural networks (FCNNs), we propose a practical approximate second-order method including: 1) an approximation of the Hessian matrix and 2) a conjugate gradient (CG) based method. Our proposed approximate Hessian matrix is memory-efficient and can be applied to any FCNNs where the activation and criterion functions are twice differentiable. We devise a CG-based method incorporating one-rank approximation to derive Newton directions for training FCNNs, which significantly reduces both space and time complexity. This CG-based method can be employed to solve any linear equation where the coefficient matrix is Kronecker-factored, symmetric and positive definite. Empirical studies show the efficacy and efficiency of our proposed method.
BibTeX
@inproceedings{chen2019bda,
  author = {Sheng-Wei Chen and Chun-Nan Chou and Edward Y. Chang},
  title = {{BDA-PCH: Block-Diagonal Approximation of Positive-Curvature Hessian for Training Neural Networks}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.1609/aaai.v33i01.33013337},
}
Figure