How Long Until Descent Finds the Formula? · Python problem 494594

The least-squares line has a formula:

\text{slope} = \frac{\sum_i (x_i - \bar{x})(y_i - \bar{y})}{\sum_i (x_i - \bar{x})^2}, \qquad \text{intercept} = \bar{y} - \text{slope}\cdot\bar{x}

where \bar{x} and \bar{y} are the means of xs and ys. Gradient descent on the mean squared error should find the same line without the formula. How many steps does it take?

Write steps_to_formula(xs, ys, lr, tol, max_steps) that returns a tuple (slope, intercept, steps):

slope and intercept come from the formula;
run gradient descent on the mean squared error of w·x + b from w = 0.0, b = 0.0 with learning rate lr (each step computes both partial derivatives at the current point, then updates both). steps is the smallest number t of steps, from 0 to max_steps, after which both |w - slope| <= tol and |b - intercept| <= tol, or None if that never happens within max_steps steps.

Examples

Input:  xs = [1, 2, 3, 4, 5, 6], ys = [9, 11, 15, 16, 21, 24], lr = 0.05, tol = 1e-4, max_steps = 10000
Output: (3.0285714285714285, 5.4, 582)

Input:  xs = [-2.5, -1.5, -0.5, 0.5, 1.5, 2.5], the same ys, lr = 0.1, tol = 1e-6, max_steps = 1000
Output: (3.0285714285714285, 16.0, 75)
Explanation: the same distances shifted to have mean 0. The slope is unchanged, the intercept moves,
and descent needs far fewer steps even with a much smaller tolerance.

Constraints

xs contains at least two different values, and lr > 0.
The tests never let descent run long enough to overflow.

Goals

Compute the least-squares line from its formula
Run gradient descent on the same loss and measure its distance from the exact answer after every step
See how the learning rate and centred inputs change the number of steps needed