Gradient Descent in One Dimension

The optimisation loop in its smallest form.

Given a gradient function grad, a starting point x0, a learning rate and a number of steps, repeatedly move against the gradient:

x = x - lr * grad(x)

Return (x, history) where history records the value of x before each step, so it has exactly steps entries and history[0] == x0.

Everything that goes wrong in training already shows up here. Too small a learning rate and you never arrive; too large and the step overshoots the minimum by more than it started from, so the iterates grow without bound. For f(x) = x^2 the gradient is 2x and the update is x * (1 - 2 * lr), which converges exactly when lr < 1.

Function signature

def descend(grad, x0, lr, steps):

Example

Input

descend(lambda x: 2 * x, x0=10.0, lr=0.1, steps=50)

Output

(0.00014272476927059603, [10.0, 8.0, 6.4, 5.12, ...])

Reasoning

Each step multiplies x by 1 - 2 * 0.1 = 0.8. After 50 steps, x = 10 * 0.8^50, which is about 0.00014. history holds the 50 values from before each step, starting at 10.0.

Constraints and notes

• history has exactly steps entries, and history[0] == x0.
• Record x before each step, not after.