Gradient descent on one number

The simplest loss there is, L(w) = (w − t)², has its bottom at w = t. Walk down to it with gradient descent.

What to build

A program that runs gradient descent on (w − t)² and prints w after every step.

Requirements

  • Start at the given w0.
  • Each step: w ← w − rate × 2 × (w − t).
  • Print step i: w = W with 4 decimal places after each step.

Input

One line: t, w0, rate and steps.

Output

One line per step.

Constraints

1 ≤ steps ≤ 100.

Example

Input:

3 0 0.25 3

Output:

step 1: w = 1.5000
step 2: w = 2.2500
step 3: w = 2.6250

Why it works

The gradient 2(w − t) is positive when w is too big and negative when it is too small, so stepping against it always moves w towards t, unless the step is so big that it jumps past.

Examples

Example 1 · Input
3 0 0.25 3
Expected output
step 1: w = 1.5000
step 2: w = 2.2500
step 3: w = 2.6250
Example 2 · Input
-1 1 0.5 2
Expected output
step 1: w = -1.0000
step 2: w = -1.0000

Prompts inside input() are ignored when checking, so input("n: ") is fine.

Hints

Hint 1

The slope of (w − t)² is 2 × (w − t).

Hint 2

Each step: w = w − rate × 2 × (w − t).

Solution

Show one correct solution (try it yourself first)
t, w, rate, steps = input().split()
t, w, rate = float(t), float(w), float(rate)
for i in range(int(steps)):
    w = w - rate * 2 * (w - t)
    print(f"step {i + 1}: w = {w:.4f}")

Lesson: Gradient descent →