Implementing simple gradient descent, a momentum method, and stochastic gradient descent; comparing their performance for training logistic regression.
The Python source file implements three types of logistic regression with gradient descent:
Batch gradient descent, updating the gradient all at once;
Stochastic (minibatch) gradient descent, updating the gradient on random subsets;
Stochastic (minibatch) gradient descent with momentum method.
Note on terminology
I checked Google for a reasonable batch_size for this blog post’s “stochastic gradient descent”, and was unable to find one.
From this Towards Data Science blog post, it seems that “stochastic gradient descent” refers to an online method that checks one data point at a time. A more common name for the method implemented in LR.fit_stochastic() is “minibatch” gradient descent, which strikes a balance between stochastic (one at a time) and “batch” (LR.fit()) gradient descent (all the data points, all at once).
Batch gradient descent
With terminology out of the way, let us first prepare the data.
We generate data points with 2 features and 2 labels that are not linearly separable, as seen below:
# Dataimport numpy as npfrom logreg import LogisticRegressionfrom sklearn.datasets import make_blobsfrom matplotlib import pyplot as pltfrom matplotlib import font_managerfont_manager.fontManager.addfont("C:\Windows\Fonts\FiraSans-Regular.ttf")plt.rcParams["font.family"] ="Fira Sans"np.seterr(all='ignore')np.random.seed(283)# make the datap_features =3X, y = make_blobs( n_samples=500, n_features=p_features -1, centers=[(-1, -1), (1, 1)])fig = plt.scatter(X[:, 0], X[:, 1], c=y)xlab = plt.xlabel("Feature 1")ylab = plt.ylabel("Feature 2")
We can then fit our logistic regression with batch gradient descent as follows:
We observe a resonable splitting line on the left, and a smoothly decreasing loss to the right.
Since we also implemented stochastic “minibatch” gradient descent, with and without momentum, we can plot the loss curves together as follows: (Code adapted from blog post instructions)
We can see different converging speeds for the three types of gradient descent. Here, stochastic “minibatch” gradient descent converges the fastest, then “minibatch” with momentum (slightly slower), then standard gradient descent.
Experiments
Having compared the different ways of gradient descent, we now investigate the hyperparameters. Namely:
Learning rate \alpha
Batch size
Momentum vs. regular “minibatch” stochastic gradient descent
Data
We will generate another dataset with 10 features, visualizing the first two:
# make the datap_features =11X, y = make_blobs( n_samples=500, n_features=p_features -1, centers=[(-1, -1), (1, 1)])fig = plt.scatter(X[:, 0], X[:, 1], c=y)xlab = plt.xlabel("Feature 1")ylab = plt.ylabel("Feature 2")
Learning rate
The learning rate determines how much we move along the gradient.
As such, when the learning rate is too large, gradient descent will exceed the optimal minimum; when it is too small, gradient descent will take longer to reach the optimal minimum.
With three different learning rates, we can see a difference in how training loss progressed over time:
Reasonably small, alpha = 0.05: loss decreased quickly, converging in less than 100 iterations.
Too small, alpha = 0.0005: loss decreased more smoothly but slowly, and failed to converge in 1000 iterations.
Too large, alpha = 1: loss jumped up and down frequently, although it managed to converge in less than 100 iterations.
This shows that indeed, we want a reasonably small learning rate. Small enough to converge, but not too small that converging becomes too slow.
Batch size
We look at another hyperparameter, the batch size.
In our “minibatch” gradient descent, we look at each “batch” separately. The size of these batches, therefore, might determine the speed of gradient descent.
Using our reasonable learning rate of alpha = 0.05:
from time import perf_counterbatch_sizes = [2, 10, 50, 100, 200, 500]for batch_size in batch_sizes: LR = LogisticRegression() start = perf_counter() LR.fit_stochastic( X, y, max_epochs=1000, momentum=False, batch_size=batch_size, alpha=0.05 ) end = perf_counter() num_steps =len(LR.loss_history) plt.plot( np.arange(num_steps) +1, LR.loss_history, label=f"batch size = {batch_size}, {(end - start)*1000:.2f}ms", alpha=0.7 )plt.loglog()legend = plt.legend()xlab = plt.xlabel("Epoch")ylab = plt.ylabel("Loss")
Here, using otherwise identical hyperparameters, we observe that batch size does affect convergence speed and runtime.
Although a batch size of 2 converged the fastest, the program runtime was longer because of more calculations per loop.
A batch size of 50 converged rather quickly, and had a decently short runtime as well.
Larger batch sizes took longer to converge. At a batch size of 500, this is effectively regular gradient descent, the one callable with LR.fit().
In conclusion, a reasonable batch size would make gradient descent converge faster, and improve the program runtime as well.
Momentum
for momentum in [False, True]: LR = LogisticRegression() start = perf_counter() LR.fit_stochastic( X, y, max_epochs=100, momentum=momentum, batch_size=20, alpha=0.5 ) end = perf_counter() num_steps =len(LR.loss_history) plt.plot( np.arange(num_steps) +1, LR.loss_history, label=f"momentum {momentum}, {(end - start)*1000:.2f}ms", alpha=0.7 )plt.loglog()legend = plt.legend()xlab = plt.xlabel("Epoch")ylab = plt.ylabel("Loss")
With a large-enough learning rate of 0.5, we observe the power of the momentum method in gradient descent.
When using the momentum method, “minibatch” stochastic gradient descent converged in around 10 iterations. Not using the momentum method resulted in a much slower convergence.
