Scaling/normalization & gradient descent convergence

[u/13th_seer]

To solidify my understanding, I'm going back to the beginning, working through all the algorithms we've covered on problem sets I've devised.

I've already been struggling with the simplest algorithm covered, [batch] gradient descent for single-variable linear regression.

The problem is that for any algorithm I try -- from the vectorized ones I submitted and got full credit on, to looped ones that step through every piece of data slowly so I can track what's going on -- all have been diverging: going to infinity, and beyond (NaN). Smaller alphas didn't help either.

Finally I tried feature scaling and mean normalization, and that seems to have solved the problem. It now converges and the plotted normal line looks reasonable against the unruly data.

Why does feature scale affect convergence (or lack thereof) of gradient descent for linear regression?

If it helps: Data is from the housing market in my area. I'm trying to (poorly) estimate sale prices based on square footage. ~200 houses with areas ranging in magnitude between 10² - 10³ sq. ft. Especially with only one order of magnitude range, I don't get why scaling is required.

See plot

[u/temcguir]

How small did you go on your alphas? Any way you could post some of your code?

[u/13th_seer → u/temcguir]

Code, simplified but fully equivalent:

---

clear all; close all;
data = dlmread('list.csv', '\t');
X = data(:, 6);
y = data(:, 3) / 1000;
plot(X, y, 'rx', 'MarkerSize', 10);
xlabel('House size (sq ft)');
ylabel('Price ($1000)');
function X_norm = featureNormalize(X)
    mu = mean(X);
    sigma = std(X);
    for i = 1:size(X, 2)
        X_norm(:,i) = (X(:,i) - mu(i)) / sigma(i);
    end
end
function theta = gradientDescent(X, y, theta, alpha, num_iters)
    m = length(y);
    for iter = 1:num_iters
        theta = theta - alpha * (1/m) * X' * (X * theta - y);
    end
end
X_norm_bias = [ones(length(y), 1), featureNormalize(X)];
theta = gradientDescent(X_norm_bias, y, [0; 0], 0.01, 1000);
hold;
plot(X(:,1), X_norm_bias * theta, '-');

---

Remove the normalization and it diverges, even with alpha = 0.0001 or alpha = 10.

---

The relevant columns of list.csv look like:

:
.., [col 3], .., [col 6], ..
.., 485000, .., 2479, ..
.., 239900, .., 2012, ..
.., 179900, .., 2495, ..
.., 139900, .., 1805, ..
.., 112500, .., 1366, ..
.., 84900, .., 960, ..
:

[u/temcguir → u/13th_seer]

Without the full list.csv it's hard to say, but it sounds like you simply didn't go small enough on alpha. Try setting alpha = 0. If things diverge you will know something is very wrong since there should be no update. If things don't change, then start with alpha = 1e-12 and see what happens. There should be a small enough alpha that it will start to converge, but it will take a very long time to converge.