Skip to the content ForoHackers
Log inJoin

Gradient descent on a parabola, in four lines of Haskell

Functional programmingHaskellOptimization
#1081 · lambda_llama · · Report

Gradient descent is an iterated function. Not a metaphor: the sequence of positions is literally iterate applied to one update step.

Minimise f(x) = (x - 3)^2. Its derivative is 2 * (x - 3):

step :: Double -> Double -> Double
step lr x = x - lr * 2 * (x - 3)

positions :: Double -> [Double]
positions lr = iterate (step lr) 0

main :: IO ()
main = print (take 6 (positions 0.25))

Each step shrinks the distance to the minimum by a constant factor: x' - 3 = (1 - 2*lr) * (x - 3). So the iteration converges exactly when |1 - 2*lr| < 1, that is 0 < lr < 1. With lr = 0.5 you land on 3 in one step. With lr = 1 you bounce between 0 and 6 forever. Above 1 you diverge.

That factor is a miniature of the whole theory: the safe learning rate depends on the curvature (here the curvature is 2, so the limit is 2/2).

Laziness bonus: iterate gives you the infinite sequence of positions and you decide when to stop, with takeWhile on the size of the step, say.

#1670 · off_by_two · · Report

Check on lr = 1: from 0 you go to 6, then back to 0. Right, a two-cycle. Nice small example of a method that is "correct" and still never arrives.

#1671 · tabs_over_spaces_42 · · Report

I do not know Haskell, but I read this one on the first try. That says something good about either the language or the example. I am going to credit the example.

#1674 · monad_tutorial_no_47 · · Report

No monads were used in this post. I am a little suspicious. The closest thing is the list itself, which is a monad if you squint, but I promise not to explain it.

#1676 · lambda_llama · · Report

Welcome. And no, iterate is just a function that applies a function over and over. If a tutorial starts with an analogy before showing a type signature, be wary.

Log in or join to reply.