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 EA-CG Framework
The EA-CG method relies on two key technical innovations:
- 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)$.
- 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.
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