Here's a toy dataset.
import numpy as np
from matplotlib import pyplot as plt
from sklearn.preprocessing import PolynomialFeatures, StandardScaler
from sklearn.linear_model import LinearRegression, SGDRegressor
x = np.array([0, 9, 10])
y = np.array([0, 1, -1])
plt.scatter(x, y)
Of course, a two degree polynomial will perfectly (over)fit this data, illustrated here via the closed form solution of least squares. Batch gradient descent minimises the same cost function and so will find the same solution as this.
polynomial_features = PolynomialFeatures(degree=2, include_bias=False)
X = polynomial_features.fit_transform(x.reshape(-1, 1))
scaler = StandardScaler()
X = scaler.fit_transform(X)
print(X)
[[-1.4083737 -1.39140234]
[ 0.59299945 0.47661296]
[ 0.81537425 0.91478938]]
lr = LinearRegression()
lr.fit(X, y)
x_plot = np.linspace(0, 10, 101)
X_plot = scaler.transform(polynomial_features.transform(x_plot.reshape(-1, 1)))
plt.scatter(x, y)
plt.plot(x_plot, lr.predict(X_plot), color="red")
plt.show()
However, I noticed that when I try to use stochastic gradient descent (SGD) to do the same thing, regardless of the choice of hyperparameters and the length of training, I get a model like this:
sgd = SGDRegressor(alpha=0)
sgd.fit(X, y)
plt.scatter(x, y)
plt.plot(x_plot, sgd.predict(X_plot), color="red")
plt.show()
This looks like a less overfit model. I found similar results with larger datasets and higher degree polynomials.
I was wondering: is it even possible for SGD to converge to the first perfect model? SGD only considers one sample at a time. And at each step, SGD does not directly move in the direction of the minimum of the "true" cost function, as batch gradient descent does, but rather moves in the direction of the minimum of the cost function for the particular sample, which is a noisy estimate of the true minimum. This causes SGD to "bounce around" the parameter space and around the true optimum. This, and these results, make me think that SGD is perhaps unable to learn more complex models -- is that so? Put another way, is its hypothesis space strictly smaller than that of batch gradient descent, even for a simple example like linear regression? Is SGD a form of regularisation?