  Optimizing Neural networks is a difficult task which is still not well
understood. On the other hand, fixed representation methods such as kernels and
random features have provable optimization guarantees but inferior performance
due to their inherent inability to learn the representations. In this paper, we
aim at bridging this gap by presenting a novel architecture called RedEx
(Reduced Expander Extractor) that is as expressive as neural networks and can
also be trained in a layer-wise fashion via a convex program with semi-definite
constraints and optimization guarantees. We also show that RedEx provably
surpasses fixed representation methods, in the sense that it can efficiently
learn a family of target functions which fixed representation methods cannot.
