Software Components in Deep Learning

Optimization Algorithms

Based on a collection of input parameters or variables, an optimization algorithm is a mathematical approach used to discover the optimum solution or optimal value of a function. Optimization algorithms are used in machine learning and deep learning to train models by altering the model's weights and biases to minimize the loss function.

Goal

Optimization algorithms aim to discover the best values for the model's parameters so that the model can accurately forecast the target variable for new input data. Optimization strategies lower the loss function, which evaluates the difference between projected and actual output values, by iteratively adjusting the model's parameters.

Optimization algorithms include gradient descent, stochastic gradient descent, momentum-based optimization, and adaptive learning rate optimization. These techniques update the model's parameters differently, each with pros and cons.

The optimization algorithm used is determined by the situation at hand, the size of the data, the complexity of the model, and other considerations. Optimization algorithms are important to the success of machine learning and deep learning models, and researchers are constantly looking for novel optimization approaches to increase their performance.

Different Types of Optimization Algorithms

Deep neural network training requires optimization strategies. Here are some of the most often-used deep learning optimization algorithms:

1. Stochastic Gradient Descent
2. Gradient Descent
3. Mini Batch Gradient Descent
4. Momentum
5. AdaGrad
6. RMSprop
7. Adam
8. AdaGradDelta
9. Nadam
10. AdamW

Stochastic Gradient Descent

After computing the gradient of the loss function with respect to the weights for each individual sample in the training data, the weights of the model are updated in SGD. Unlike batch gradient descent, where the weights are updated after computing the gradient of the loss function with respect to the weights for the full training dataset, this is not the case.

Advantages:

• SGD is more computationally efficient than batch gradient descent since it updates the weights after computing the gradient for each individual sample.

• More suitable for huge datasets: SGD can be much faster for huge datasets because it only needs a subset of the data to update the weights at each iteration.

• Aids in avoiding local minima: Stochasticity in SGD updates can help the algorithm avoid local minima and find superior global minima.

• Can be used in online Learning: SGD can be used to update model weights on each new data point in online learning scenarios where fresh data is constantly arriving. 

Disadvantages:

• The updates introduced by SGD have a significant variance because of the stochastic gradients computed for each individual sample. This can lead to instabilities and a sluggish convergence.

• Setting the learning rate: Because it affects the convergence rate and the stability of the optimization, setting the learning rate, which determines the size of the weight updates, can be difficult for SGD.

• More iterations may be required to achieve convergence: Because of the high variance, SGD may require more iterations to find the best solution than batch gradient descent.
• SGD can become stuck in saddle spots in high-dimensional spaces, which are places with relatively flat surfaces and several minima and maxima.

Gradient Descent

It is a form of optimization method used to train models in machine learning and deep learning by minimizing the loss function. After computing the gradient of the loss function with respect to the weights for the complete training dataset, the weights of the model are updated in GD. This means that the gradient is calculated by adding the contributions of all training samples, and the weight update is done in a single step using this aggregated gradient.

Implementation

Below is the implementation of the Gradient Descent algorithm used to find the cost function of the minimum of the two-dimensional one with the 3D plot visualization of the optimization path. 

Source Code

# Import the Required Libraries
import numpy as np
import matplotlib.pyplot as plt
from mpl_toolkits.mplot3d import Axes3D

# Define the cost function
def cost_function(x):
    return (x[0]**2 + x[1]**2)/2

# Define the gradient of the cost function
def cost_gradient(x):
    return np.array([x[0], x[1]])

# Set the initial parameters and the learning rate
x = np.array([2.0, 2.0])
learning_rate = 0.1

# Set the number of iterations to perform
num_iterations = 10

# Initialize lists to store the parameters and costs at each iteration
x_list = [x]
cost_list = [cost_function(x)]

# Perform the gradient descent algorithm
for i in range(num_iterations):
    gradient = cost_gradient(x)
    x = x - learning_rate * gradient
    cost = cost_function(x)
    x_list.append(x)
    cost_list.append(cost)
    
# Plot the cost function surface
fig = plt.figure(figsize=(8,6))
ax = fig.add_subplot(111, projection='3d')
x1 = np.linspace(-5, 5, 100)
x2 = np.linspace(-5, 5, 100)
X1, X2 = np.meshgrid(x1, x2)
Y = cost_function([X1, X2])
ax.plot_surface(X1, X2, Y, cmap='viridis')

# Plot the optimization path
x_list = np.array(x_list)
cost_list = np.array(cost_list)
ax.plot(x_list[:,0], x_list[:,1], cost_list, color='red', marker='o')
# Set the axis labels and title
ax.set_xlabel('Parameter 1')
ax.set_ylabel('Parameter 2')
ax.set_zlabel('Cost')
ax.set_title('Gradient Descent Optimization')
plt.show()

Obtained Output:




Description:
The necessary libraries are imported for doing the numerical and visualization of the algorithm.
Here, we define the cost function which is the sum of squares of the input variables x[0] and x[1] which creates the simple bowel-shaped cost function. 
The gradient of the cost function is alternatively defined as the vector containing the cost function's partial derivatives with respect to x[0] and x[1].
The parameters' initial values are [2.0, 2.0], and the learning rate is set to 0.1. The number of iterations is limited to ten. At each cycle, two empty lists, x_list and cost_list, are initialized to store the arguments and costs. 
For the specified number of iterations the gradient descent algorithm was performed in a loops. 
Using the current values of the parameters the gradient cost function was calculated in the each iteration. 
The cost function may be calculated using the new parameter values and then adding them tot he cost list of the algorithm. 
Following the completion of the optimization, the cost function surface is visualized in 3D using the matplotlib tool. The optimization path is then depicted as a red line with markers, with each marker representing the parameter values at each iteration. 
After that, the axis labels and title are specified, and the plot is presented with the show() method.

Advantages:

• Guaranteed convergence: GD assures convergence to the loss function's local minimum.

• Efficient for small datasets: Because the gradient can be calculated fast over the full dataset, GD can be efficient for small datasets. 

• Convergence behavior is well understood: GD has a well-understood convergence behavior that can be used as a baseline for comparing different optimization methods.

Disadvantages:

• Computationally expensive for large datasets: Because the gradient must be computed for all training samples at each iteration, GD can be computationally expensive for large datasets.

• GD is prone to becoming caught in local minima and may fail to locate the global minimum of the loss function.

• Tuning of learning rate is required: The learning rate, which governs the magnitude of the weight updates, must be carefully calibrated to achieve GD convergence.

Mini Batch Gradient Descent

Mini-Batch Gradient Descent is a variant of the conventional Gradient Descent optimization technique used in machine learning and deep learning. Instead of computing the gradient of the loss function across the whole training dataset (as in batch gradient descent), mini-batch gradient descent computes the gradient on smaller random subsets of the data called mini-batches.

The mini-batch size is often designed to be a small percentage of the training data, ranging from 10 to 1000 samples depending on the size of the dataset and available processing capabilities. The size of the mini-batch is a trade-off between variance (i.e., noise generated by utilizing only a subset of the data to compute the gradient) and processing performance.

At each iteration of the method, a mini-batch of training data is randomly sampled, and the gradient of the loss function is determined based on that mini-batch. The model's weights are then modified using the estimated gradient, and the procedure is repeated until convergence is reached. Overall, mini-batch gradient descent is a popular deep-learning optimization technique due to its ability to converge rapidly and efficiently on big datasets.

Advantages:

• Computational efficiency: Because it uses less memory and computation to calculate the gradient on smaller subsets of data, mini-batch gradient descent is more computationally efficient than batch gradient descent.

• Mini-batch gradient descent can converge quicker than batch gradient descent since it computes the gradient on smaller mini-batches of data.

• Mini-batch gradient descent is less likely to get stuck in local minima and can avoid undesirable solutions by incorporating stochasticity into the updates.

• Better generalization: Because the weights are updated more frequently, mini-batch gradient descent is less likely to overfit the training data.

Disadvantages:

• To ensure that the algorithm performs well, the mini-batch size and learning rate must be carefully set.

• Non-deterministic updates: Mini-batch gradient descent introduces randomness into the updates, which can make reproducing results challenging.

• Sensitive to starting conditions: The convergence and performance of mini-batch gradient descent can be affected by initial conditions such as initial weight selection.

Momentum

Momentum is a technique used to accelerate convergence and increase the stability of gradient-based optimization algorithms such as stochastic gradient descent (SGD) and mini-batch gradient descent. During each iteration, it adds a fraction of the previous update to the current update of the weights.

The momentum term is analogous to a velocity term, with the gradient understood as an acceleration in weight space. The momentum term aggregates the gradient's direction and speed, smoothing down the oscillations and noise in the updates.

The momentum term is commonly represented by the hyperparameter beta (), which regulates the weight of earlier updates. 

The momentum algorithm's update equation is as follows:

v(t) = βv(t-1) + (1-β)∇J(w(t)) 
w(t+1) = w(t) - αv(t)

where v(t) represents the momentum at time t, J(w(t)) represents the gradient of the loss function at time t, w(t) represents the weights at time t, is the learning rate, and is the momentum coefficient.

Advantages:

• Faster convergence: Momentum aids the optimization method in achieving a faster convergence towards the minimum of the loss function by accelerating updates in the direction of the preceding gradients.

• Improved stability: By smoothing out the updates and preventing the algorithm from being stuck in local minima, the momentum term can reduce oscillations and noise in the optimization process.

• Momentum can be especially useful when the gradients are noisy or sparse, as it allows the algorithm to proceed efficiently toward the minimum of the loss function despite the noise.

• Improved generalization: By minimizing oscillations and noise during the optimization phase, momentum can assist the model in generalizing to previously unknown data.

Disadvantages:

• Tuning the momentum coefficient (beta): To ensure that the algorithm performs well, the momentum coefficient (beta) must be carefully calibrated. An incorrect beta value can cause the optimization process to stall or become unstable.

• Sensitive to starting conditions: The performance of momentum can be affected by early conditions such as the initial weights and learning rate.

• Overshooting danger: The momentum term can lead the optimization method to exceed the minimum of the loss function and fluctuate around it in some instances.

AdGrad 

AdaGrad is a deep learning optimization technique that adjusts the learning rate of each parameter based on previous gradient information gathered during the optimization process. It is a gradient descent version in which the learning rate of each parameter is scaled according to the inverse square root of the sum of the squares of the previous gradients.

AdaGrad's concept is to lower the learning rate for frequently updated parameters while increasing it for infrequently updated values. The assumption is that if a parameter has been modified frequently in the past, it is likely to be close to its optimum value, and hence should be updated more slowly. In contrast, if a parameter has been updated seldom, it is likely to be significantly out of date.

The updated formula is as follows:

g(t) = ∇J(w(t))
r(t) = r(t-1) + g(t)⊙g(t)
w(t+1) = w(t) - α⊙g(t) / (sqrt(r(t)) + epsilon)

• g(t) - Gradient of the loss function
• r(t) - Sum of the squares of the gradient up to time t.
• w(t) - Weight at time t.
• α - Learning Rate
• epsilon is a constant

Advantages:

• AdaGrad changes the learning rate of each parameter based on past gradient information, which can help to accelerate convergence and increase optimization process stability.

• Manual tuning is not required: AdaGrad does not require manual tweaking of the learning rate hyperparameter, which can be time-consuming and difficult in practice.

• AdaGrad is robust to sparse gradients because it boosts the learning rate for infrequently changed parameters, which can aid in overcoming the sparsity problem.

Disadvantages:

• Learning rate decay: The learning rate of AdaGrad can decay too quickly, especially for frequently updated parameters, which can slow down convergence or cause the algorithm to get stuck in local minima.

• Accumulation of gradients: AdaGrad accumulates the squares of the gradients over time, which can cause numerical stability issues and lead to slow convergence or divergence.

• Memory requirements: AdaGrad requires storing the historical gradients for each parameter, which can be memory-intensive for large models with many parameters.

Conclusion

Each optimization technique has advantages and disadvantages, and the approach chosen is determined by the individual problem being handled as well as the features of the data and model. Furthermore, various versions of these algorithms have been presented to address their shortcomings and increase their performance.

References

[1] https://www.e2enetworks.com/blog/optimization-in-deep-learning-learn-with-examples

[2] http://www.d2l.ai/chapter_optimization/