Two features have standard deviations 1 and 1000 and are uncorrelated. Compute the condition number of the Hessian for a squared-error linear model on them, state the resulting gradient descent convergence factor, and say what standardisation does to both.

Two features have standard deviations 1 and 1000 and are uncorrelated. Compute the condition number of the Hessian for a squared-error linear model on them, state the resulting gradient descent convergence factor, and say what standardisation does to both.

Approach: Write the Hessian of the squared-error loss as proportional to the feature second-moment matrix, read off the eigenvalues for uncorrelated features, and use the standard convergence factor in the condition number.

10^6. The Hessian is 2*X^T X/n, which for uncorrelated centred features is diagonal with entries proportional to the feature variances 1 and 10^6, so the condition number is kappa = 10^6/1 = 10^6. Gradient descent contracts the error by a factor of (kappa - 1)/(kappa + 1) per step, which here is 0.999998, so reducing the error by a factor of e takes roughly kappa/2 = 500,000 iterations. The largest stable learning rate is set by the big eigenvalue at 2/L, and at that rate the small-eigenvalue direction moves by about 2/kappa of what it needs each step, which is the whole problem. Standardising each column to unit variance makes the Hessian the identity up to a constant, so kappa = 1 and gradient descent converges in one step for uncorrelated features. With correlated features standardisation removes the scale part of the ill conditioning but not the correlation part, and whitening or a PCA rotation is needed to remove the rest. This is also why a penalty must be applied to standardised features: a fixed lambda penalises a coefficient on a feature measured in basis points a million times more weakly than the same economic effect measured in percent.

Follow-up: With the two features correlated at 0.99 and both standardised, what is the condition number, and what does that say about the value of decorrelation over rescaling?

Key concepts: condition number, Hessian, standardization, convergence rate.