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

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?

1 Answer

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.

• Bad communication on my part, I didn't mean to imply that LinearRegression uses gradient descent -- it's just clear that batch gradient descent will (and did) reach the same solution. Thanks for the answer. So the issue in this example was just bad hyperparameters. To the more general point though -- for a convex cost function, do there always exist hyperparameters such that SGD will converge to the minimum? – Denziloe May 17 at 22:46
• I believe that the answer is roughly "yes" (in theory at least, Bottou (1998)). Note that "SGD" refers to a family of methods, so available hyperparameters may vary between implementations. Moreover, convergence may be impractically slow in some cases. – GeoMatt22 May 18 at 4:25
• Regularization note: early stopping is a form of regularization, both in general and in SGDRegressor. This differs from the (unintentional) "early stopping" in your case, by using a holdout set to evaluate overfitting. – GeoMatt22 May 18 at 18:09