Skip to yearly menu bar Skip to main content


Poster

Recurrent Convolutional Neural Networks Learn Succinct Learning Algorithms

Surbhi Goel · Sham Kakade · Adam Kalai · Cyril Zhang

Hall J (level 1) #716

Keywords: [ learning algorithms ] [ universality ] [ recurrent convolutional neural networks ] [ Turing completeness ]


Abstract:

Neural networks (NNs) struggle to efficiently solve certain problems, such as learning parities, even when there are simple learning algorithms for those problems. Can NNs discover learning algorithms on their own? We exhibit a NN architecture that, in polynomial time, learns as well as any efficient learning algorithm describable by a constant-sized program. For example, on parity problems, the NN learns as well as Gaussian elimination, an efficient algorithm that can be succinctly described. Our architecture combines both recurrent weight sharing between layers and convolutional weight sharing to reduce the number of parameters down to a constant, even though the network itself may have trillions of nodes. While in practice the constants in our analysis are too large to be directly meaningful, our work suggests that the synergy of Recurrent and Convolutional NNs (RCNNs) may be more natural and powerful than either alone, particularly for concisely parameterizing discrete algorithms.

Chat is not available.