Deep Networks Always Grok and Here is Why
Ahmed Imtiaz Humayun Randall Balestriero Richard Baraniuk
Grokking, or delayed generalization, is a phenomenon where generalization in
a deep neural network (DNN) occurs long after achieving near zero training
error. Previous studies have reported the occurrence of grokking in specific
controlled settings, such as DNNs initialized with large-norm parameters or
transformers trained on algorithmic datasets. We demonstrate that grokking is
actually much more widespread and materializes in a wide range of practical
settings, such as training of a convolutional neural network (CNN) on CIFAR10
or a Resnet on Imagenette. We introduce the new concept of delayed robustness,
whereby a DNN groks adversarial examples and becomes robust, long after
interpolation and/or generalization. We develop an analytical explanation for
the emergence of both delayed generalization and delayed robustness based on a
new measure of the local complexity of a DNN's input-output mapping. Our local
complexity measures the density of the so-called 'linear regions' (aka, spline
partition regions) that tile the DNN input space, and serves as a utile
progress measure for training. We provide the first evidence that for
classification problems, the linear regions undergo a phase transition during
training whereafter they migrate away from the training samples (making the DNN
mapping smoother there) and towards the decision boundary (making the DNN
mapping less smooth there). Grokking occurs post phase transition as a robust
partition of the input space emerges thanks to the linearization of the DNN
mapping around the training points. Website: https://bit.ly/grok-adversarial