Problem 421797 · medium · Level 04 Non-Linear Data Structures

Descend Until the Loss Stops Falling

gradient descent · learning rate · stopping rule · mean squared error · linear regression

A bakery wants to predict how many minutes a delivery takes from its distance in kilometres, with the line minutes ≈ w · km + b. The loss of (w, b) is the mean squared error on the recorded deliveries, xs (distances) and ys (minutes).

Write descend(xs, ys, lr, tol, max_steps) that trains the line by gradient descent and returns the tuple (w, b, steps, loss):

  1. Start at w = 0.0, b = 0.0 and compute the loss there.
  2. One step: compute both partial derivatives of the loss at the current (w, b), then set w ← w - lr · ∂L/∂w and b ← b - lr · ∂L/∂b. Then compute the new loss.
  3. Stop as soon as the loss after a step is not lower than the loss before it by at least tol (this includes a loss that went up), or when max_steps steps have been taken, whichever comes first.

steps is the number of steps taken and loss is the loss at the returned (w, b). The step that triggers the stop counts, and its parameters are the ones returned.

Examples

Input:  xs = [1, 2, 3, 4, 5, 6], ys = [9, 11, 15, 16, 21, 24], lr = 0.05, tol = 1e-6, max_steps = 10000
Output: (3.0312845622420777, 5.388384536199617, 323, 0.5809783430738948)
Explanation: step 323 lowers the loss by less than 1e-6, so the descent stops there,
close to the least-squares line w = 3.0286, b = 5.4.

Input:  the same data, lr = 0.065, tol = 1e-6, max_steps = 10000
Output: (8.428333333333333, 2.08, 1, 328.3338865740739)
Explanation: the first step overshoots: the loss rises from 283.33 to 328.33, so it stops at once.

Constraints

  • 1 <= len(xs) == len(ys) <= 200, 0 < lr <= 1, 0 < tol <= 1, 0 <= max_steps <= 20000
  • floats are compared with a tolerance of 1e-6; the tests avoid losses that fall by almost exactly tol

Goals

  • Implement batch gradient descent for a straight line from a stated starting point
  • Update both parameters from the same gradient, computed before either changes
  • Stop by a precise rule: a fixed step budget, or a loss that no longer falls by enough
Starting Python…