How Long Until Descent Finds the Formula?

The least-squares line has a formula: slope = Σ (x - x̄)(y - ȳ) / Σ (x - x̄)² and intercept = ȳ - slope · x̄. 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

• 2 <= len(xs) == len(ys) <= 100, and xs contains at least two different values
• 0 < lr <= 1, 1e-10 <= tol <= 1, 0 <= max_steps <= 20000
• the tests never let descent run long enough to overflow; floats are compared with a tolerance of 1e-6

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