A Provably Correct Algorithm for Deep Learning that Actually Works

The success of deep convolutional neural networks (CNN) has sparked many works trying to understand their behavior. We can roughly separate these works into three categories: First, the majority of the works focus on providing various optimization methods and algorithms that prove well in practice, but have almost no theoretical guarantees. A second class of works focuses on analyzing practical algorithms (mostly SGD), but under strong assumptions on the data distribution, like linear separability or sampling from Gaussian distribution, that often make these problems trivially solvable by much simpler algorithms. A third class of works takes less restrictive assumptions on the data, provides strong theoretical guarantees, but these guarantees hold for algorithms that don't really work in practice. In this work, we study a new algorithm for learning deep convolutional networks, assuming the data is generated from some deep generative model.