Deep learning: The Adam optimizer

Implement the optimizer that trains most modern networks.

What to build

A program that minimizes f(x) = x² with Adam and prints x after every step.

Requirements

  • Use β₁ = 0.9, β₂ = 0.999 and ε = 1e-8. Each step t (from 1): g = 2x; m ← 0.9 m + 0.1 g; s ← 0.999 s + 0.001 g²; m̂ = m / (1 − 0.9ᵗ); ŝ = s / (1 − 0.999ᵗ); x ← x − rate × m̂ / (√ŝ + ε).
  • Print step I: x X with four decimal places.

Input

One line: the starting x, the learning rate and the number of steps.

Output

One line per step.

Constraints

At most 1,000 steps.

Example

Input:

1 0.1 3

Output:

step 1: x 0.9000
step 2: x 0.8004
step 3: x 0.7016

Why it works

Dividing the averaged gradient by the square root of the averaged squared gradient makes each step about the size of the learning rate, while bias correction keeps the first steps from being too small.

Examples

Example 1 · Input
1 0.1 3
Expected output
step 1: x 0.9000
step 2: x 0.8004
step 3: x 0.7016
Example 2 · Input
-2 0.5 1
Expected output
step 1: x -1.5000

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

Hints

Hint 1

Keep m and s, both starting at 0; at step t use m̂ = m / (1 − 0.9ᵗ) and ŝ = s / (1 − 0.999ᵗ).

Hint 2

The update is x ← x − rate × m̂ / (√ŝ + 1e-8), with g = 2x for f(x) = x².

Solution

Show one correct solution (try it yourself first)
import math

x, rate, steps = input().split()
x, rate, steps = float(x), float(rate), int(steps)
m = s = 0.0
for t in range(1, steps + 1):
    g = 2 * x
    m = 0.9 * m + 0.1 * g
    s = 0.999 * s + 0.001 * g * g
    m_hat = m / (1 - 0.9 ** t)
    s_hat = s / (1 - 0.999 ** t)
    x -= rate * m_hat / (math.sqrt(s_hat) + 1e-8)
    print(f"step {t}: x {x + 0.0:.4f}")

Lesson: Optimizers: momentum, RMSProp and Adam →