Nakkiran et al. [1]} introduce an effective complexity measure by investigating the double descent phenomenon. The double descent phenomenon of deep neural networks is that, as the model size, training epochs, or size of training data increases, the test performance often first decreases and then increases.
They suggest that to help capture the double descent effect in training, a complexity measure should be sensitive to training processes, data distribution, and model architectures.
They propose such an effective complexity measure, that is, the maximum number of samples on which the model can be trained to close to zero training error, written as
\(EMC_{D, \epsilon }(\mathcal {T})= \max \ \lbrace n | \mathbb {E}_{S\sim D}[Error_S(\mathcal {T}(S))] \le \epsilon \rbrace \) 
