Migrated to Typst!

Gradient descent

Gradient descent is a method to find local optima of a differentiable function $f$. By intuition, the gradient tells us direction of greatest increase, and vice-versa for negative gradient. So we take steps in directions that reduce function value.

The algorithm works as follows:

• Pick an initial point $x_0\in R^n$
• Repeat $x_{t+1}=x_t-{\gamma }_t\nabla f(x_t)$, for $t=1,2,3,\dots$

Where ${\gamma }_t$ is the $t^{\text{th}}$ step size / learning rate.

Possible Stopping Criteria

We could iterate until $||\nabla f(x_t)||\le ϵ$ for $ϵ>0$

slides 16-17 have some shit ??

Backtracking line search

In exact line search, instead of picking a fixed step size that may or may not result in a decrease in function value, we consider minimising the function along the direction specified by the gradient to guarantee that the next iteration decreases the function value.

We choose $x_{t+1}\in \arg {\min }_{\gamma \ge 0}f(x_t-\gamma \nabla f(x_t))$

With backtracking line search, we start with a large step size, $\gamma$, and keep shrinking it until $f(x_t-\gamma \nabla f(x_t))<f(x_t)-C$

This always guarantees a decrease, but it may not decrease as much as line search. (though in practice this isn’t a huge issue, as it’s still typically faster)

Slide 21 algorithm

slides 22-23 example

Optimality criterion

An unconstrained problem: $x$ is optimal if and only if $x\in \text{dom }{f}_0,\nabla f_0(x)=0$.

Slides 24-28

Subgradients

Slides 29-37

Stochastic gradient descent

Slides 38-41