EA-CG: An Approximate Second-Order Method for Training Fully-Connected Neural Networks

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

Introduction

Training deep neural networks efficiently remains a cornerstone of machine learning research. While first-order methods like Stochastic Gradient Descent (SGD) are the industry standard due to their low computational cost per iteration, they often suffer from slow convergence and sensitivity to plateaus. Second-order methods, such as Newton’s method, offer faster convergence by leveraging curvature information (the Hessian matrix). However, their high memory and computational overhead—historically $O(n^2)$ or $O(n^3)$—have limited their use in large-scale deep learning.

The EA-CG (Expectation Approximation - Conjugate Gradient) method introduces a novel approach to bridge this gap, specifically for fully-connected neural networks (FCNNs). By combining a robust Hessian approximation with an efficient solver, EA-CG achieves second-order convergence speeds with memory requirements comparable to first-order methods.

Addressing Scalability and Non-Convexity

Standard second-order approximations like the Fisher Information Matrix or the Gauss-Newton matrix often struggle in non-convex regions of the loss surface, where the Hessian can become indefinite. To address this, the authors propose the Positive-Curvature Hessian (PCH).

The PCH uses a "Pos-Eig" function to modify the eigenvalue decomposition of the approximate Hessian. By replacing negative eigenvalues with non-negative values, the method ensures that the update direction always points toward a local minimum, providing stability in non-convex optimization scenarios.

The Pos-Eig function ensures the Hessian approximation remains positive-definite, stabilizing training in non-convex regions.

The EA-CG Framework

The EA-CG method relies on two key technical innovations:

  1. Expectation Approximation: Instead of explicitly constructing and inverting the massive Hessian matrix, the authors use an expectation approximation to compute Hessian-vector products. This reduces the space complexity of certain components from $O(n^2)$ to $O(n)$.
  2. Conjugate Gradient (CG) Solver: The update direction is found using a CG solver, which avoids the need for direct matrix inversion. This is significantly more memory-efficient than Kronecker-factored Inverse (KFI) methods like KFAC.

Furthermore, the method treats weight and bias terms independently during the backpropagation of curvature information, leading to a more precise approximation of the true Hessian compared to existing block-diagonal methods.

Experimental Evaluation

The authors benchmarked EA-CG against SGD and several second-order competitors (Fisher-KFI, GN-KFI, etc.) on the CIFAR-10 and ImageNet-10 datasets.

Wall-Clock Efficiency and Accuracy

A common criticism of second-order methods is that while they require fewer iterations, each iteration takes much longer in "wall-clock time." EA-CG overcomes this hurdle. On CIFAR-10, EA-CG variants (PCH-CG) converged faster in actual seconds and reached higher final test accuracies than both SGD and KFI-based second-order methods.

Training loss (left) and test accuracy (right) vs. wall-clock time on CIFAR-10. The CG-based methods (dotted lines) significantly outperform KFI-based methods (solid lines) in terms of time-to-convergence.

Scalability and Robustness

On the higher-dimensional ImageNet-10 dataset, traditional KFI methods frequently failed due to GPU memory exhaustion. In contrast, the memory-efficient CG approach of EA-CG allowed for successful training. Additionally, in experiments with non-convex loss functions (e.g., sigmoid-based loss), EA-CG remained stable and outperformed SGD, whereas Gauss-Newton methods failed due to the indefiniteness of their curvature matrices.

Conclusion and Future Directions

EA-CG represents a significant step toward making second-order optimization practical for deep learning. By effectively handling non-convexity and drastically reducing memory overhead, it offers a viable alternative to SGD for fully-connected architectures. Future work aims to extend this framework to convolutional neural networks (CNNs), addressing the specific challenges of weight sharing in convolutional layers.

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{chen2019ea,
  author = {Sheng-Wei Chen and Chun-Nan Chou and Edward Y. Chang},
  title = {{EA-CG: An Approximate Second-Order Method for Training Fully-Connected Neural Networks}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.1609/aaai.v33i01.33013337},
}
Figure