  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.

Machine Learning;Machine Learning