Digital media is ubiquitous and produced in ever-growing quantities. This\nnecessitates a constant evolution of compression techniques, especially for\nvideo, in order to maintain efficient storage and transmission. In this work,\nwe aim at exploiting non-local redundancies in video data that remain difficult\nto erase for conventional video codecs. We design convolutional neural networks\nwith a particular emphasis on low memory and computational footprint. The\nparameters of those networks are trained on the fly, at encoding time, to\npredict the residual signal from the decoded video signal. After the training\nprocess has converged, the parameters are compressed and signalled as part of\nthe code of the underlying video codec. The method can be applied to any\nexisting video codec to increase coding gains while its low computational\nfootprint allows for an application under resource-constrained conditions.\nBuilding on top of High Efficiency Video Coding, we achieve coding gains\nsimilar to those of pretrained denoising CNNs while only requiring about 1% of\ntheir computational complexity. Through extensive experiments, we provide\ninsights into the effectiveness of our network design decisions. In addition,\nwe demonstrate that our algorithm delivers stable performance under conditions\nmet in practical video compression: our algorithm performs without significant\nperformance loss on very long random access segments (up to 256 frames) and\nwith moderate performance drops can even be applied to single frames in\nhigh-resolution low delay settings.\n