Bolstering Stochastic Gradient Descent with Model Building

S. Ilker Birbil, Ozgur Martin, Gönenç Onay, Figen Öztoprak

Abstract

Training deep neural networks typically relies on Stochastic Gradient Descent (SGD) or its variants, which are notoriously sensitive to hyperparameters like the learning rate. We introduce Stochastic Model Building (SMB), a novel optimization algorithm that enhances SGD by utilizing local quadratic models to adaptively adjust both step size and search direction. SMB achieves faster convergence and superior generalization across diverse deep learning tasks while demonstrating significant robustness to initial learning rate choices. By leveraging local curvature without the computational overhead of traditional second-order methods, SMB offers a more efficient path to training high-performance models.

Introduction

The performance of deep learning models is heavily dependent on the optimization strategy employed. While SGD is the standard, finding the optimal learning rate and decay schedule often requires exhaustive and energy-intensive grid searches. Adaptive methods like Adam and line-search strategies mitigate some of these issues but often fail to adjust the search direction or introduce significant memory overhead. This paper addresses these limitations by proposing a method that uses local curvature to improve the optimization trajectory without the complexity of classic second-order techniques.

Stochastic Model Building (SMB)

The core contribution is the SMB algorithm, which integrates local quadratic modeling into the stochastic optimization process. Unlike standard gradient descent, SMB performs a "trial" step. If this step fails to satisfy a sufficient decrease condition (the Armijo condition), the algorithm constructs a local quadratic model using gradient information from both the current and trial points.

Key features of SMB include:

  • Local Quadratic Modeling: Estimates local curvature to refine the optimization path.
  • Group-wise Adaptation: Parameters are organized into groups (e.g., layers), allowing for independent adaptive step lengths across the network.
  • Trust Region Constraint: Ensures the updated step remains within a region where the local model is accurate.
  • SMBi Variant: A statistically rigorous version that uses independent data batches for model building to ensure convergence.
An illustration of the SMB iteration process. When a trial point $x_k^t$ is rejected, a local model is constructed to determine a more effective iterate $x_{k+1}$.

Experimental Evaluation

The authors evaluated SMB against popular optimizers, including Adam and SLS (Stochastic Line Search), on datasets such as MNIST, CIFAR-10, and CIFAR-100 using architectures like ResNet-34 and DenseNet-121.

Performance and Convergence

On the MNIST benchmark using a Multi-Layer Perceptron (MLP), SMB and its variant SMBi demonstrated superior performance. As shown in the figures below, SMB achieves a faster decay in training loss and reaches higher test accuracy compared to baseline optimizers when measured against wall-clock time.

Performance comparison on MNIST. SMB (dark blue) and SMBi (light blue) exhibit faster training loss decay and superior test accuracy relative to Adam and SLS.

Robustness and Generalization

A critical advantage of SMB is its robustness to hyperparameter tuning. Experiments on CIFAR-100 with DenseNet-121 showed that SMB consistently outperformed other optimizers in training error and reached the highest test accuracy. Notably, the authors report that SMB's performance remains stable across a wide range of initial learning rates, whereas standard SGD's performance is highly volatile. This suggests that SMB finds more robust, "flatter" minima that generalize better to unseen data.

Discussion and Limitations

While SMB offers significant improvements, there are areas for future development. Currently, the algorithm lacks an internal mechanism for automatic learning rate decay over long training cycles. Additionally, while SMBi has a rigorous convergence analysis, a full theoretical proof for the more efficient standard SMB algorithm is still needed. Finally, although the computational cost is offset by faster convergence, the additional gradient evaluations required during model building present an opportunity for further optimization.

Conclusion

Stochastic Model Building represents a significant step forward in making deep learning optimization more robust and efficient. By adaptively adjusting both the step size and direction through local quadratic models, SMB reduces the need for extensive hyperparameter tuning while achieving state-of-the-art performance across various tasks.

Summary updated

Abstract

Stochastic gradient descent method and its variants constitute the core optimization algorithms that achieve good convergence rates for solving machine learning problems. These rates are obtained especially when these algorithms are fine-tuned for the application at hand. Although this tuning process can require large computational costs, recent work has shown that these costs can be reduced by line search methods that iteratively adjust the stepsize. We propose an alternative approach to stochastic line search by using a new algorithm based on forward step model building. This model building step incorporates second-order information that allows adjusting not only the stepsize but also the search direction. Noting that deep learning model parameters come in groups (layers of tensors), our method builds its model and calculates a new step for each parameter group. This novel diagonalization approach makes the selected step lengths adaptive. We provide convergence rate analysis, and experimentally show that the proposed algorithm achieves faster convergence and better generalization in well-known test problems. More precisely, SMB requires less tuning, and shows comparable performance to other adaptive methods.
BibTeX
@inproceedings{birbil2024bolstering,
  author = {S. Ilker Birbil and Ozgur Martin and Gönenç Onay and Figen Öztoprak},
  title = {{Bolstering Stochastic Gradient Descent with Model Building}},
  booktitle = {Top},
  year = {2024},
  doi = {10.1007/s11750-024-00673-z},
}
Figure