Abstract
In this paper, we introduce a structured stochastic quasi-Newton (S2QN) framework for minimizing finite summations of nonconvex functions, a common problem in large-scale machine learning. The core challenge in second-order optimization is finding a computationally cheap way to incorporate local curvature information. We propose splitting the Hessian matrix into a "cheap" base part and an "expensive" refinement part, approximating the latter via quasi-Newton updates. By exploiting low-rank and Kronecker-product structures, our method remains computationally affordable while capturing richer curvature than standard approximations. Numerical results on logistic regression, deep autoencoders, and convolutional neural networks demonstrate that S2QN is highly competitive with state-of-the-art methods like KFAC and Adam.
Introduction
Training modern machine learning models involves solving massive finite-sum optimization problems. While first-order methods like Stochastic Gradient Descent (SGD) and Adam are industry standards due to their low per-iteration cost, they only utilize gradient information. This often leads to slow convergence on complex, non-convex loss landscapes where the "curvature" changes rapidly.
Second-order methods, such as Newton’s method, use the Hessian matrix to take more direct paths to the optimum. However, for models with millions of parameters, calculating and inverting the full Hessian is computationally prohibitive. Existing approximations, such as the Kronecker-factored Approximate Curvature (KFAC), often discard significant curvature information to maintain efficiency. This paper addresses the gap: how can we incorporate more of that "missing" curvature information without breaking the computational budget?
The S2QN Framework
The core innovation is the Structured Stochastic Quasi-Newton (S2QN) framework. The authors observe that the Hessian $\nabla^2 \Psi(\theta)$ can often be decomposed into two parts: $$\nabla^2 \Psi(\theta) = H(\theta) + \Pi(\theta)$$
- $H( heta)$ (The Base): A "cheap" part that is easily computed or approximated, such as a subsampled Hessian or a Gauss-Newton matrix.
- $\Pi(\theta)$ (The Refinement): The complex or expensive part that is typically ignored by other methods.
S2QN uses a standard approximation for the base $H(\theta)$ and then employs a limited-memory BFGS (L-BFGS) update to "fill in the blanks" for $\Pi(\theta)$. To maintain efficiency, the framework utilizes:
- Low-Rank Structures: Applying the Sherman-Morrison-Woodbury formula to invert the combined matrix rapidly.
- Kronecker-Product Properties: For deep learning layers, the refinement matrix is structured as a Kronecker product of two smaller matrices, making it feasible for high-dimensional convolutional and fully-connected layers.
- Stochastic Secant Conditions: Traditional quasi-Newton mathematics are adapted to function reliably with noisy, batched data samples.
Experimental Results
Deep Autoencoders
The authors evaluated variants of the proposed method (e.g., SKQN) on deep autoencoder tasks using the MNIST, CURVES, and FACES datasets. As shown in the results, the structured quasi-Newton approach consistently achieves lower training and testing losses compared to both first-order optimizers (Adam) and second-order competitors (KFAC).
Convolutional Neural Networks (CNNs)
On more complex architectures like ResNet-18 trained on the CIFAR-10 dataset, S2QN methods demonstrate superior convergence speed and final generalization. The refinement step adds negligible computational overhead compared to the significant gains in training efficiency and final testing accuracy.
Key Insights
- Curvature Refinement: Most second-order approximations simply ignore the "complex" part of the Hessian. S2QN demonstrates that even a rough quasi-Newton approximation of that missing piece can significantly accelerate training.
- Structural Exploitation: By proving that the block Hessian of a convolutional layer maintains a Kronecker-product structure under certain assumptions, the authors enabled sophisticated quasi-Newton refinements for CNNs without a massive memory footprint.
- Adaptive Stability: The method includes an adaptive regularization strategy based on the norm of the stochastic gradient, ensuring stability even in highly non-convex regions.
Conclusion
S2QN provides a robust framework for incorporating richer curvature information into stochastic optimization. By strategically decomposing the Hessian and exploiting the underlying structure of neural network layers, it achieves faster convergence and better generalization than existing state-of-the-art methods. Future work includes integrating these methods into large-scale industrial frameworks like MindSpore to support broader AI applications.
Summary updated