Theo HOPSORE

grokfast paper notes

  • Gradient updates can be decomposed into fast-varying and slow-varying components.
  • fast varying components contribute to overfitting and slow-varying ones to generalization.
  • They accelerate generalization under grokking by amplifying the low-frequency part of the optimizer’s gradient using LPF.
  • Grokking is a state transition phenomenon.

With \(g(t) = \frac{\partial l(t)}{\partial \theta(t)}\), we have this simple discrete optimizer abstraction:

\[\theta (t+1) = \theta(t) + u(g(t), t) = \theta (0) + \sum^T_{\tau = 0}u(g(\tau), \tau)\]

Since optimization a collection of discrete random signals \(u(t)\), it’s dual representation \(U(w)\) in the frequency domain is:

\[U(w) = \mathcal{F}\{u(t)\} = \sum^T_{t=0} u(t)e^{-iwt}\]

Since they assume grokking is linked to slow varying compononents of \(u(t)\), it will be related to low frequency part of \(U(w)\). \(U(w)\) can be represented by \(G(w) = \sum^T_{t=0}g(t)e^{-iwt}\) since optimizer are first order with \(g(t)\) linearly correlated with \(u(t)\).

Low Pass Filter - Grokfast MA

\(\hat{g}(t)\) convolved gradient \(g(t)\) by a univariate time-invarient LPF \(h(t)\) :

\[\hat{g}(t) = g(t) + h(t) * g(t) \text{, and in frequency domain : } \hat{G}(w) = G(w) + H(w)G(w) = (1+H(w))G(w)\]

so

\[\hat{u}(t) = u(\hat{g}(t), t) = u( g(t) + h(t) * g(t), t)\]

The goal is to design a filter \(h(t)\) with low pass proprieties in \(H(w)\): window moving average (MA) over fixed size window of width \(w\):

\[h(t) = \begin{cases} \lambda / w &\quad\text{if } 0 \le t \lt w\\ 0 &\quad\text{otherwise} \end{cases}\]

One major flaw is the memory scaling: you need \(w\) times more memory than originaly needed + non linear training time scaling. So non applicable to actual big models.

Exponential Moving Average LPF

New LPF with smaller memory footprint (size of the model params)

\[h(t) = \lambda(1-\alpha)\sum^t_{\tau = 0}\alpha^{\tau}\delta(t-\tau) = \lambda\alpha^t(1-\alpha)\]

with \(\delta(t)\) the discrete unit impule at the origin.

We can then express the convolution \(\mu_t = \sum_{\tau = 0}^t h(\tau)g_{t-\tau}\) as a recursive algorithm:

\[\begin{align} \mu_t &= \sum_{\tau = 0}^t h(\tau)g_{t-\tau} \\ &= \sum_{\tau = 0}^t \alpha^{\tau}(1-\alpha)g_{t-\tau} \\ &= (1-\alpha)g_t + \sum_{\tau = 1}^t \alpha^{\tau}(1-\alpha)g_{t-\tau} \\ &= (1-\alpha)g_t + \alpha\sum_{\tau = 1}^t \alpha^{\tau-1}(1-\alpha)g_{t-\tau} \\ &= (1-\alpha)g_t + \alpha\sum_{\sigma = 0}^{t-1} \alpha^{\sigma}(1-\alpha)g_{(t-1) - \sigma} \\ &= (1-\alpha)g_t + \alpha \mu_{t-1} \end{align}\]

Discussion

  • Removing fast gradient result in a delayed and unstable generalization
  • State transition can be exploited for faster generalization under grokking (apply MA only after overfitting)
  • Following Omnigrok[1], weight decay accelerate generalization under grokking.

Trajectories

Theses observations support the interpretation that grokking is a state transition phenomenon.

References

[1] Kumar et al. Grokking as the Transition from Lazy to Rich Training Dynamics. 2023 cs.LG