Delivery Time Nudge

Easygradient descentAlso known as One Step of Gradient Descent for Linear Regression

A pizza place promises customers a delivery time. Its model is a straight line: minutes = w · distance + b, where w is minutes per kilometre and b is the fixed time to bake and pack. Each night it looks at the day's real deliveries and adjusts w and b a little so tomorrow's promises are closer.

That small adjustment is one step of gradient descent: work out which way each number should move to shrink the average squared miss, then move it a small amount that way. Training any neural network is this same step repeated millions of times, with far more numbers.

Your task

Write trainStep(distances, minutes, w, b, rate). The loss is the mean squared error L = (1/n) · Σ (w·xᵢ + b − yᵢ)², where xᵢ is distances[i] and yᵢ is minutes[i]. Its gradients are:

dL/dw = (2/n) · Σ (w·xᵢ + b − yᵢ) · xᵢ
dL/db = (2/n) · Σ (w·xᵢ + b − yᵢ)

Compute both gradients using the current w and b, then return [w − rate · dL/dw, b − rate · dL/db].

trainStep(distances: float[], minutes: float[], w: float, b: float, rate: float) → float[] Numbers are accepted within 1e-6.

Examples

Example 1

Input

distances = [1, 2, 3]
minutes = [5, 7, 9]
w = 1
b = 1
rate = 0.1

Output

[2.7333333333333334, 1.8]

Why

Predictions are 2, 3, 4 and the truth is 5, 7, 9, so the errors (prediction minus truth) are -3, -4, -5. dL/dw = (2/3)(-3·1 - 4·2 - 5·3) = (2/3)(-26) = -17.333…, dL/db = (2/3)(-12) = -8. Both are negative, so both numbers go up: w = 1 + 1.7333… = 2.7333…, b = 1 + 0.8 = 1.8.

Example 2

Input

distances = [2, 4]
minutes = [10, 16]
w = 3
b = 4
rate = 0.05

Output

[3, 4]

Why

The line 3·x + 4 gives exactly 10 and 16. Every error is 0, so both gradients are 0 and nothing moves. A perfect fit is a flat spot in the loss.

Constraints

1 ≤ n = distances.length = minutes.length ≤ 10,000
-1,000 ≤ distances[i], minutes[i], w, b ≤ 1,000
0 ≤ rate ≤ 1
Answers within 0.000001 of the expected values (or relatively that close) are accepted.

Start with brute force

Without the gradient formula you could probe: try w a tiny bit bigger and a tiny bit smaller, compute the loss each time, and see which is lower. Do the same for b. That costs several full passes over the data per number, and with millions of numbers in a real model it is hopeless. It also only approximates the slope.

The formula gives the exact slope for every number in a single pass. That is the whole reason calculus matters for training: the gradient tells you which way is downhill for all the weights at once.

Hints

0 of 4 shown

Hint 1
In the first example, every prediction is too low. Should b go up or down? What sign does dL/db have there, and what does subtracting it do?
Hint 2
The gradient points uphill, toward a bigger loss. Subtracting rate times the gradient moves downhill. When predictions are too low, the errors are negative, the gradient is negative, and subtracting it raises the numbers.
Hint 3
Both gradients start from the same per-delivery error, w·x + b − y. For w each error is weighted by its distance, because a long delivery is affected more by a change in minutes per kilometre.
Hint 4
Loop once, summing error and error · x. Multiply both sums by 2/n. Only then compute the new w and new b, both from the old values. If you update w first and use the new w for b's gradient, you get a different (wrong) step.

Walkthrough and solution

Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.

How to solve it

Every delivery contributes an error, prediction minus truth. The gradient for b is just the scaled sum of errors. The gradient for w weights each error by its distance. Then both numbers step against their gradient.

Trace the first example: w = 1, b = 1, rate 0.1, deliveries (1 km, 5 min), (2 km, 7 min), (3 km, 9 min).

Delivery 0: predict 1·1 + 1 = 2, error -3. Sums: error -3, error·x -3.
Delivery 1: predict 3, error -4. Sums: -7 and -3 - 8 = -11.
Delivery 2: predict 4, error -5. Sums: -12 and -11 - 15 = -26.
Scale by 2/3: dL/db = -8, dL/dw = -17.333….
Step: w = 1 - 0.1 · (-17.333…) = 2.7333…, b = 1 - 0.1 · (-8) = 1.8.

The true line here is 2x + 3. One step moved b from 1 toward 3, and w from 1 past 2. Overshooting is normal early on; with a sensible rate, repeated steps settle down. With a rate that is too large, they bounce further away each time.

Reference solution

function trainStep(distances, minutes, w, b, rate) {
  const n = distances.length;
  let gradW = 0, gradB = 0;
  for (let i = 0; i < n; i++) {
    const error = w * distances[i] + b - minutes[i]; // prediction minus truth
    gradW += error * distances[i];
    gradB += error;
  }
  gradW = (2 / n) * gradW;
  gradB = (2 / n) * gradB;
  // Both gradients used the old w and b. Now step downhill.
  return [w - rate * gradW, b - rate * gradB];
}

def train_step(distances, minutes, w, b, rate):
    n = len(distances)
    grad_w = grad_b = 0.0
    for x, y in zip(distances, minutes):
        error = w * x + b - y  # prediction minus truth
        grad_w += error * x
        grad_b += error
    grad_w *= 2 / n
    grad_b *= 2 / n
    # Both gradients used the old w and b. Now step downhill.
    return [w - rate * grad_w, b - rate * grad_b]

TimeO(n)One pass over the n deliveries to build both sums.

SpaceO(1)Two running sums.

Learn the idea: How Models Learn Regression and Classification Neural Networks

Ctrl+Enter runs

Run your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.

Write code