Timezone: »

 
Poster
Recurrent Convolutional Neural Networks Learn Succinct Learning Algorithms
Surbhi Goel · Sham Kakade · Adam Kalai · Cyril Zhang

Wed Nov 30 02:00 PM -- 04:00 PM (PST) @ Hall J #716
in Poster Session 4 »

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.

Keywords: learning algorithms · universality · recurrent convolutional neural networks · Turing completeness

Author Information

Surbhi Goel (Microsoft Research NYC)
Sham Kakade (Harvard University & Amazon)
Adam Kalai (Microsoft Research New England (-(-_(-_-)_-)-))
Cyril Zhang (Microsoft Research NYC)

More from the Same Authors