Title: Optimisation

Q: Gradient descent with momentum
A: After computing gradients \(\nabla_w, \nabla_b\), then compute velocities for \(w\) and \(b\) as
\[
\begin{align*}
v_w &\mapsto \beta v_w + (1-\beta)\nabla_w \\
v_b &\mapsto \beta v_b + (1-\beta)\nabla_b.
\end{align*}
\]
FInally, update the weights as biases as
\[
\begin{align*}
w \mapsto w - \alpha v_w  \\
b \mapsto b - \alpha v_b.
\end{align*}
\]
Usually \(\beta=0.9\) is quite robust

Q: RMSProp
A: In Root Mean Square Propagation, we compute gradients \(\nabla_w, \nabla_b\) and then update a running mean gradient squared:
\[
\begin{align*}
s_w &\mapsto \beta s_w + (1-\beta)\|\nabla_w L\|^2  \\
s_b &\mapsto \beta s_b + (1-\beta)\|\nabla_b L \|^2.
\end{align*}
\]
Finally, update the weights as biases as
\[
\begin{align*}
w \mapsto w - \alpha \nabla_w / \sqrt s_w  \\
b \mapsto b - \alpha \nabla_b / \sqrt s_b.
\end{align*}
\]
We will need to add an \(\epsilon\) to the denominators to avoid numerical precision issues.
This method is useful for sparse features and saddle points where we want to give less important parameters a chance to update too.

Q: AdaGrad
A: The Adaptive Gradient Algorithm is similar to RMSProp with no decay parameter, simply tracking the sum of gradients squared, which is a good proxy for distance moved in that direction:
\[
\begin{align*}
s_w &\mapsto s_w + \|\nabla_w L\|^2  \\
s_b &\mapsto s_b + \|\nabla_b L \|^2.
\end{align*}
\]

Q: Adam Algorithm
A: The Adaptive Movement Estimation algorithm combines RMSProp and Momentum:
\[
\begin{align*}
v_w &\mapsto \beta_v v_w + (1-\beta_v)\nabla_w  \\
v_b &\mapsto \beta_v v_b + (1-\beta_v)\nabla_b \\
s_w &\mapsto \beta_s s_w + (1-\beta_s) \|\nabla_w L\|^2  \\
s_b &\mapsto \beta_s s_b + (1-\beta_s) \|\nabla_b L \|^2.
\end{align*}
\]
then applies bias corrections for initialising at zero
\[
\begin{align*}
v_w &\mapsto \frac{v_w}{1-\beta_v^t} \\
v_b &\mapsto \frac{v_b}{1-\beta_v^t} \\
s_w &\mapsto \frac{s_w}{1-\beta_s^t} \\
s_b &\mapsto \frac{s_b}{1-\beta_s^t}
\end{align*}
\]
and update as
\[
\begin{align*}
w \mapsto w - \frac{\alpha v_w}{\sqrt s_w + \epsilon}  \\
b \mapsto b - \frac{\alpha v_b}{\sqrt s_b + \epsilon}.
\end{align*}
\]
Usually \(\beta_v=0.9, \beta_s=0.999, \epsilon=10^{-8}\) and \(\alpha\) is tuned.

Q: Bias correction for EMA from zero
A: Given a sequence \((x_t)_{t\geq 0} \), consider an EMA initialised at zero:
\[\begin{align*}
y_0 &= 0\\
y_t &= \beta y_{t- 1} + (1 - \beta) x_t \quad (t \geq 1).
\end{align*}\]
Now assume that \(x_t=x\) is actually constant, we obtain a geometric series
\[\begin{align*}
y_t &= x (1 - \beta)\sum_{\tau = 0}^{t - 1}\beta^\tau \\
&=x (1 - \beta^t).
\end{align*}\]
Hence the bias correction
\[
y_t \mapsto \frac{y_t}{1 - \beta^t}.
\]

Q: Batch size schedule for SGD
A: - Increase batch size to fill GPU
- Increasing over time
  - a rough estimate of the proper direction is good enough early in training
  - later in training it's important to preserve our progress and not "bounce around" too much
- Multiple of 32 as CUDA groups into "warps" of 32 threads

Q: Gradient flow
A: Continuous time equivalent of standard gradient descent:
\[\frac{\mathrm{d}\mathbf{w}}{\mathrm{d}t}=−\nabla_wL(\mathbf{w}(t)).\]

Q: NTK
A: The form of the Neural Tangent Kernel comes from:
\[\begin{align*}
\frac{\mathrm{d}\mathbf{y}}{\mathrm{d}t} &= \nabla_\mathbf{w}\mathbf{y}^T \frac{\mathrm{d}\mathbf{w}(t)}{\mathrm{d}t} \quad \text{(chain rule)}\\
 &=−\nabla_\mathbf{w}\mathbf{y}^T \nabla_\mathbf{w}L \quad\text{(gradient flow)}\\
 &=−\nabla_\mathbf{w}\mathbf{y}^T \nabla_\mathbf{w} \mathbf{y} \nabla_\mathbf{y} L \quad\text{(chain rule)}\\
 &= -\textrm{NTK}(\mathbf{w}) \nabla_\mathbf{y} L\\
 \textrm{NTK}(\mathbf{w}) :&= \nabla_\mathbf{w}\mathbf{y}^T \nabla_\mathbf{w} \mathbf{y}.
 \end{align*}\]
The following properties hold in the limit as  \(n_1, \ldots, n_L \rightarrow \infty\) (\(\text{width}\to\infty\)), the NTK:
1. Converges to a deterministic limit, meaning that the kernel's limit is irrelevant to the initialization values and only determined by the model archite
2. Stays essentially constant during training.
Therefore the network output is a linear function of the weights during gradient descent after initialisation.

Q: Lazy training
A: When a network is heavily over-parameterized, the model is able to learn with the training loss quickly converging to zero but the network parameters hardly change.

Q: The Lottery Ticket Hypothesis
A: Dense, randomly-initialized, feed-forward networks contain subnetworks ("winning tickets") that - when trained in isolation - reach test accuracy comparable to the original network in a similar number of iterations.
The winning tickets we find have won the initialization lottery: their connections have initial weights that make training particularly effective.