RedEx: Beyond Fixed Representation Methods via Convex Optimization
This work addresses the optimization challenges in neural networks for researchers and practitioners, offering a novel approach that bridges the gap between provable guarantees and performance, though it appears incremental in advancing existing methods.
The authors tackled the problem of neural network optimization by introducing RedEx, an architecture that matches neural network expressiveness and can be trained layer-wise with convex optimization guarantees, provably surpassing fixed representation methods by efficiently learning target functions they cannot.
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.