SGD on Neural Networks Learns Functions of Increasing Complexity

Neural networks have been extremely successful in modern machine learning, achieving the state-of-the-art inawiderangeofdomains, including image-recognition, speech-recognition, andgame-playing [ 14, 18, 23, 37]. Practitioners often train deep neural networks with hundreds of layers and millions of parameters and manage to find networks with good out-of-sample performance.However, this practical prowess isaccompanied by feeble theoreticalunderstanding.