Is stochastic gradient descent unable to learn more complex models which batch gradient descent can learn?

Question

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?

Answer 1

Your example is not showing the difference between batch vs. stochastic gradient descent. Rather, it is more the difference between direct vs. iterative solution of the least squares model. See here for more details.

In general, iterative methods can require many iterations to converge, and the returned solution will depend on the tolerance requested. For your example, I believe the same problem would occur for any gradient descent.

In this particular case, using the following hyperparameters

sgd_opts = dict(alpha=0, eta0=5e-1, tol=1e-8, max_iter=10**4)
sgd = SGDRegressor(**sgd_opts).fit(X, y)

will give a reasonable solution:

Note that LinearRegression uses a (direct) SVD solution. It does not use batch gradient descent.