Thanks to the combination of state-of-the-art accelerators and highly\noptimized open software frameworks, there has been tremendous progress in the\nperformance of deep neural networks. While these developments have been\nresponsible for many breakthroughs, progress towards solving large-scale\nproblems, such as video encoding and semantic segmentation in 3D, is hampered\nbecause access to on-premise memory is often limited. Instead of relying on\n(optimal) checkpointing or invertibility of the network layers -- to recover\nthe activations during backpropagation -- we propose to approximate the\ngradient of convolutional layers in neural networks with a multi-channel\nrandomized trace estimation technique. Compared to other methods, this approach\nis simple, amenable to analyses, and leads to a greatly reduced memory\nfootprint. Even though the randomized trace estimation introduces stochasticity\nduring training, we argue that this is of little consequence as long as the\ninduced errors are of the same order as errors in the gradient due to the use\nof stochastic gradient descent. We discuss the performance of networks trained\nwith stochastic backpropagation and how the error can be controlled while\nmaximizing memory usage and minimizing computational overhead.\n