Stochastic Gradient Descents Optimizer and Its Variants: Performance of the Optimizers for Multinomial Logistic Models on Large Data Sets by Simulation

The concept of optimization is currently very developed and has been applied to various fields of science, engineering, medicine, computer science, and others. The concept of optimization has given birth to many methods and algorithms that help develop the theory and application of these fields. Some of them are least squares and maximum likelihood methods. In addition, gradient-based algorithms were also born, such as Newton. Especially in the field of statistics, the concept of optimization is very helpful in building models such as linear regression models, binary and multinomial logistic regression, time series, cox regression, and others. These models continue to grow, especially in the field of data science. These models can then be used for prediction and object classification.

One of the popular gradient-based optimization optimizers is SGD [1, 2]. This optimizer has an algorithm that iteratively optimizes a function that is differentiable or subdifferentiable. Thus, SGD will converge even if it is applied to functions that have derivatives or do not have derivatives. SGD works by replacing the actual gradient computed on the entire data set with an estimated gradient computed on a subset of the data set. This gives it an advantage over the use of Newton's method in solving the system of equations generated by maximum likelihood, which is the most widely used method for parameter estimation in statistical modeling. The method is very powerful for smaller data sets [3]. Of course, by using part of the data set to compute the gradient, it provides computational efficiency for large data sets [4, 5]. In its development, SGD [6] has several variants, including SGDM [7], DemonSGDM [8], Adaptive Moment Estimation (Adam) [9]. AdaGrad [10], Root Mean Square Propagation [11].

Evaluating SGD variants for multinomial logistic regression (MLR) on large datasets is a critical area of study due to several specific benefits and implications for practical applications. Some of them are handling high-dimensional data.

Furthermore, the impact of evaluating SGD on decision-making is giving information about accurate and efficient model [12]. Accurate and efficient models can lead to better decision-making in critical areas such as public health, finance, and policy-making. Evaluating SGD variants can enhance the predictive power of MLR models, ultimately benefiting stakeholders.

While there is extensive research on SGD and its variants, there is a lack of focused studies that compare the performance of these optimizers specifically for multinomial logistic regression. Most existing literature tends to concentrate on binary classification or does not adequately address the complexities of MLR [12, 13].

The rest of the paper is organized as follows. In Section 2, we briefly explore the related works of SGD and its most variants. In Section 3, we will explain about the optimization related SGD and its variants. Furthermore, the experiments and comparative results are discussed in Section 4. The last two sections are about the conclusions and future research.

3.1 Multinomial logistic regression

Multinomial logistic regression [24, 25] is a statistical model used to predict categorical outcomes with more than two levels. It generalizes binary logistic regression by modeling multiple classes simultaneously. The mathematical formulation of the multinomial logistic regression model can be expressed as follows:

Assume we have K categories for the dependent variable Y, where Y can take on values 1,2,…, K. Let X be a vector of predictor variables (features). The probability of outcome Y=k for k=1,2, …, K given the predictor variables is modeled using the SoftMax function:

$\begin{gathered}P(Y=k \mid \boldsymbol{X}) =\frac{\exp \left(\beta_{k, 0}+\beta_{k, 1} X_1+\beta_{k, 2} X_2+\cdots+\beta_{k, p} X_p\right)}{\sum_{J=1}^K \exp \left(\beta_{j, 0}+\beta_{j, 1} X_1+\beta_{j, 2} X_2+\cdots+\beta_{j, p} X_p\right)}\end{gathered}$           (1)

where,

β_k,0 is the intercept term for category k,

β_k,j are the coefficients corresponding to predictor variables X_j for category k,

p is the number of predictor variables.

To ensure identifiability, one category (often the last one, K) is chosen as the reference category, and its parameters are set to zero:

$\beta_{K, 0}=0, ~\beta_{K, j}=0$ for $j=1,2, \ldots, p$            (2)

The log-odds of being in category k versus the reference category K is given by:

$\begin{gathered}\log \left(\frac{P(Y=k \mid \boldsymbol{X})}{P(Y=K \mid \boldsymbol{X})}\right) =\beta_{k, 0}+\beta_{k, 1} X_1+\beta_{k, 2} X_2+\cdots+\beta_{k, p} X_p\end{gathered}$             (3)

3.2 Maximum likelihood estimation

The parameters $\beta$ of the model are estimated using the method of maximum likelihood. The likelihood function for the multinomial logistic regression can be expressed as:

$L(\beta)=\prod_{i=1}^n P\left(Y_i \mid \boldsymbol{X}_{\boldsymbol{i}}\right)=\prod_{i=1}^n \prod_{k=1}^K P\left(Y_i=k \mid \boldsymbol{X}_{\boldsymbol{i}}\right)^{I\left(Y_i=k\right)}$               (4)

where, n is the number of observations and I(Y_i=k) is an indicator function that is equal to 1 if Y_i=k and 0 otherwise. The log-likelihood function is therefore:

$\log L(\beta)=\sum_{i=1}^n \sum_{k=1}^K I\left(Y_i=k\right) \log P\left(Y_i=k \mid X_i\right)$                  (5)

3.3 Stratified K-fold Cross Validation (SKCV)

SKCV [26-28] is one of the variants based on k-fold cross validation [29], where folds are created to preserve the target class distribution. SKCV is particularly useful when dealing with data with an unbalanced class distribution. It also ensures that each fold has the same percentage of each class label.

K-fold cross-validation

The dataset is divided into k subsets (folds). The model is trained on k-1 folds and validated on the remaining fold. This process is repeated k times, with each fold serving as the validation set once.

Stratified k-fold cross-validation

Similar to k-fold, but it ensures that each fold has the same proportion of class labels as the entire dataset. This is particularly useful for imbalanced datasets.

SKCV is a powerful tool in the scikit-learn library that enhances the model evaluation process, aids in hyperparameter tuning, and helps in selecting the best model

3.4 Algorithm

The gradient descent algorithm [30-32] is an optimization algorithm commonly used to solve an equation or a system of equations without constraints. Its application is widely found in statistics, research operations, machine learning, deep learning, and others [33]. Furthermore, the algorithm works iteratively to find estimated parameter values as a solution to the steepest descent equation.

Suppose one can compute the gradient of a function ∇f(θ) at any point x. In this case, the simplest method for optimizing f(θ) is the gradient method, in which one constructs an iteration sequence starting from some initial approximation θ₀, one constructs an iteration sequence.

$\theta(t+1)=\theta(t)-\eta \nabla f\left(\theta_t\right)$          (6)

where, the parameter η > 0 is the step size, or what is usually called the learning rate in machine learning.

Gradient descent uses all observation points to compute the gradient at each epoch. This makes it computationally inefficient for large data sets. To overcome this, several variants of gradient descent have been introduced. These variants of GD no longer use all observation points, but only some of them, always referred to as mini-batches. In general, the word stochastic is always associated with the names of these variants. One such variant is SGDM. This SGDM updates the gradient every epoch based on the momentum. In this case, momentum is an extension of the gradient descent optimization algorithm that allows the search to build up inertia in one direction in the search space and to overcome the oscillations of noisy gradients and coast over flat parts of the search space.

Another popular variant is Adam [34]. This optimizer is an algorithm for first-order gradient-based optimization of stochastic objective functions and relies on adaptive estimates of lower-order moments. The optimizer is easy to implement, computationally efficient, has a small memory footprint, is invariant to diagonal rescaling of the gradients, and is well suited for problems with large amounts of data and/or parameters. The method is also suitable for non-stationary targets and problems with very noisy and/or sparse gradients.

Recently, an increasingly popular variant of SGD is DemonSGD [35, 36]. DemonSGD uses linear learning rate decay models that reduce the influence of a gradient on current and future updates. By decaying the momentum parameter, the total contribution of a gradient to all future updates is decayed. In the following subsections, the algorithms used in the experiment are presented in pseudocode.

SGD

1. Parameter: learning rate η, timestep t

a. θ₀=0 or random

b. t=0

2. While θ_t not converged do

$\theta_{t+1}=\theta_t-\eta \nabla_{\theta_t} f\left(\theta_t\right)$

3. End while

SGDM

1. Parameter:

a. learning rate η

b. momentum β

c. timestep t

d. θ₀=0 or random

2. While θ_t not converged do

$\beta_t=\beta_{t-1} v_{t-1}+\left(1-\beta_{t-1}\right) \nabla_\theta f\left(\theta_{t-1}\right) \theta_{t+1}=\theta_t-\eta \beta_t$

3. End while

Adam

1. Parameters:

a. $\eta$: learning rate

b. $\beta_1, \beta_2 \in[0,1)$: Exponential decay rates for the moment estimates

c. $f(\theta)$: Stochastic objective function

d. $\theta_0$: Initial parameter vector

e. $m_0=0$: Initial first moment vector

f. $v_0=0$: Initial second moment vector

g. $t=0$: initial timestep

2. While θ_t not converged do

a. $g_t \leftarrow \nabla_\theta f_t\left(\theta_{t-1}\right)$

b. $m_t \leftarrow \beta_1 \cdot m_{t-1}+\left(1-\beta_1\right) \cdot g_t$

c. $v_t \leftarrow \beta_2 \cdot v_{t-1}+\left(1-\beta_2\right) \cdot g_t^2$

d. $\widehat{m_t} \leftarrow \frac{m_t}{1-\beta_1^t}$

e. $\widehat{v_t} \leftarrow \frac{v_t}{1-\beta_2^t}$

f. $\theta_t \leftarrow \theta_{t-1}-\eta \frac{\widehat{m_t}}{\sqrt{\widehat{v_t}+\epsilon}}$

3. End while

Demon SGDM

1. Parameter:

a. number of iterations T

b. learning rate η

c. $\beta_{\text {init }}$ (Initial Momentum),

d. $\beta_t$ momentum

e. $v_0=\theta_0=0$ or random

2. While θ_t not converged do

a. $\beta_t=\frac{\beta_{\text {init }} \cdot\left(1-\frac{t}{T}\right)}{\left(1-\beta_{\text {init }}\right)+\beta_{\text {init }}\left(1-\frac{t}{T}\right)}$

b. $\theta_{t+1}=\theta_t-\eta g_t+\beta_t v_t$

c. $v_{t+1}=\beta_t v_t-\eta g_t$

3. End while

3.5 Performance evaluation

Three metrics, loss function, accuracy, and ROC-AUC, are used to evaluate SGD variants in multinomial logistic regression. It is grounded in their relevance to the objectives of the study and their established significance in the literature. These metrics collectively provide a comprehensive evaluation of model performance, addressing both the optimization process and the practical implications of classification accuracy [37]. By utilizing these metrics, the study can effectively assess the strengths and weaknesses of different SGD variants [38, 39].

In general, all optimizers are capable of achieving convergence for both simulation datasets and the Red-Wine dataset. The following Table 2 shows the values of the learning rate, first momentum and second momentum for each dataset used in the simulations and real-world. Next, Table 3 presents the average run times of the teams (s), the average number of epochs, and the ROC-AUC scores. Additionally, Figures 1 and 2 display the accuracy interval values for each optimizer and dataset used. The ROC-AUC score and accuracy intervals will be used as the basis for assessing the performance of each optimizer.

ping_mu_jie_tu_2.jpg

Figure 2. Model performance for red-wine quality

For 5000 observations, the models generally performed best, with test accuracies often above 97%. Performance decreased for 10000 and 20000 observations, with accuracies dropping to around 87% and 86% respectively. There's no clear trend in performance as the number of variables increases from 30 to 50. For 5000 observations, SGDM and DemonSGDM generally outperformed SGD and Adam. For 10000 and 20000 observations, the differences between optimizers were less pronounced. Adam often had slightly worse performance compared to the other optimizers, especially for 5000 observations.

All optimizers performed similarly on this real-world dataset. Test accuracies were much lower (around 60%) compared to the generated dataset, indicating this is a more challenging classification task. Adam slightly outperformed the other optimizers, with the highest test accuracy of 60.35%. The log-loss values were significantly higher for this dataset compared to the generated data. Furthermore, Figure 1 shows a series of plots comparing the performance of different optimization optimizers (SGD, SGDM, DemonSGDM, and Adam) across various datasets and conditions. The plots are organized in a 3×3 grid, with each row representing a different number of observations (5000, 10000, 20000) and each column representing a different number of features (30, 40, 50).

Each individual plot displays the accuracy of the four optimization algorithms for a specific combination of observations and features. The optimizers are listed vertically, and horizontal lines with dots represent the accuracy range and mean for each algorithm. The relative performance of the algorithms seems fairly consistent across different numbers of observations and features. In most cases, the order of performance from best to worst appears to be: DemonSGDM ≈ SGDM > SGD > Adam. The accuracy values generally fall between 0.86 and 0.98, indicating high performance across all conditions. There seems to be slightly more variation in results for the 5000 observation datasets compared to the 10000 and 20000 observation datasets. The number of features (30, 40, 50) doesn't seem to dramatically change the relative performance of the optimizers. Adam consistently shows the widest range of accuracy values and often performs slightly worse than the other optimizers. These two algorithms frequently have very similar performance, often overlapping in their accuracy ranges.

Figure 2 displays the performance comparison of four different optimization algorithms (SGD, SGDM, DemonSGDM, and ADAM) on a wine dataset. SGD shows a wide range of performance, with accuracy varying from about 0.58 to 0.61. SGDM has a narrower performance range, clustered around 0.59 to 0.60. DemonSGDM displays the widest range of performance, spanning from about 0.50 to 0.60. ADAM shows the most consistent performance with the smallest range, achieving an accuracy of about 0.60. ADAM seems to perform the best with the highest and most consistent accuracy has decent performance but with more variability than SGDM and ADAM. DemonSGDM shows the most unpredictable performance, with a very wide range of possible accuracies.

In general, the performance differences between these algorithms on this wine dataset are relatively small, with all achieving accuracies between 50% and 60%. This suggests that the classification task for this wine dataset might be challenging, as none of the algorithms achieve very high accuracy.

In conclusion, the findings indicate that while all optimizers can achieve convergence, their effectiveness varies significantly across datasets and task complexities. SGDM and DemonSGDM stand out in simulations, while Adam garners a slight edge in challenging real-world applications, albeit with modest performance. The varying results highlight the need for careful optimizer selection based on dataset characteristics and required performance thresholds particularly in predicting outcomes, where subtle distinctions in methodology can influence results substantially. Further exploration into hybrid approaches or alternative optimization techniques may yield enhanced performance, particularly for complex, real-world datasets like the wine classification case.