3. Gradients

• Loss derivative: n-dimensional, where each axis is a parameter of the model that we can tweak.
• We try to find the global minimum, i.e. where the mean loss is the least.

Closed Form for MSE Regression

We try to minimize the MSE. Since mean = sum $\cdot$ constant, we minimize the loss sum:

$$\sum _{i=1}^n{\left(y_i-w^{\top }{x}_i\right)}^2=\Vert y-Xw{\Vert }_2^2$$

where $y$ = output vector, $w$ = weights vector, and $X$ = input matrix. Therefore, for the optimal weights:

$$\hat{w}=\arg \underset{w\in {\mathbb{R}}^d}{\min }\Vert y-Xw{\Vert }_2^2$$

Minima always have a slope of 0 $⟹$ we are looking for $\hat{w}$ s.t.

$$\begin{array}{rlrl}{\nabla }_w\Vert y-X\hat{w}{\Vert }_2^2=0& ⟺2X^{\top }\left(X\hat{w}-y\right)=0& & (\text{chain rule})\\ & ⟺X^{\top }\left(X\hat{w}-y\right)=0& & \\ & ⟺X^{\top }X\hat{w}=X^{\top }y& & \end{array}$$

which is the normal equation we already know 🥳.

Gradient Descent

It is not always possible to find a minimum directly. Therefore: Iteratively move towards minimum by moving in direction of gradient derivative, where $\eta$ is the step size:

$$w_{t+1}=w_t-\eta \nabla L(w^t)$$

Usually: interrupt when progress distance is low:

$$\Vert \nabla L(w_t)\Vert \le ϵ/\eta$$

Justification:

We know that $w^{t+1}=w^t+\eta v$, where $v$ is some normalized vector. We estimate the loss of $w_{t+1}$ using a first order Taylor expansion (b/c of viscinity to $w^t$ for sufficiently small $\eta$):

$$L(w^{t+1})=L(w^t+\eta v)=L(w^t)+\eta \nabla L(w^t{)}^{T}v+o(\eta )$$

For small $\eta$, we neglect $o(\eta )=$ higher order remainders:

$$L(w^{t+1})\approx L(w^t)+\eta \nabla L(w^t{)}^{T}v$$

We now try find a $v$ of length 1 (we control length with $\eta$) that minimizes $\eta \nabla L(w^t{)}^{T}v$. By Cauchy-Schwarz:

$$\begin{array}{rlrl}& \nabla L(w^t{)}^{T}v\le \Vert \nabla L(w^t)\Vert \Vert v\Vert & & \\ ⟺& \nabla L(w^t{)}^{T}v\ge -\Vert \nabla L(w^t)\Vert & & (\Vert v\Vert =1)\end{array}$$

Equality only holds if $\nabla L(w^t{)}^T$ and $v$ point in the same direction. Hence:

$$v=-\frac{\nabla L(w^t)}{\Vert \nabla L(w^t)\Vert }$$

Plugging into $w^{t+1}=w^t+\eta v$:

$$w^{t+1}=w^t-\eta \frac{\nabla L(w^t)}{\Vert \nabla L(w^t){\Vert }_2}$$

We skip the normalization to save computation and not overshoot minima.

Optimizer

Goal: Large steps in flat areas, small steps in high curvature ones, dampened oscillations

Larger step sizes make convergence faster but may lead to oscillation in ill-conditioned gradients (left).

Momentum: combine new step with weighted previous step. $w^{t+1}=w_t-\eta {\nabla }_{w}L(w^t)+\beta \left(w^t-w^{t-1}\right)$

Adaptive methods (Adam, AdaGrad, RMSProp): Different step size for different entries $w_i$. Intuitively: the elements 𝑖 that already changed a lot have smaller step size.

$$w_i^{t+1}=w_i^t-\frac{\eta }{\sqrt{{\text{previous\_change}}_i+\gamma }}\frac{\partial L}{\partial w_i}(w^t)$$

$\text{previous\_change}=(w_i^t-w_i^{t-1}{)}^2$ $\gamma >0$ to prevent division by 0.

Mini Batching

Continuously adjust the gradient for a subset of the training data.

Pros:

• Less memory (although same as calculating gradients for subsets first and then averaging)
• Converges faster
• Variance helps escape poor local minima

Cons:

• Never settles (can be solved with optimizer)

Convexity

Every slice roughly looks like either a quadratic or linear function (i.e. looks like a polynomial with only even degrees)

More convex $⟹$ better for learning (less likely to get stuck in local minima)

**Conditions for all $w,v$:

0. $L(\lambda w+(1-\lambda )v)\le \lambda L(w)+(1-\lambda )L(v)$ for $0\le \lambda \le 1$
   • Pick any two inputs $w$ and $v$
   • The line between $L(w)$ and $L(v)$ is $\lambda L(w)+(1-\lambda )L(v)$
   • For any input between $w$ and $v$, $\lambda w+(1-\lambda )v$, the loss must be below
1. $L(v)\ge L(w)+\nabla L(w{)}^T(v-w)$
   • The graph of the function lies above all its tangent planes
   • We check where we would land if we moved from $L(w)$ in the direction of $\nabla L(w)$
2. ${\nabla }^{2}L(w)$ is PSD
   • Hessian contains 2nd derivatives along diagonal.

Strong convexity: no linear parts